1000 997 771
841172419 462874877 494244759 754628804 90009933 264988191 130417408 459274175 529665375 918265864 536555972 628257613 317141380 845572414 435605640 465770398 332385052 1335864 804486918 765321235 703807450 690338788 612785292 259898307 875437127 766622754 908375164 244146682 8270397 930188358 980878026 52460212 536073580 97039258 629423233 426643238 414568408 148413913 332412478 21696566 654792280 696254390 147515059 445524222 916585753 310792019 814891302 219854157 87996954 134401226 679320047 726306853 379568046 594032808 805335293 856584766 494530813 990685805 751627346 135490178 351955586 624220429 892584579 866495631 712358542 459439986 269545273 357742392 564572100 487133943 661595570 630164740 903752091 851551214 550281536 769910446 523285727 512249372 524743113 121705891 8136753 536174904 552316485 114578055 932109442 813611375 865338180 771031472 164651932 488933859 562301285 353689513 213658777 279344935 659423712 381949873 455026794 692024261 671034621 331565114 29359185 636538040 738630299 405408618 647169127 648836082 659969194 613649821 820442647 438765783 425369009 297109985 232209057 421807296 333747017 559081080 38029720 444474234 202699423 871607642 210069348 810451908 428808950 893382320 660333505 801453524 876271139 518029146 902396478 762225619 123301647 665524074 550451903 991618140 403789881 641155751 864703996 396947713 340436529 774587147 570078208 172750534 549301278 209573701 995186858 73080484 438132281 539048760 999583791 546951687 433808464 941559930 502880150 425849169 826908740 882552534 414786362 626550869 19899531 205348555 965794636 199618780 280314031 77107210 165042767 284527908 477765068 742325243 522260890 582114395 96281878 20727865 254672858 121550120 927661649 377161489 815359885 221484067 40632407 202853384 773240711 898365528 755628950 210019410 627343217 967303113 934639759 70331739 922577989 1946089 956309592 445182274 895604436 578277409 790147355 284450649 512196672 128288846 110900373 466339495 921462402 779138881 312596632 429049446 675389669 63790398 635459465 771148421 368152713 111335550 149667554 919005734 361610977 634510765 973607345 949285921 720625717 470109804 193402648 855027072 932037153 740506064 122080459 118935553 55182356 601735905 422585749 358020759 649153490 329412892 33901523 947796457 356761075 889182962 204270071 144922322 553929825 665148999 863116038 599131871 486472414 180836083 988949787 824141524 492809596 982134596 701919202 799739688 520532259 627790970 967569181 876476548 922406414 336153418 152824099 507168327 582421582 100853852 863478620 926184709 363555398 501517517 152330950 699041027 100037933 865945262 400417907 851082429 635450767 470470530 246185993 833846113 33020364 32687300 435867200 204695377 207315608 804901983 250053480 868188325 67052409 569351988 60373984 520419751 172868428 183299480 572510880 630255957 918409921 244420051 972502448 416932322 636036314 752749730 231481518 889134389 42650992 14316981 797283661 622568296 439545774 213443634 581043152 105346890 920221844 933771568 786467731 760464094 496664949 756484157 549798787 16627162 175218297 963139545 598582432 364122665 770082076 202442744 538528386 902092905 599154349 606925956 477482449 937734254 695139536 544660441 897924812 640899005 424849405 706015560 798879171 484565522 475247614 749970324 501402525 645916634 428754549 920448887 54644307 279741626 490788692 965723166 185545587 796667398 561780578 685026729 84090014 537030474 483163837 984286637 370719754 909438661 435044691 613265841 196003072 608261097 960768871 219341236 772107871 628956125 348548115 608331429 449790231 803051515 255343040 387425002 213588143 976153682 592354479 885159130 853723073 49612836 367572339 315362627 110658168 218270825 461783925 642366436 27924760 266427467 921586031 666003444 965323895 956548520 165772786 142217882 132263548 310080404 194622432 309034354 241211559 361707732 995754226 354572558 459796617 57773155 116374067 106965875 201674823 800169457 314768002 544026264 173497627 850156639 393463573 702083818 50184659 832414788 876366321 281889227 31353680 706901099 383932018 859331598 5832969 815899731 631377354 806338173 176537477 43476653 283356538 57244244 896371428 20114402 972016602 612523971 578305367 792081035 764141207 569206895 233622436 522352631 951615279 490321905 387459491 584391848 873701751 449916501 254886595 407323350 379747862 552855709 66172038 936737514 781698311 302668604 870463744 395451908 771838491 314701468 772381020 37505655 848792948 743410584 684856407 768297031 754429452 380978178 103464131 856843698 267548716 156040990 192059910 157629348 926279669 946936357 740890264 688570945 544245210 645590212 849721992 205177183 361004836 121493402 895078904 292967177 682981997 889203389 558591900 89851901 971966501 553344054 886958912 322834991 336594193 325143168 639244351 183755588 395439302 282365709 465083404 520569112 729750066 131193025 360323757 56716344 296708116 193756277 621427002 586156649 555139455 27400565 368222819 632118559 751224411 63282691 346828520 157146119 850318308 453689298 203221022 154233213 997731625 168543883 642101361 96095510 260707214 197061195 672874972 997618200 575846219 319058979 965452402 891681789 741766634 876975255 906441433 582285044 466816716 586483232 493371082 458473056 937759653 49694122 350756243 596920663 520463100 361816854 981865109 950245156 601042604 115125689 392419269 934297541 985314406 140794587 205683247 577144941 102512685 553123898 93892206 629413891 823230168 616738436 262226230 294991778 123542163 540220896 481325515 310557463 837644126 448303718 922994311 913815398 499306893 266153122 273904472 979617094 320548422 192528917 851967551 48592288 258649606 748981684 581753298 49700883 37279004 523853927 117169594 388482419 245238317 280149899 461568310 827286598 84977838 990283121 133342615 978394950 747843949 753532893 316792514 274810337 699245321 108289671 997341105 312771772 984539253 736562077 938111730 475551788 36264313 235657279 147189542 413885627 553825585 955963650 960470403 955253673 341784716 234738286 693614163 234149225 793274062 330691968 355530611 708349471 892482062 292134441 405238485 59694633 270773177 621373900 899072254 719248019 551613709 589098436 160008584 268007841 349588383 798450652 778509729 629842249 708057046 975035605 299292299 463946678 321066861 327256291 959448602 938412486 963691509 850629680 866192697 162538893 731643728 781362520 11546213 38541520 43241527 963123692 857852976 623785355 431121590 241863919 256352704 221383276 237315243 289534812 699857741 308857685 138823754 778484381 131441318 389474782 3386523 60766485 793490861 568053200 713817594 453960344 496699094 285477803 93932695 430502638 725400492 705071393 478972660 830906964 785237325 142820761 430309994 391379962 398103273 172930733 471738788 926966405 762450502 871038636 965936929 472799887 306889279 315718425 59661750 420319522 649839936 139274025 539840778 198564929 338164172 377465929 301496857 18489696 21023992 875045527 85879730 591935463 538073837 80257380 389241081 118232498 444077929 985569720 50108389 457132435 889572414 289780942 676616643 375091663 380053970 963079827 72806833 233476253 495564702 891180075 413656868 470351531 310937263 639962733 576139363 802261400 690777128 390670434 725446921 272820347 122395070 388506569 53909127 801548379 556809786 501697430 662983839 790390452 410569723 775277167 630297578 452933112 585688433 558587182 54085203 25963020 988050851 575938402 788258202 766124743 341170346 83362253 266383315 145352822 141673012 546499303 795021284 948535387 911943682 329092953 440121866 84698409 100156010 312944772 415348820 798615434 572695253 837400824 209401127 510574745 818017346 975034621 604451768 67144296 195633602 642184461 624118933 398026364 1698042 599982679 991211549 393140812 948327588 596756798 693519107 378952133 455092494 232545752 529956047 463584713 338079385 16891504 683585116 11848875 523693115 767797253 239266907 239215796 939859966 816862409 773578703 661671586 156238207 892155042 703779984 49864228 405508207 687699372 219643336 872963679 797859094 15047860 453894264 165976172 951135435 786430911 961271796 13886935 496809597 194326145 982197859 187889441 538990893 142636263 14728000 812475968 935317617 267011982 397934556 259044634 832619251 111878217 237283801 769461261 440929520 929409694 421698992 996963434 595932858 849749578 690375468 34608885 105596726 599738809 179332077 295529063 892808799 183419022 791157223 417877996 341247937 549382177 223325664 974009254 95596286 868234236 858638837 140151592 746573901 150705758 805654549 784939515 155547894 947662520 336738948 34273820 97993175 643458098 286486618 14504060 493373410 160443943 149459970 892146559 458523805 518990500 157056443 662368638 625786016 68316397 701599770 976874309 702909979 835433977 751566470 955247253 63983437 865994993 67922363 138668707 861287694 673034165 239992904 301661335 525237574 898352982 223121169 251621902 620408691 91601053 465053645 718796697 680760615 443065475 595793801 173838652 623053448 467537079 735860003 321553135 300883663 258499611 162750927 290318113 552713929 199105351 689267606 873678640 576273753 797394181 478612946 126385649 930106356 112656083 701730740 951919151 290330915 804526436 746169534 872032548 151565573 435843359 200403273 851111681 310573514 791587999 251659521 958828 150785081 562983729 408123747 348491773 97635371 240022361 812447302 379966656 239293197 560548173 50277967 214134454 135355490 929529720 152425851 687623251 380599871 801857785 670262169 625231873 223449550 92361249 943888077 157901468 226489291 978729209 126460943 267191797 895363338 849235385 15724970 666899791 103228143 294343506 73499581 888508389 618374132 4543974 805961405 54482274 880274983 675638090 931395057 697036391 286543785 990812043 111033333 621231368 776355120 816407910 687717176 702114639 321576069 645963982 226118270 438257080 741138183 872846185
105055070 541419444 745451559 768859924 543366852 650376742 593644010 434691163 393590129 423312872 98545514 853119234 537541238 73065031 943353173 687450751 200355773 837508995 106358892 295395452 524088960 956670801 786205702 733815130 530893776 417438553 137624714 188290217 464720655 708818871 683085304 911401393 684464758 432672126 128848993 780443629 546914704 158313264 976062058 585659787 865217981 870272839 106301390 381363693 180574384 661292208 623391193 332175402 386290929 282446155 513828845 139094925 108753500 998095980 873557505 320170517 109930145 555796317 735704349 267063028 836990914 174197210 765177823 652928785 878541975 657814675 599880953 687184262 75425613 272218541 927348144 754457122 929846243 222799169 366848607 319394791 527238316 848594908 672385778 675598221 433993423 371129598 905998187 710809598 917310666 159948699 776606305 581866200 829762795 869088925 952780156 330182382 670582230 46515551 163131386 232334535 79626498 221987379 208814381 597802781 679360827 943315166 642245883 867617120 181527841 125960471 407815773 31616561 940236200 79613707 257431520 5353959 254216343 205947868 257729063 326027021 222073609 551267357 161512038 812795106 713857006 781548120 663966953 448308695 677404811 308149640 872916875 709775381 460741366 737730975 605424704 847757813 530960539 789722113 499354507 53667973 332608186 437034503 578534152 530504714 823052006 896350590 139878884 245328504 886500231 48208677 247109471 663959036 207484505 201764146 788067153 751510899 36531435 583152078 524165283 709340400 408064801 555538836 472455633 806388794 351293875 765818902 293812079 191326539 168310956 277476952 916013729 77936850 120681963 484448083 329640865 413570226 954638245 59625076 594169916 524323457 525813985 835074586 181410389 781393930 920411130 345141787 88442977 147566027 265313057 483842111 193571818 15425400 175733465 635395780 801086989 674668150 837834873 892754649 310839803 797247073 915824302 991048995 405652347 978931078 874774518 239970362 918697831 430927721 965696293 861830957 812054570 780872001 251215844 428644858 736529481 885539959 981828397 336027671 6258391 454379307 729413073 978388716 329093630 509071023 816097522 20593750 544406909 713139721 659785353 428329766 470406437 322688629 729228257 605872544 186526555 542925793 851946010 67552253 593391514 441841008 379903143 622306537 609924846 565112312 29899728 553500677 863366265 641338500 133074737 88171622 537668593 620632274 256570425 703550740 614926368 258069973 446422188 815771532 390078307 992062516 645389602 212254783 577591852 976677578 900469125 413157137 848585089 126239524 582933399 483947994 448401274 372774918 957017962 715668200 129504710 855104998 592586726 21686139 892142119 100075887 646541126 865737800 113053937 707821568 151558043 629097463 684059535 913312811 223995207 717130149 832321790 297682486 382383492 676593507 43211856 915261085 866549979 372254901 733517611 294627982 480508333 809644819 252760648 509578347 646124206 877654635 885340660 253708876 597858660 429513117 663833746 987114618 6607532 527457534 574400278 881106421 108411702 890866902 253408651 588646127 136822276 939090914 796537231 837836623 204099311 577966034 732200658 820439856 91290402 646014924 641402779 750113631 503299997 903258343 231410498 419384800 664513971 982794929 104246967 324036713 56813964 812189610 29495546 923966181 642412708 956676551 337335713 263082482 152784970 314412783 910640469 311702371 896751138 803809665 440781908 372685504 519977636 429378253 593228529 973251009 98335642 577835414 115240464 425634007 655080102 1988247 73935787 543787939 399096762 480413946 813466447 481706877 807431581 880851170 881658015 563266542 111359597 12046819 282032592 798987062 761160728 624989572 819657772 251445959 253824225 238187460 924109967 393647559 311772641 683160466 437175277 235234706 877460868 242081108 167181770 802354743 168611336 957963617 415126208 110198006 205379585 961686151 310276861 780147400 73906904 392766086 428591810 429403351 163003719 426385042 86694629 865213697 626349534 875683285 937071952 22272601 356707714 417611754 637697919 939582374 163958761 896449380 742717190 445104099 828708383 30651973 833927689 798222525 394528515 346552455 563808707 159183640 660195274 71983767 150116607 698293643 352587388 262724564 270895266 568110815 822523506 182492949 608358431 375257747 462151902 227749152 142816257 827202395 954958659 418735412 504372837 380722589 944943097 475441536 643289469 124826610 487760043 914458537 33120270 441116587 685081816 648480072 382929394 333198666 585740885 467526762 686100120 411272964 124064201 63405070 845083519 683570502 934583087 943204522 624939710 531948845 839652952 602913447 890784639 611617036 405740902 232613088 404670079 945915114 592212818 526326055 153282704 582832897 224815208 139063489 702650648 2660929 558403270 14350564 379630736 286875850 565640928 586406720 961627397 481698934 150679551 587499123 31364761 371915596 881926333 165377683 572760579 494711310 331153802 658643369 785661707 951268524 370510635 397898288 650205455 34729167 179512117 777900954 725357954 673437775 176058518 496701131 953523815 820499901 412924941 649847964 804985562 371199706 769534637 457000025 110700423 645862686 263933534 346571332 471587121 128170546 528760924 420868624 187673389 471953014 156940214 741441382 188372452 972807548 481575888 683748451 410351957 635624587 200926945 2858520 21388688 61223709 847021686 481692425 882566972 612598625 280073709 505829807 447600657 173961402 390192379 958003958 765152095 741248573 14817319 929214143 16727686 290813239 804672332 460815455 142552956 796884901 703128091 697308959 227078474 368940731 489517719 673313978 175955087 208412510 58671511 621333473 224516603 169987753 354081607 816761530 355899093 844264044 929172903 489684317 500141942 513961896 927876362 142356566 710147020 905803540 573305497 579741990 205126616 713077147 103262414 701418690 549221424 525491420 285036537 648184338 618648190 170722217 509140159 546678387 355334655 237103752 536699029 876929078 235222020 551679029 837408841 165246751 908117620 527825950 686414458 563983078 47426632 341824230 236086299 716924857 626160654 272243938 633873652 96572600 20006504 171805855 790748193 863096440 299466890 583146330 723779217 129005953 613375678 68222342 741762952 692967120 588876003 572142922 953738013 549338198 224120042 487038720 832626877 720681846 418201432 49431480 473483174 733667211 657563080 83390899 842071405 420651616 844515174 16075496 227625081 665218230 728063860 105032578 719079557 706043074 38792137 796749407 795088162 439021739 933055308 335574931 697070642 550527248 279641726 643100387 617321070 871553409 296842222 36975691 344491490 274845441 424788162 34116216 761208940 73903755 230400308 551080271 213115456 176137610 79701779 192100 800146022 827463263 550510142 30491524 346179898 864316638 441155885 841891116 816449260 33149649 774446440 404436751 909380094 297983092 111932941 956674707 675828681 381687031 176993870 115030356 527693048 412339968 803583473 51475360 29687818 903166246 553403854 917001466 575098836 641632375 289470549 598724760 718120957 384264434 789099013 512774629 692267905 707039758 197784566 64375039 944676655 798859058 608149072 466954042 499645995 833614906 223668946 243994523 758412396 230664697 317252428 133822813 720752959 897709233 825328677 516886128 5470146 351317660 510462677 434784757 325514090 52586087 151968364 574849219 965742205 128706994 170567690 41616357 240446105 892582801 67742565 907356954 179138859 602412302 996174150 744597844 717884409 767407012 159114763 408469305 601980313 79234501 986364967 51290533 372085239 71593814 599113886 202246694 687515347 450731566 892062090 367507327 867091009 903801498 646811800 491556902 613667623 305700828 851540875 880052421 14145986 43870375 646204600 209210044 93499425 415383973 136522121 267099805 178578600 905201 175940859 868023471 330762895 994088861 809893919 168385901 878960737 31753262 116169884 640654852 694340222 927039771 440171819 703498456 429371289 170306129 606652954 348722175 334054714 159042226 486080458 176800708 552144444 52786321 439126833 958769958 465028944 516227127 631045209 455836758 183450489 277567074 97915615 697879357 72754318 246963905 12982901 894522355 628047804 984032377 716394848 569363273 364401665 293266083 552977658 376219968 383195314 160954571 962614833 363268496 838773238 60878707 383345158 414898722 864885576 325832846 253086224 829421462 200390649 742434821 678706423 631900094 193087915 144065077 482766073 918564385 915691223 769950831 390749800 540134009 989257544 309791607 373773865 302825781 818821790 420921862 178520118 863467000 12568781 873980744 396779549 206714392 860856987 128679775 940016512 559348512 800867877 248822750 454958739 184121678 745300314 750852174 105270433 20089878 614008446 960410284 395036296 333182621 727464105 734055913 125924152 617829438 47141446 65110121 267459639 725804297 226576788 540748933 166600224 797731903 109053736 269084425 837401887 616014551 342938217 766273462 898880887 564499965 893005843 836578753 899859964 249129357 700281525 330709074 199836825 968042140 973813043 590388998 81923276 865129968 617677636 540219502 30106661 619888259 254580212 959344270 141619915 17734660 702415908 736374623 716201462 840790357 648119045 239144269 211432566 394884366 7127713 758666169 256710954 113136633 308926546 23781752 242656650 424539540 70038345 308093778 110294559 808011410 260526856 593062020 413510405 85335386 107256296 482229054 470479471 308870790 978286996 263777062 567375139 883561318 416281996 356626388 797304570 933707899 893631908 157689684 668865378 705572860 228899970 229169831 436369372 703249492 703356451 108574785 915615358 912380065 950006870 275076236 395432049 222728503 677143359 376606308 912316532 966066715 980488150 713637274 845161815 625275785 373035622