1000 1000
264704197 120999146 136987924 40280999 438515315 805152546 234164454 129099933 971852321 983937488 410134225 668461222 574343409 885417013 394300887 86086437 570981511 221329455 57893312 584381871 154204049 738660729 728257729 551666498 540440394 165573287 512342480 452470821 669622703 340240729 965382636 953292241 144902419 86035524 289571086 987645468 423893886 928104871 464748969 105872436 123582647 242780928 505538017 199537013 745991283 983136444 65304379 842202106 646596193 140145001 630412665 134706415 170189559 917006962 498351627 78228861 784928508 545206283 276287905 127534371 580361498 602636875 833497706 569752320 168745739 687931378 25556222 401296664 903079778 244718550 696658577 923575834 20801451 728508574 144327567 355924229 987918030 767675763 39770237 690017157 35094958 619519152 803294929 322191158 334280933 412368057 946079172 696252934 727024412 429649275 739609644 879769415 84017875 429336930 578822041 559811577 192014409 783587083 235524450 277645214 641105035 776026757 478219070 115129181 14794716 647713890 894892898 720571222 16609338 29190516 796633468 940732244 641040997 243193942 968755343 956678858 9273458 747543114 522400393 605708171 235611799 713122606 952769734 230441676 782661943 119932537 618863044 263420409 832590609 341598454 889752736 346283651 906815307 693782514 787563199 656787150 558988762 325699987 408388854 484659329 514686813 546683978 168335178 925036722 876453250 928472013 452720553 11844689 152089336 237462880 322160445 768682370 968998501 643437693 43682975 50514865 225072892 729100215 432384534 267319887 944916772 470850912 634063725 30265497 170224154 233237753 310521575 363661868 30383316 169764888 450267291 509435980 637917173 871736242 398793145 910647926 108164902 535373865 729080956 796833592 454223174 403988143 945062274 621479206 158107041 272551814 767759721 136585361 638455939 61417522 286340474 221735821 57584824 684185411 747165460 140519367 201499817 652532397 746971523 597836965 403721689 956715523 163056092 661594742 716321675 768003151 590039320 568646343 716350006 451084111 528630621 313480942 118564698 359276034 829011041 701887370 725160671 666415978 738132895 114167505 659739773 31924187 55285186 560410488 920735596 860283017 130521101 634454758 758692855 367621879 37543666 929265562 700477795 673784691 852411165 71823458 547390766 338428922 269296694 866684149 689572434 918907490 292588975 817571123 959281983 237458599 110596904 240580147 243465869 754150540 417951469 281530082 3734782 837883412 802111064 342905930 634546070 489807159 227640803 152130560 715231872 928498199 246388488 150318222 849120860 925374177 144892127 398434867 729447157 621850442 452366143 469546842 539193693 387659516 713639740 534692970 516992535 857296504 338125822 866018073 835065313 510544637 841323884 623928018 263447616 97154821 157189035 626682906 850977848 865147377 547354125 291373786 244996624 939186671 470490191 110958524 736419272 379219571 498680309 361856442 100482924 442510270 773429065 207078157 857344783 659400969 841728390 692474075 187583662 175274604 203919131 521450008 542450577 561050789 483834181 666635165 281236448 744939400 606001978 339209101 825332344 409340060 105053325 334942889 701010888 52772808 89618199 62382450 312651094 267282041 738280309 813796994 153189966 976016018 645498866 305360396 624826185 89137985 804282524 278984850 215551309 168847257 594398943 553423322 316656379 938695783 362188486 979254770 615808805 280079020 162058869 734380867 181183810 369453245 10097001 370504521 99611572 71283549 375804845 690139394 298702528 556804228 57525845 328898093 541889825 375688946 127439949 637860162 88758221 860742112 825399220 195532272 296560866 898263825 226507934 152656046 744845166 27581792 599790352 363219948 766909962 542625171 231657310 545144535 908129469 857808700 828842600 58937965 640541108 137921815 28350886 652508654 643869973 722021608 678993723 841257574 133264624 93113222 542874973 243438394 898920791 87870405 571326178 595882116 80857922 669576241 881037234 751107032 508469231 307671666 507999415 520756793 745631224 52014388 230352221 525650738 660315722 503767010 204996751 276291221 664210989 151320875 599909211 925460171 408720654 240375863 829642972 167269687 511882951 651482680 361674598 595158462 843234786 901936204 785745600 501130119 423181627 966641925 366621967 608618061 936072922 771638072 796521561 282814428 707172910 649949343 222508649 870914963 453849073 301814340 446156727 275123659 405340166 639133553 908796254 624069800 989896706 739052214 367907666 419326829 798705655 949998257 404075252 381212131 844178042 667444605 85885665 866208268 221166146 963673720 431514130 572154241 589291507 484046818 76028159 331125923 943448847 963269306 950314008 454860215 671912499 631376617 421669677 686364693 493511239 243776850 33178914 771394023 705494253 780656564 950203751 401551808 911153562 222352670 713096228 4873554 522951161 898293860 876305539 713583463 169501973 692354474 590425869 138797942 423932057 89855279 953274951 36055194 583694890 284557380 125583279 109265482 517158975 679505068 899086402 30153826 152428854 400940805 814102622 387312147 863423383 522109047 930181370 411641248 441522916 638436687 157747928 462976946 602205583 324007774 608422754 241156717 927009838 525235777 26330288 350816998 324804570 64281672 458859964 757421184 484881735 231860715 741853637 100094374 413476035 861509035 466379692 737395667 473100877 485500327 883936894 566698676 853582737 771426223 335434231 892162908 637795835 374816020 216075739 255716655 839738025 818202475 636086218 292502906 760752795 323432900 319170370 627815219 116770363 270748787 848522386 566176918 269382538 760197523 716607965 269854968 452119349 216095588 551878799 561995103 605114428 347367663 585069043 796207312 976644436 168236723 526468099 39759609 169964459 665264332 85791246 322395252 811953378 920480819 73868602 901430342 642875472 819534976 497343164 142912010 159574371 817081938 260807988 569032646 461284519 931522758 357440133 92109771 695786347 988662715 997640683 88222446 901367480 731742988 163841780 795671284 106337837 806399633 527279853 85692509 825600827 187824050 978085038 662394583 493339852 956562731 339381673 526029630 893915970 145225888 807361520 843153344 237366813 493349993 584803239 594170986 919760600 109872641 162436711 479524148 339756055 612937461 118527668 98267328 610994557 89281857 974945370 695401048 488129989 515133051 652937312 917441227 877139 82935094 369633655 948184250 720802111 364262472 537818844 418022911 244117671 184035561 902811118 654967618 916469760 642095996 634175117 537000401 384222483 441025849 754252108 675523106 32679843 818238629 282410430 47210910 316296338 827369309 740322912 858165232 7145962 834245142 355398069 447978048 322237571 280944444 129467789 533468369 896433231 245263616 269187614 653873631 804440053 301129599 224523527 859394320 625589344 151351159 485191725 34390845 720556424 552205755 302378597 558013827 702629473 596451847 589022172 635637210 166517029 880745027 229409044 663049001 485274459 244268086 135905818 523871556 712303460 234812541 875650875 400756756 940668164 520949196 119219626 375497475 770641585 893349700 810194255 206506864 518646675 94307197 284576740 839760004 944915557 426487833 651422108 245042497 588680664 112770657 54022602 253354221 890134815 540428524 563498599 286157085 765106037 766458105 830410082 156562027 526645190 830082524 224135858 975930688 151352644 730750936 891331027 393297837 424882569 183509738 935502917 236199293 961675598 210839789 724016131 163052826 12296602 783841626 498039791 72802301 186391175 532449389 213899035 848004693 530340286 5263801 204683471 395997628 488334502 616630150 269207415 693423687 281726246 20506370 54478886 507281136 160954027 734642588 690886710 963151748 554242922 969184968 734914985 834765732 790446548 418129336 669525757 769724940 653214462 340192294 446159633 818417818 541094465 50958912 318296181 69311348 723009320 18516670 406755068 326864968 390541367 407070587 121389775 685191434 280341374 108644580 375423282 227166411 938363350 750969264 374953701 492206462 481127343 729265460 953031114 854789452 237031361 955067289 866248813 228444667 649244495 324406271 120797077 314646544 58959399 3288366 854622117 468356745 979235013 661217923 520611197 686358881 517707400 338566459 58201392 815107772 907610260 767597128 499736218 545302930 627063788 460040357 184461369 606809522 728341852 668869817 577081132 222858265 591152692 879521451 403609733 818954775 373903993 993650663 67520448 295570354 99912702 862739997 395323616 677553429 52838932 40899335 74571117 987025786 980274186 972506541 274079910 688510330 857273476 67448884 946779393 59277318 994160143 742529501 981347101 343974824 696929226 335495729 610436273 714037097 57759471 388800742 589706421 973148751 250362369 835072764 745491860 446644573 679685394 366181981 920499234 641446830 637634625 917033537 350931057 376037334 429588715 227044621 774188754 428291718 883994450 138116461 365355333 881966517 720462542 891208039 897541378 792786923 740165942 736566640 308601023 720142076 316224772 518309911 968134725 516682261 194774701 375083203 581689790 172010851 974083704 139773573 46131932 614258835 451778839 85044254 54841683 371155842 32688198 227359267 627867173 218086483 259886832 87690949 552123679 790431707 365164248 993199867 214438533 525514196 717361563 275267118 498031960 922279250 640263313 55184923 853033845 892457772 840592168 1497454 939173026 200095662 386617574 250518793 905424128 291020254 318554790 182317674 868171036 759958543 743402101 964108290 272590670 145210301 558711506 6431291 576740159 346371626 708335123 108782814 886683076 639620797 635280149 495628851 708843881 925044897 751828618 361829421 307252380 296901157 277039009 806187232 966648629 827868799 435384030 946003994 230111596 254914868 825033134 500859488 180162076 0
920210341 260278945 365764956 488480807 345594555 468285234 624776852 303886936 611534100 579438333 656556351 483966138 265187640 107309654 428717427 198663185 157908235 442044028 640996606 436201726 193439789 190420492 261241586 665487283 534264383 957831147 301089289 11767269 791758022 583708953 460867723 414240861 67023643 983581695 276760071 500438783 234987801 108274186 130434554 545097741 390697210 365340919 145063248 498558262 282226328 239181386 296809897 904454862 127684268 41286107 674661093 291235376 320030778 184913596 92560479 952676999 55253119 180546445 30812789 554302058 695132519 517189915 703388469 974859180 117868168 270053958 896327490 376709502 673632190 767149833 881704834 964880104 302535903 602001468 546861009 97060264 671912025 148983304 344455096 411219983 53355848 906949892 653950149 722415925 511757107 374955009 463044908 59330876 192234027 159152727 172889411 299328356 294774001 285003714 515236887 163104722 932018058 50222750 333718353 896048300 599823310 192971476 229094308 271233381 987654110 312395025 663010848 656290079 992357741 513466248 402349816 663823780 261409511 586869300 369789943 902069349 14172062 753661660 95943082 571827529 617837612 647268509 830257029 890038098 169851886 565844725 776190216 598197634 503245086 625559816 547964489 272209697 138529390 513923574 654534785 205615967 943138496 658568557 630241852 437709671 18347837 764150335 345049736 764563407 562873877 924757857 767271797 264847882 208590218 695763092 486722998 753780893 411412053 683615559 654504861 495572504 863462759 81649353 156360972 656212310 344347487 522532087 674322957 772754401 382504813 283637444 113056838 818598886 161653117 403319679 472162214 482206539 819855435 965366074 270305618 568219033 784120490 765660275 766570706 164475300 355126344 699482278 495447045 444955096 489464749 219112219 65713591 838097133 251937582 322001531 256848551 188960288 767550036 272345340 479200957 87352390 99012961 445287289 168314448 275664509 563514901 167159908 779883195 346397947 392992668 25760189 702020838 30079278 192996196 631509811 272423795 815534631 210025365 491905563 584976434 936207830 123234176 654588759 460569576 107590098 269179541 547297558 574313044 925044428 784355441 679223879 923769665 568020502 365573722 354787353 675678625 51127089 57523374 694331547 375671543 462603446 186200699 242959815 477423230 676517257 783662211 680333413 292201635 276548710 926598897 374772176 345015913 359835451 484644311 514191513 75812147 106726487 792961294 986069221 811470504 326844789 483541822 167890485 878580049 728115681 630441652 323511842 405749267 889386649 70867570 828112442 987828243 881979169 734115513 986794047 415836684 608512906 225712447 920571729 778530011 40036682 443105047 641823414 119124429 982571066 221325391 163891898 793163035 805231750 97992718 293525566 39546955 571072741 776098692 407240324 488427067 649107179 316884442 945783492 444543766 24383556 648574126 577182746 397938019 842501265 368297355 222133398 727082060 603229813 233905817 126624795 741115301 686285480 849230288 792349797 74151035 319412349 760025767 431058587 402283708 989951581 951623217 942880054 7787522 96318278 141797036 824698886 284610016 324189710 201229468 287270550 77076299 579587745 11806335 202688136 909091606 446724464 346389051 875774799 506786030 555523731 343186917 458821880 737177059 508439840 388173401 537904214 697289446 140344383 321567162 167271824 739604997 704612620 559705514 560600261 816650958 119129315 315716520 315098105 429778464 309576236 719226127 111911609 890698203 293353875 605073599 724820109 182903306 651402209 634001180 886580303 993429671 83052065 890423862 921250461 273032776 81049760 797700534 960899906 580958888 774143041 547283135 755976733 432350378 52630965 412219035 785236117 725905096 17940348 319555704 397193188 406578863 964729909 264285397 243856996 398903836 138192750 775798178 952040907 139766927 42555255 983120980 354637607 822016968 715987073 123236486 723820453 749169788 815937448 578290717 654556320 153256330 305417025 491086025 52147732 842087012 659078479 738686662 324940706 196853892 844563438 421152620 727595757 532781024 676989925 337918799 38453609 921667613 939183211 509076112 267396961 926756361 383999439 565923289 778615180 301446091 253506461 586064396 12390763 631001458 817994465 127418462 948760710 961866289 376861418 344868689 700995628 837948064 530851682 670096313 921140174 467511046 303845907 363435738 803126080 414153414 206085347 606879792 873465775 202584227 751458982 572167891 907604234 627825851 403751021 603757491 582561767 538929085 532514767 918832442 273793674 439545813 208706984 650308057 784517284 63499080 259686246 889404673 38090460 745132770 235645616 134235085 551615214 614422193 113289856 110144583 189393771 222851359 404385813 17742111 167061525 290312090 717898759 115758646 98534195 761939082 141885121 775404672 108358750 447055924 461909077 490104749 929540101 890571488 391884765 711111526 652668063 678065313 994928440 646336495 464605337 609375769 504389061 661507256 110207769 929363722 963643910 724816031 638043775 542264669 634463236 848811704 170548120 260099213 675805453 14597411 413462606 191777371 152629222 778401429 435531976 848079839 431864925 524711881 654388006 378722728 842459397 674004065 477003614 582311124 130496785 409301425 855179348 898250815 27643657 768502103 170437508 835244956 140741261 282874134 357330746 296842355 887401070 676944985 836878078 682266768 906940953 317727664 305555510 385229877 410794445 413596785 371349392 312595583 525802823 351488546 581842461 193108793 513172959 742969097 197479318 513466672 684540552 581667856 281666870 308886926 353283426 279331980 73384035 392235728 962276984 816070716 47319047 276169551 718888801 828061975 292807821 744971877 558208713 141260723 586827608 194094446 943252358 905959970 65358326 428198132 934715415 160532221 249299128 823914025 981118344 404704422 940210457 281536249 620515663 565924034 435329080 674511619 843556311 872397059 336766924 925952432 672152033 701182368 898111849 395125956 477218909 64204492 902835592 103056075 45460000 316754519 774717766 18165494 111285461 690113157 161806378 182269284 262075956 939517373 875305212 415615129 476865129 701947666 530261884 833033641 229045521 733397390 293132279 480186135 339716824 960114322 418090298 480575771 156894870 268102167 727480484 641859318 423543470 775549946 567829123 940694796 624872739 534188976 432894823 207766044 730050753 474815408 260996697 494933045 81449830 971073125 322360557 519744743 541967202 997354483 302555859 656407788 516330370 33506266 231664691 932131618 318648158 213370101 39511963 573890351 65352386 555437698 833399181 146843857 569930289 137108021 524991054 533187589 944979618 738997324 400083704 597809251 37316259 36161176 491053045 469690918 404379331 541722440 132172132 667553250 943298810 703102786 560416375 690675834 642943558 984149269 136256556 350360900 191999255 961634401 213042967 969692567 892659049 997465186 123588691 35748414 556016968 975983091 50024237 842461653 188767486 119626811 791397635 460587862 113127673 261448246 565680427 577967594 657882869 100506446 948502219 295922599 965195635 884480793 593377270 473570914 74669237 472369932 808785330 233291624 966128928 884299751 825125468 231390215 546928945 305921876 542112407 308752051 106017393 245157535 564546573 417932628 34894532 815036193 608877724 120577986 655897903 66919316 689645237 606602531 269399628 120871574 44487597 894559263 514901843 967867598 232915852 722799697 346343196 27297099 476080436 964176179 15229895 566178879 819354782 435864459 840362267 281184041 545919899 315806632 962431831 357488356 648928609 180031299 336355841 194137048 228498976 75400441 564574044 531077556 489585016 111677669 11461595 260081353 208783720 901894367 382445488 883192942 375550774 230799997 329992443 386451291 348130595 441109663 320876101 197577352 155540460 468601844 230673560 935363795 791479583 975232443 321142871 345360381 280984139 64126458 479913128 603726262 917453573 631638042 941432199 911452460 73990283 975144117 36722761 670374011 212353694 70187766 619094713 858278401 479087663 173023464 337057372 557671684 760196002 685265662 118989339 231032472 389757267 71849023 379914549 873131289 49964074 184329926 787023735 98497972 180449832 160212249 110070651 912719038 406212392 155963235 637901680 3244866 9611948 493936432 701827589 348063204 826123612 974896259 117960591 795700896 407813943 84569876 452584810 2611725 277132776 94992637 96457191 325034220 761351604 215097964 335413396 17904914 446529241 307341439 67354819 391065991 39591635 451098500 625300851 785395967 424924584 229345829 18604129 112605131 930722335 375120520 266777004 599784041 446586182 278134439 494890163 472107521 436064367 229006058 311673964 804624004 812345409 394252349 659570032 467555993 738136526 444494497 493275233 398696524 321864047 87047267 960688052 680724165 866554511 95161217 75629141 814337306 3776284 586946581 409739953 511015714 467802009 431806324 425341654 795335667 840495237 818448109 155135801 487872273 269087989 485549703 462335130 993482074 42176726 675091629 892977218 889017283 978315325 123833309 365969421 89979165 706923528 54471278 93171431 935933743 994882576 281864615 277145756 216845010 938886903 139494156 75603613 515021573 34438996 702190980 150372707 52635270 757693432 872319049 171697723 820366044 941351475 340925843 255576788 6254788 137898968 477057142 420384260 374006933 333397217 219113444 510747719 396295906 372093459 898980725 436147482 441829178 950601441 631200816 750123729 902914519 111895213 860752610 961302668 994914344 51436440 638234037 591035354 953925490 831483645 619094158 397093576 479609567 658850278 982160371 547980418 359848584 374779445 814226230 155634182 719633048 266881150 54782200 58609363 14362184 798907423 181687900 585834745 265584848 322533706 565929321 0