1000000000 610363186 847371151 1000
665297781 786213968 431288588 909998294 800117192 27065236 692646918 881650665 265579161 44215444 99633849 582605709 402479473 972764887 466468004 538706661 251804078 454620935 67255325 783865759 693395798 583174943 305918899 503101381 981809034 107696 736321655 483548150 915653608 522392060 930220290 531480676 137508642 415350325 397326104 259446388 49906285 182584648 671276492 338678336 261395181 591023935 153674749 462437732 447651634 774818731 37593315 470669793 291214033 319029521 736243114 237259790 821916681 265106642 692523199 949789079 859119408 613606458 667275115 733261574 592374311 300874291 543978782 813512198 744881563 468525961 767043204 350813493 206040819 110672548 352692740 652032266 97260827 427680828 403926493 596776490 200110923 304900062 559368695 700000525 993422215 835570710 206982833 910716317 219462633 205317511 838945278 849411370 659368964 998567831 344842715 786897978 116293003 326391054 981218543 813135291 852656555 440360260 906259064 468339107 847813497 647454637 470453113 944432163 867205513 151553205 239119496 939474138 368331201 420899536 247376737 132486570 834990277 949711024 620982443 81411887 342518476 378127155 778991015 367943572 348469874 545275352 56385894 637448937 882127906 770367480 387345403 17529147 407122393 623168212 310401068 672979716 802353747 35872895 546600088 846387376 300967510 429269215 256392811 268053578 829544266 686659144 103131036 304035729 946380780 484154761 373538047 959264151 119114407 501096251 567585653 289718400 951729454 184997101 763714281 236171051 777082904 510576700 991702118 916921262 353007965 581301320 19414698 959073572 137278625 844421900 553200503 110421041 420573482 136096276 300043483 539232431 498494283 859724240 41599647 159348433 257022428 112608262 673974830 592480111 969149506 906043477 66185465 513454402 238957882 370711287 694549065 638780589 714624776 896331191 40551835 802383149 530032309 490866413 433390147 797420231 870140120 81369173 698357698 225974414 127154781 344192308 592934168 46706075 83746353 923174489 224295451 899852875 173694530 853706243 902597300 128355498 123548281 933022344 380962020 106193416 233840458 261511999 406892010 300787013 150839259 50997536 269620802 326332447 737651871 291910169 207827214 69850659 380221130 538957068 165427233 417932392 844461637 147318439 396281284 952767647 454046080 69335348 309332145 961201854 473842427 733878075 216496787 824209494 145709087 801284435 317565514 826747809 931246579 600450723 749661014 266122155 580381014 592986027 918300288 981728057 786602501 518911778 419170782 183237493 181011859 355745044 412489663 636561928 195503340 174663873 190498524 884333821 264217063 773746071 263007695 848992742 65930705 511009580 750923513 10106378 206703739 514959157 559462692 132324457 257849137 48454316 475395202 254259753 924969771 332828967 735298160 461545265 480344294 755528588 98182208 880937363 88264102 617320867 818321415 682842155 375506323 754090758 628635338 928341156 87380016 790872994 352385454 856185582 696908353 562894939 909791544 782930174 1404232 294395845 108661033 904898487 149699761 226807473 169733689 855836210 193722267 304941020 174007977 753100855 97462970 603864355 140515569 486915113 595875700 92918922 467719088 90830575 802359638 134882932 308465522 354512799 103242594 31507388 189967937 556684296 680471523 260733365 205300658 555688503 50305924 456866380 225477214 360657373 295882756 403112270 870765831 934025942 68556027 96177576 475092271 531607554 122455137 814170539 6286235 426069748 170050521 812122516 187777956 256895628 128964309 692149943 45184605 282195423 140856768 852729185 587302443 957334695 976752347 911715167 901007230 247594596 572817312 171390089 777672002 747878778 376852761 835095930 577937348 324480858 15067252 905992648 285644285 123821933 163582391 550185780 981570704 289462680 948819111 662994585 731096038 703441162 838141402 223569320 506937620 702505913 151796988 41413083 244992756 867107196 646623033 452328390 191157156 142801786 256658586 439958305 593052320 958753319 123503975 188371402 567274542 429593344 335319797 722746854 275652712 772920811 351506580 43593969 391930162 837904191 531739741 196638399 997997890 429520739 188797789 217359683 294525440 139280551 131062233 518486839 793413773 105593571 889663778 724233011 246921487 808612129 98643372 41794526 213462719 296502726 85521421 691979710 405312448 268193655 512175519 928155367 186049764 202201919 14789658 535437584 69259937 115641291 110494108 574877131 431021267 712101541 364243259 434326642 430972747 970376128 47034557 235834209 484496931 755680119 497488481 61337379 105186696 493766594 858341753 428452351 486011672 444136746 574907423 940138911 803752777 283565184 613843198 351197001 209200430 600913677 148379989 593977762 406529661 324797899 772117640 811255289 393975823 859581863 869886475 113324952 908223601 200315937 529353293 889796156 801634814 837667846 854456620 629273254 912368729 74263706 462116238 413011093 810309753 608488027 541151178 534612004 152380583 186217836 879512779 841351158 482855641 14064677 161833572 148814081 373569242 409816692 809103321 733080049 762717510 663318433 805308660 306980209 86919148 561257282 229235933 182671616 333985128 839551668 303589865 13732589 30230048 196542623 462032481 79057421 499455884 915216491 691959406 64054716 678321471 632039804 165134345 864081297 256212648 461271104 167487661 687807436 75121857 926424793 91321780 468107485 176168013 549603908 865724412 776942534 298861757 5316372 231709660 956412012 501596292 381831748 765068206 443018636 488419506 110405087 152443007 161644584 193726639 378429627 493937205 504575359 657005094 997452210 921961794 243633636 572955649 348936401 870010280 46631940 985234651 666135970 915004382 348260510 247720074 534250815 524328001 181575745 169300634 19940169 126988257 766648911 166373580 217059069 610806656 855651538 311173837 776006417 671670691 521521584 258773864 557955476 570348909 560871985 195991791 867875469 674085462 304388488 551287468 170296501 651341082 291691398 825910311 814061399 311626359 865350906 119694641 589404274 849328137 334205353 245897545 667164060 885949617 577354847 198071366 385803915 953277515 433454564 806343330 516809723 523412572 902096298 297949472 778669730 336815695 94500776 210393678 254738167 375730877 233202542 277476022 278770696 563528548 821431369 698402446 978054050 240850791 971113147 622961235 52972503 176894642 950897452 160191596 469419264 748401196 567197499 208473466 193989788 506199173 433041423 305133484 187533358 440912740 528105609 321074218 741735645 208423083 420936127 862361674 345529718 522197341 878795124 590883632 148282670 32070749 41000721 830617386 468975985 814403808 697785304 269424867 254486776 445569634 413378355 540431246 245883342 802800569 29417485 498439988 234924441 226411684 405656216 677193313 998441121 362711392 458041737 652357894 201373102 43514448 129162539 802576082 551440173 589325789 603964162 744221591 113794792 214889893 660696027 753937378 198269729 498465385 374035554 730938115 196712948 103450882 310978334 711412966 602531696 291085646 308721262 357776088 188516222 853780635 5419997 899593211 104497380 719592640 639359206 775755880 755871029 484887381 875522328 345834258 271900407 424719801 30061182 579637232 977143835 685906029 330429113 129407855 630643204 314798262 488441856 486041537 946077801 760687422 903359366 51488475 391128939 256642709 173113566 753120707 431115534 148963363 735059765 749807794 585561565 689418980 316796278 783091836 570965415 185070092 916723791 255338338 799136866 730595330 877976394 789123824 957361306 350253197 452822358 977084568 52894170 414974400 521605570 596584742 198627757 73399444 968850333 172801756 881239154 865506549 588094491 310641726 422751428 233612699 728542183 730473117 971417746 373647511 651541952 446479614 675018283 949925506 196614542 597033291 221189632 239968873 182576251 878677624 763536375 467338783 141495381 848488044 173414411 440705101 259542407 589955795 455056769 949858019 944043761 934323897 781326821 971137772 165208870 432573388 641353375 926475011 935335706 606931508 150548512 533121824 876737490 367967346 748031088 789243284 879145299 33815512 327902359 611917914 205203518 950659430 454723136 711205709 340380364 950092366 587754900 176258487 996458602 328519491 246637203 588040514 477183707 248892230 907323884 111149444 851682644 177965436 694112807 822793551 920281003 985600130 366282178 342708327 347719038 810876582 471498215 255850478 816730855 80016764 516997929 465365344 259902637 201890464 148874591 316810585 380129204 67698609 717947183 901442414 45539319 875172907 915566452 131302992 269947654 451033297 973098995 713112043 167881197 859516047 837467190 703248295 817851203 656103004 868411109 12918934 232683794 148812974 354955489 27349063 94218189 829671490 677429265 669119091 586453324 644835368 471813793 191069210 812168608 711742727 776107302 219761239 929021259 780461306 383062469 985027298 402379569 367428586 283034760 288941618 781256262 858986079 520221198 951764655 776628712 393164521 108931031 74037352 952760257 329842350 473977523 49648917 151967966 767556682 390895248 623965366 823266464 402331230 628728433 345505174 109686333 957238008 425467358 783100026 708614745 817471583 718272201 995319226 506379882 248992116 438615835 578737324 884775608 173138407 96881570 495959370 131372566 365536049 687411702 940213284 979997965 699975491 572675777 346360986 534683315 277162736 382090415 817517181 410904367 836046047 440418011 803129894 195682046 163076053 630106005 949779484 697856243 387954817 596265430 200651687 803594425 486861798 773560722 369072522 729796225 332320541 780116966 713255362 429168386 709251859 788019942 719530951 676294006 916173901 677013520 124135413 63540037 618037703 16045983 175655389 523858524 881018798 383200324 144396518 215765319 341586876 826853307 556867818 543700306 428141763 634668274 318414872