1000
337356428 31396952 366696963 49157158 157341733 127551695 994265873 141765859 225549184 503595979 925459475 545561926 142386401 127325016 614751144 348147140 29863860 374518254 233581115 275063041 719955738 647276280 158668754 21857506 829182630 798637728 654835998 69403904 600009685 103246886 171620568 833513601 465711029 445803022 15773178 868885574 609941948 212333271 38930086 322198359 142820314 559687442 922175646 640535743 106954179 135526194 746470081 399099298 417796023 788771343 585125367 863856153 227666635 578119050 334027242 521913050 242702941 661577274 392887503 890578065 597545583 257808352 921611703 960057560 957557946 309063158 489410746 582556236 873122062 484873098 827635721 611032324 433066383 26415357 193790636 707296674 126641826 971838244 397140836 26506482 181627807 510465140 7443941 241384097 803882472 362426752 77385579 736319895 147856307 577757818 995893841 379661900 368669339 812667202 85457182 623158458 876852053 818418869 589130841 996890691 90748661 103345052 812076748 58587848 691873946 754965130 451475837 483282278 601550164 42605845 342300962 507602326 578261865 952139765 945398902 891030419 935920072 472494684 820402042 159859935 178483603 434508139 883405453 759023686 345840264 142588555 190127181 472961091 757534124 321115581 187264810 167059814 590329718 899767579 95320373 82396399 879730961 700199234 719616234 157127299 668905314 183151543 276046939 729549215 495637357 732288797 496906360 645234240 850101898 555748974 246079594 611577621 586885009 35010228 212656502 931477816 545109643 745502761 284463529 156064259 3130926 24638946 43466488 943170456 535491329 491101327 383035558 945264129 40228933 712161568 747773821 317927995 978464483 192430185 676175618 61403410 252134344 304890259 866976288 440027983 349545854 740169213 447928332 465702145 223445505 575498214 232276694 690878999 340021535 116069716 157502054 450420764 102709581 565102927 352632273 180181946 555833217 247431270 285861023 666396161 166009183 97107351 983300961 32942912 758956996 97972354 44452912 755752571 125764731 856497696 889413781 696110934 416304113 869026084 437797721 265871309 555300328 146781152 356269903 285697445 430090003 412654591 563147876 800322342 149688959 632924148 919083681 635863694 466473586 603960287 50386348 40645803 428096289 533968196 637694186 896873238 989048192 957539823 307012155 831611475 694030923 44342895 576436770 381419337 563321050 422067827 222477879 495383346 252629863 475391382 304422236 666040597 53112489 459442362 3344957 914123119 241426788 202099427 339227397 523350101 107177265 641095776 301252338 819838595 496671497 937211388 625948776 202561048 499666111 552932607 47193209 713270910 400982062 676586692 618860414 108578353 848432220 351382563 170825547 783108947 456564054 232386477 755205455 517060667 404966938 873042463 648833030 335184999 214216977 191033544 196897670 540024852 772723684 900155841 876949699 281530190 870383227 149440791 98328772 687750234 97017144 598289982 281469915 782523387 520989307 809584870 494233550 626299791 608491438 306427184 594351812 127574546 84178163 340436271 374351547 933789302 494203561 90909315 948094898 730954382 782377479 559260028 864977561 927733689 461583254 231629794 124804974 104155093 525161265 168554928 826020890 324149442 57926272 467055907 496187327 673517305 176402144 630121742 931150337 806265144 855563483 601907338 750522294 906136761 586102137 545536319 281751537 876964003 352341793 450184990 340933217 534018698 370848602 472999007 491932636 382081063 868636046 852993508 71763144 703185279 56423584 327916833 775105154 875612228 529246402 406227917 262216842 51946278 439518453 572833305 530055006 710244719 467185585 221638438 836981035 709371008 266315359 940591426 313163668 335597760 15031654 335488915 749137801 152830969 479440876 910377784 364821382 840341205 918566685 214937002 474397946 176288998 678008518 645416248 938048669 241798797 626934411 56085344 917064774 753106603 690240710 599259493 950703948 638779889 144011634 458605141 477430090 211934562 984315842 525209937 791075459 478160616 295432662 55984559 131310722 351582509 716424006 371624174 594276174 493006069 130573264 392103996 888237453 879814245 200767354 791147392 183021542 305551043 971479190 64541993 790960428 731972851 150347696 3665206 89389188 277080410 91043125 100909232 273957126 222531553 327571244 866949947 992071428 433143641 1989521 503619631 217611214 743504319 966890659 546395271 437817771 314220462 344887743 993633872 382995721 954949949 106041221 697437650 159193670 278962925 34646171 398249545 935812031 271288510 626061933 267009287 333424278 454973947 924581588 633605318 748174202 451681301 533935308 588095714 414773384 894869637 355481003 643231378 809642065 89756857 783705564 874547428 50908641 856543824 452837520 713598820 799347607 506273396 192410842 697307890 415448590 74483100 334074362 1481558 23142147 766818594 918685011 923191443 90638389 926823574 380744411 774064025 846097414 637431046 115079801 309389829 664881489 334488221 9787427 914661073 357639747 239155379 660206486 189837685 452727850 400861362 587249859 816902126 527484658 78297006 466094384 881065054 711616198 231308891 594071968 608018624 190742709 688467334 48569315 172279313 948160007 109055547 759979281 488484973 947999375 757925683 905147974 19745581 538210508 427537698 466342091 309424577 221988956 943479002 300809387 537546403 592588475 358516301 372719140 388648922 518377629 480884148 224663989 597179776 994411318 878899003 800665319 770448125 134958813 223192110 572561563 695998138 140783964 741254940 893588918 734411121 570757608 523166568 240810353 842209621 6180991 206488263 127074189 752438131 725354234 977122134 976204218 202649567 587329993 147772701 226592276 921156792 164175053 445260890 74599243 576778012 597346417 36660495 379355878 642997112 672708559 210892135 987845598 11555782 293519612 555019851 155521575 683506466 434480186 829157159 730914285 914617199 979722172 687952013 43951039 846703492 415286161 822443589 165164841 476674801 768458444 447416035 638284591 92109388 316035552 146822450 703145024 906538314 118095696 898093546 774801813 203597271 833209803 96120153 920928743 191867485 945311354 264250728 795822852 958548132 88982029 731420944 976631575 528355341 516257149 600862189 253060857 283466808 558319184 725926746 548451450 428715393 792230581 632276627 798507194 623305958 634343385 547836081 322160693 898485045 231802001 349491645 138235314 275091463 340441691 364642212 121854448 308387018 796467528 619764367 782736265 375023991 181945949 909007489 466148048 266527820 721292659 272424957 586224299 551564148 664150958 446552202 268490944 490678075 331825928 43260799 773068707 32813305 485205997 794968977 274141465 975480112 710275602 397835389 308996715 277440925 314049613 398183784 271966467 502685561 102514148 744882299 273191912 995907944 681044277 340302137 310069508 616658848 252298522 517657811 78549108 684233388 810273256 285096361 637024732 603403530 870922309 611840096 342986705 544932934 312817340 291690327 74445215 645699917 509868161 535534004 886985479 642473387 908755714 201668033 716572374 786446675 250403955 298768297 867797162 203221266 952173728 39793771 31524453 770912625 412186617 400399102 107718925 102691812 807524330 826646277 370135614 190306218 770326411 58493909 512010598 996358521 130876313 445597125 852438563 909929227 442832189 234456940 714730333 45459725 25586714 216148783 52758704 521552539 865263792 156097884 748167562 350518590 456942096 828957841 638597515 883867410 883320750 585512720 892666098 133167415 338749642 335296318 647284294 270128758 594398604 484505512 64688388 335839338 633624563 574126756 40568087 267585309 729491408 771511633 943697052 767064371 893171839 636402338 492859980 435518927 51621535 207579866 164079698 295449419 671889355 946013521 338824502 979089944 675658928 537623327 131915976 929199905 918584760 832774392 813612038 320002975 312567947 816237866 285620189 480362236 491507334 129839673 818887128 277497724 212872758 50330111 356526690 283899099 680238083 654337454 168478217 822490715 744367275 90425752 44722480 387675703 745461201 397756767 488938899 238276209 430618704 793063347 890110134 894539699 890968692 628640510 760976860 104450993 902156398 738752505 161538240 860214331 727873116 164986396 82146364 738055099 92568087 979347552 689977588 349528737 703411692 717450592 383039759 1854065 112045010 723713277 349804728 655453015 115666710 774097223 647958640 344923168 986112189 901939844 458898196 202834553 964752673 388609375 902533723 279445585 598650996 283933406 513946248 190633770 156149736 229614533 836875305 463209897 540763387 385219859 132865844 343447688 177042098 844701284 459696482 780828746 669032739 883906052 604270919 12094508 494650275 134250156 347216885 397434907 205743142 580255829 914892987 687540805 177695447 86044892 566149689 980937384 997321575 847347592 325982874 759620284 317102165 636926573 272904881 415397707 482083963 58780932 278098330 721070201 704055259 96817680 710238925 143617970 900453014 981538369 65967242 234886522 90078296 868594130 752346289 464661422 187880142 928772280 779734912 432572190 956042629 556246333 78384455 823451604 195745021 704439679 119978456 479866846 515474796 435591036 198355514 867048294 558808943 761511409 822294542 275580088 419368218 437052306 126069569 108579174 494699185 236184129 291432281 584881215 63849085 705998406 475151280 502842009 223778522 608569423 120604001 330261364 767856102 30411216 736595720 592560610 498582272 675226623 801957241 6613102 640506976 934310648 463809796 419155759 898109287 542341335 851303814 591521859 602347760 437589285 6730289 980335290 159818123 784888565 376231226 678925456 147795676 648793918 105604972 356193799 442995500 697919149 735958813 20810352 682752697 461294012 539581516 13321341 270219880 742415151 904865646 582260984 154139898 300046391
970805900 499517179 253231548 868258434 51535381 203305831 147388565 139016650 630404283 960442894 441386216 273402770 763158728 645493005 110272266 948901188 856187364 66431062 340445226 795515741 888975335 248709910 744371196 447282434 971961205 194348931 911404616 475119946 312556944 632944369 707237872 795050508 697992041 720384459 14522192 853530843 757249563 907879432 404479775 486286576 977507951 481933052 181662210 930570635 227553565 89611283 119507756 189539854 8634290 498963520 361508689 660312344 845819424 353566855 931540269 362608228 554753414 706042696 44940969 782666287 679751885 715242331 718433018 801870024 421602841 474335245 404705236 15740526 677854797 666378536 520215544 410411977 437594093 462709865 805424999 815346335 35434997 342223918 870420168 415615071 826309784 8605089 499665792 167062297 875199670 577085671 739049784 354443316 6900963 712834726 674033068 954254579 495864523 563805731 124304442 110712189 370870055 907168387 275695867 818794703 953618468 853829552 500371601 38966747 857274247 271116472 190755179 571898226 662659356 842819840 747509448 525775464 639693407 11406925 683630131 104976551 588747321 917499665 645643877 183526248 189140935 32213151 478678301 772853119 172517782 102182490 435937329 24563318 795783815 379480568 457222579 918786321 807726533 649463276 460033824 830391116 729293591 593780278 436419927 753389919 847321931 336531190 713980011 964375421 664056424 527591456 404929343 103671710 509554077 508280592 517564255 404333203 656354019 646996326 876617464 118094578 71101715 825925225 667116418 222787832 524724561 455147946 352068681 569750737 835264586 815304334 141919295 857460601 108477817 984860061 676179317 890020984 971121185 420951837 182103801 290765226 943151613 685276906 708407103 894883972 993781941 899408383 655825589 755182729 825602555 818466236 716017661 161098723 506731036 983236977 217717532 91779403 528658020 612103775 988748352 505484379 330938662 655182153 525368833 369427249 365912987 28007689 150134778 732257623 265669410 536275618 511063142 730196845 801907936 651099830 655614425 7846739 663300119 272569252 292804048 179536859 985906016 667378368 831332043 97960986 304208768 823771372 329196380 951647328 37798764 798262282 322344164 331553906 746341506 591788350 527386378 912028622 689953804 944932356 634535117 83037413 727928056 300651090 113043582 53867442 207737707 658883967 693716620 100065882 22693372 522279412 572287589 677046501 905405936 123888108 108554275 760092468 134246016 751072222 805859807 94034075 168284275 937374871 862968584 791752709 66942116 340969452 511912656 401949839 201475764 651717383 966032163 725580578 22206794 347689341 454591265 851286101 946497997 409591495 98974706 984859785 60662959 459285650 937252426 713028376 179300713 607071041 714440016 571438584 663415446 768257673 664245639 886624534 679371919 162139741 515311099 545097399 871966526 883647046 511676713 892774238 39069529 669266808 873349035 113552817 723817030 803286241 38455338 696022423 582651719 485620358 249742685 382498075 376869172 906770948 714282259 3638784 673905808 134010317 132558538 81191486 886781265 110281509 509171009 30649300 47228066 480361326 828568005 30369177 976249531 643213904 229411015 132020361 330997116 21879387 551323909 621100535 484641885 671481225 274776935 124540146 355104146 862254681 150505370 236530645 81921837 103961893 270017027 926532020 391105207 542720115 114702035 215648279 344162040 799943895 897979255 658756975 594379580 350173980 563940364 247392175 99047105 168850792 977456712 494094181 858837152 835967410 779730650 610033720 764325776 579517907 398385504 696237800 591421886 248928873 876394350 805079362 174924499 589343331 950041699 845984507 565467327 823686011 990545070 843695006 122948588 403453830 383643546 736013964 256960378 530956754 989255362 154794796 298328844 782469979 807807201 870340611 647373168 186311120 385514651 208460306 927952007 961714267 125979196 667573851 925466667 342662932 771487990 916074287 46871730 239961766 317864537 592555635 593706453 984195274 427682103 335511071 480814981 508089170 341892304 921862798 941093723 735654917 229011011 294688941 850062378 790645990 395620760 619507303 63736906 535850426 827524547 789906510 598595908 554412484 389727093 406723397 299010778 497298073 386769123 496822112 845054951 326881805 431840174 426952076 530489169 811208462 896085260 419225535 415821653 172827332 486240001 64495768 885059325 743170223 882457516 966492252 520426075 560286182 480223530 807995205 263260350 513194604 941373967 435025204 296602121 193690121 339903485 915863034 758247173 105315728 474164679 324986016 5185276 843880926 330641209 532639521 651728417 325047149 434752198 584156445 513028854 251326489 509729821 563586575 542357778 711096909 301216743 181787577 43991497 725864756 146870466 345559663 390902956 535834751 427152219 7191945 742086667 367405074 879171062 173579283 42437627 395050961 614471124 343188507 394518907 639551192 123617427 454339944 273885490 871564719 209492702 490965948 125367673 881513174 761991540 998650516 628292170 654421262 468987843 962134209 936625012 775617076 54005740 20576389 96755603 925531744 73588358 195499989 652310485 521830305 665755152 368169540 53833967 171938604 934715392 472168820 7717046 868770926 463811096 484498700 85877409 616541838 239845132 302909887 671080256 859885799 396163593 787156623 81026412 84205814 867831790 809505264 180156466 11084705 84885394 499262321 263960288 272480311 633546538 162501389 422186467 437039762 981050224 99093002 150726629 310343947 558618457 973339119 344951499 443232762 841416328 938034893 118063302 994115283 223649007 874983406 433788945 83421803 644099466 372956101 92418219 372226029 840838403 933034537 214144491 398315431 522429087 900568928 983699338 176840271 909093286 301439780 853255028 59772137 160162988 256795035 418025969 956046241 319890054 886716661 978691777 211693851 96219807 720566055 691764363 671419965 998153148 950903903 255959864 738839352 432747097 815866028 144462351 279449637 712720773 380203187 375415906 958603231 889160848 406110376 499015936 370767678 169011245 210645362 814555873 171394901 605014044 619281802 894609604 198860807 227872978 557030245 894818425 245502860 781211632 953958594 172144843 472616667 263928856 667925295 774219355 518244954 789946565 184257510 933992307 650900333 637004207 13360562 489386175 104695577 56254112 479092438 924213897 857543700 550133224 687344084 56116252 153403093 17511465 378317670 17788213 604938990 226652354 322132965 349318672 668179192 638771705 653043856 585654327 773044454 940880923 440243802 779144020 421119711 230675282 787853116 548505376 319167261 656203720 260308132 708787344 583158038 526631936 735561034 775645683 977343939 874088191 844229028 46084369 821725377 487206207 446837852 426518422 67978240 935643488 258657193 657700525 974792413 50560880 319055572 165431639 238813110 541931832 934907446 660330118 400452838 735781273 177828390 99350759 417814562 636607798 416241493 469314494 705079043 227578135 302662837 889783467 850823075 379371979 132059527 23357874 386339842 705216676 284779877 266124624 430211412 452836039 284123124 726028805 771621621 977214875 170911178 926180289 902488540 539918531 706897306 141127765 922684520 943729131 723888768 578454431 570461173 65638808 551731410 149348979 454710020 733744337 460955020 301424560 29436725 348780518 566318703 820800827 895790576 514516280 901512572 165911893 373595951 221240812 451676044 420121883 206805963 159674084 478737400 831053830 658496207 235811852 403895932 352826141 374580664 899689565 646556691 472674073 772682246 766280250 921897668 197048845 265819124 862986302 171261884 35658322 863546138 942724395 649814585 206003398 619024122 74950350 535144897 472144010 376955752 823991713 451881276 390764721 793734166 724107376 151020261 130079703 672704437 190364613 601194924 758847467 563662331 488368205 80424864 339402745 888097889 677029529 668321684 475926178 600395949 749661005 436452104 145759000 506363595 868036381 112424255 726184703 973949317 971385828 292370525 377177736 959803525 804395352 511865332 81458111 895327889 909145308 358678059 265697626 577461587 989424408 356303088 14796295 911095621 886418933 114047833 154484620 733268106 979716622 818679764 704167080 394682988 830966316 594613076 931564377 571838385 458444784 905813145 177889321 332507513 656759770 518425325 380437789 235939083 360152307 924256076 256749054 938295192 971237993 667047461 382742096 430372120 72072992 649989965 48632980 604212919 795354633 691380745 22038099 762289472 907203525 884787152 280157259 366000153 73890299 91434715 105304404 450342721 999049023 95317728 614051034 867510220 679537303 836890687 289138347 666595212 558315566 278262856 382124221 91570786 739057922 193227444 319725133 456267059 773180174 330418916 390520717 610581124 542303135 599936490 696060160 608239294 253436007 138393321 622273320 815153277 565155606 639341358 156590295 856538800 281983206 149874846 989463508 220021532 379772638 923460889 268913660 224440543 369284440 110373890 843974580 289721292 839476806 191798050 811150589 771294935 864893296 232281261 410804600 236276728 758362568 953155881 808306457 317573361 564920805 841118273 232178711 316582854 16754768 108885177 319414943 844639178 454952464 792640202 463879613 541786964 769614189 877937844 91034600 570275803 931174735 762604183 975187932 422860471 575359301 684934965 269184829 872258156 154931197 534425497 638247967 899783754 15719902 121529508 338386810 130287665 91386646 902421597 344036147 513192570 436439547 721134529 867132820 209963342 436664861 743512919 573948524 242676797 831954817 171647950 972457624 441384770 273867148 767086740 487132061 618223105 17272201 941111280 678189902 824150516 971955170 646389513 429853252 949108608 62762489 748382391 704805113 630793318 415044098 414286696 22737940 815808255 939537297 281318574
