1000 129
28138734 766816771 356994217 973457465 773609434 770200289 33372802 916603214 879958446 310111895 672563418 374127296 237147555 57161774 436394013 57457785 29070505 952929228 70519618 215675639 550269450 226559731 226937366 268439906 178959381 310069501 946410533 493829910 652940416 403226482 43285599 51302049 296266068 291616654 182952916 474687505 958208825 836229824 306241531 976348139 608709910 129042191 519817292 306968320 907110767 42464885 5015472 174379846 325989346 719562038 174381542 822047631 781770046 75115852 389060162 734647219 836988693 420624248 528172584 398282807 950006566 986571801 442506033 366542680 350135173 100485494 736497514 187261969 183329505 626803191 640684855 734344683 59552847 614251099 725572494 756063255 774186113 502133863 132036638 634050369 883485527 2617306 90815782 23796917 745340666 334773518 914915568 267376126 645119435 412625922 567139858 519718901 719854730 189866411 221582799 879239632 301889368 439849384 833517319 491199273 90496009 87365166 587339074 247060347 885478593 793393780 82014903 487101668 170016495 257297452 103496734 86003944 106535806 831168202 802417752 814025916 625655662 408721568 223690514 176387047 430777676 453197584 576734526 286854539 698553972 508854282 358587549 419310505 359637573 550343448 391788958 645017093 162564046 252658958 41962781 435118103 620173783 541297865 460078422 156157274 282966287 442980700 448421957 325098207 94903709 757494942 386002059 367074659 617858811 198444906 931140915 218571090 498288676 392211734 245551640 524289348 444782195 514475941 214965632 444279594 908022245 704549051 930779368 410210404 52367958 131068239 747412716 145645309 439211066 674067669 825579998 637893235 590251304 698600208 312504806 197278144 25534930 425964779 880158528 194470040 594645386 308383485 298070471 232013885 114719180 30325316 554974321 481919888 701251386 479254212 621095108 387466410 16542253 97475017 890341987 468510990 435129915 573036475 72205388 280718718 711222541 962418670 472355484 341841720 385407021 117436437 552023940 211235878 326765694 908554242 238315289 509272885 907672299 996653720 804571339 979007360 332956314 503323442 290320207 635803243 755803006 356270610 772262294 781328860 6085294 503891592 851193662 564536732 447018953 657695760 96748737 591916170 620713477 325059288 320785169 247391705 929085342 175081428 803795603 773992027 167945170 171152971 773588106 479272946 253262012 329786262 287603461 302423302 983830196 237815621 114944762 19117152 744607316 466303362 745018015 226437297 209409686 732791990 882331308 997234296 89104364 627554954 716863017 569717026 340860 786600753 710882007 56309683 618550458 414639172 378927681 365999449 650063220 997188785 666395573 698674029 612234124 707682645 201563834 375605767 307891361 821513390 874476973 352022008 835516387 43715235 336503765 331247836 988451968 353526017 946911458 737416010 712251423 891427275 205915809 548838184 231418155 169524138 477110549 21340678 74838324 766841354 898071716 544933191 408223691 523754560 357040866 680886055 453344307 323432428 922926764 890227533 910957145 115335561 256477381 201294582 549069716 810126562 432668338 818301135 45918425 40363454 524575716 603979674 767555156 687765136 772832106 179827990 733952843 402726441 203411347 639877264 73208466 73473926 169047873 556352834 9914939 444101144 755786464 378941159 204566190 272821096 435439431 755881338 92611301 646210842 538374021 583165854 408442298 760085960 273131239 64371445 950026786 228133742 310416797 454694586 669672435 524841968 963777719 550872793 697986444 512410835 687387196 376957992 783389485 39613490 649937666 866512131 409155083 348299933 233989593 611127384 956674969 630999194 645730828 705367904 6972963 586014795 375987574 702546092 41192096 875959636 857271900 983468955 220763414 758193846 539107151 749768012 200628583 891120791 638376307 565259068 651882275 832779765 764767844 719912343 525799885 642413070 832552942 974238848 761918892 257060 516758717 512961188 852365885 557300846 122710795 202772472 140246526 603327249 989882225 228492727 130787456 291515926 630684316 972409281 639012403 502404374 387077559 121203501 435651806 811846477 517018389 84564384 476719054 736673161 630426756 301949587 63522247 845574399 229556973 109155866 566873360 494636390 562624729 72823421 241547305 861585113 92965602 933933718 209551484 707981961 529649526 865326178 382113579 158272495 295815993 456279616 48431692 578663313 52636048 963692751 812672359 590716086 549794981 445928809 933394129 918666614 245712263 684042927 138838374 923772454 30055023 68626557 593496780 79659593 593544453 841291961 215212371 827610320 408604051 131362401 119733266 561730864 147468428 322924630 631145502 295066039 315514952 156080519 302200118 347861864 600071276 838906738 246679622 875667739 16031485 591700722 305512514 412715314 874002809 145580438 875734834 148562595 918643249 963272350 193278269 891844559 669845524 958251030 492204596 539499020 263168647 988475447 643697720 696322095 610021077 708847540 144838678 893989056 760971495 764084355 910641234 741281045 308988593 66015936 99171184 810436176 363497549 221341128 849120126 673481895 462270064 966068392 763922121 732909009 585370421 614937060 975760207 152396524 557090064 279372324 782689973 842510139 384705582 954878853 449094677 289276928 270279611 364473305 253656198 544291796 553028592 228120077 671207042 643824461 35777626 154470197 39140727 192514412 27843280 763077388 533200321 157519646 583223757 493512865 549120102 844098860 484005604 450270068 560512038 23925236 301002701 137454622 914384596 308626617 850937570 417899800 500778072 27127527 611559765 999896410 609763695 877294968 240842294 273677395 159422393 317889220 889945616 974131754 391395301 210110493 908753734 721998117 693429083 303765389 731630879 523328876 182676071 921889826 887718530 137438436 793953819 517564862 58480826 829349037 899585127 33556034 545394936 782853144 696583181 825841028 826425384 559201175 230328084 458798261 343271045 806057552 806742036 607708466 371215347 541364238 653945803 474934667 818789723 780512276 774809341 563789943 604712454 69115725 924346689 625688533 297850966 35626037 428593257 297877429 772687900 137179098 761892830 176730723 659608282 499037114 125586849 182076898 578462004 586441833 965901105 104546875 263922864 985889649 68972895 596079060 14767379 584773509 603436693 443409963 52146446 437137933 925108770 679810974 884183978 68260745 901208832 407642787 648244766 497932189 31026047 371664644 561843579 857977554 77520950 451817621 82140959 877528828 55687817 864569875 121444122 736823106 528835701 138398184 566874393 34798559 776875561 301959249 783241236 500379165 298220797 698657536 444632142 447870244 508564787 866155701 5266001 361138853 877290357 195522220 497961752 36200008 579119215 717223956 231872484 518183036 776039202 691515020 361410179 495846645 684331887 229504583 515812933 709675449 844288379 241749379 531678204 494211565 843615482 823217481 329778595 870003011 350086275 411507956 708477207 306053117 691556344 59280873 111193592 893615631 308979582 765079652 128699282 399302236 233264821 432949792 372070531 73230406 980280013 812017241 371218746 587735973 447119967 577060998 76399286 715619539 371246542 853007645 302649771 4565594 365974356 102894432 118529438 567341073 656899533 386028814 77674997 177555432 696256774 873000241 235939114 955963658 696828123 157144755 448505470 852936360 960432622 236431605 389808784 966683795 817913313 959054357 939172396 568537568 37341556 705964993 599646891 697115616 259861944 662368216 234235405 647012241 511488839 252756195 940798727 567012275 61924672 746987696 959136627 952886445 806592937 272523400 900207907 754509446 50356938 200083880 300734217 989938073 122227831 422201874 401547223 738648428 173551809 220563899 69136906 567535859 646967034 750532406 533995587 751399125 881954027 702911501 156040601 316970463 347876737 436241991 582724710 126671108 80969623 549896152 892253114 417249255 965924435 28918809 538183538 213236572 827911044 124089774 491684028 84513084 95666650 36676769 401920771 541056969 525550234 821014550 732332177 806796483 135278726 42014783 440230662 187584392 695651899 112664385 632887699 256875289 84036875 287804920 336436864 182282656 47849067 699201471 149617265 396107745 209026154 53250801 415183355 413848359 500840750 818157510 822880533 277395977 777701318 382058875 499964375 45883456 309455828 64904928 132885969 892708787 883373488 40426819 456280476 558397668 618468997 50150651 695483176 959188576 744937137 141418747 823410481 108942826 490569013 885871876 433248225 275843584 752909223 388445306 361349989 811164144 54586951 512074352 815945292 463383351 653180245 733254189 459105591 786508712 980293729 225008901 676197062 679390917 133924728 964116197 350773720 911748921 534994593 451108409 792381282 112450863 852352907 468188342 591308910 732127037 77284504 275943632 374959940 89204486 338055983 937444703 880185086 148938896 153537969 82838574 263527897 532455957 47284186 384838545 465898164 876920899 161441949 348653070 976524715 267848897 431432749 747691095 905908555 66863424 202604231 878895040 571584727 872003575 741089057 890396988 794794331 812193455 665525171 687532452 999019867 93666323 716292196 435139189 611760716 175583799 874793382 649249178 718217829 278401473 130311147 959391829 769009860 914907499 150670403 274153983 148673785 118162229 290459996 801420294 746578334 497660924 584311585 915501227 346049558 973764548 800964848 626553768 94043854 944558338 297239008 968577478 848251417 967575216 362405527 16180229 326257346 109299793 535130235 11924548 908581378 331409107 962089517 331007065 79278613 562047997 948469760 962064514 960775211 689835106 349370980 432766278 18078662 501524877 352813384 108991443 770460290 785632454 122517548 633700567 244727394 369260621 119606664 613794977 34164043 921508677