1000 1000 451
787139201 840305263 677124878 498642724 823367787 421204207 299266627 900321886 546762019 469708513 638605644 159350208 175108298 721872974 72901829 963577183 908725270 833101302 824548637 713833794 234497233 827278795 9584919 716413928 109176408 616660852 875240013 195098305 877809180 793142987 313128360 941388976 30784036 752522847 762417641 875442320 613368202 696662003 819091492 796225963 82611449 590163197 668757056 40642628 993146678 197108520 593372536 955831311 623829908 877773522 24812252 959870644 554179198 238486415 643075537 993286735 152180209 658009252 868653709 880937971 805533183 818264461 855052444 636206114 886650189 711820919 640725342 839261527 44700053 327997638 252181638 920458364 397936677 861998481 324865692 729937780 84982367 442313249 950017916 156310418 324718647 349261430 311349974 857332256 393936568 482948546 334141612 760356058 127289983 699472107 218610646 32253552 543339582 643495181 858917505 31584519 782517563 514457078 717755564 833032889 659377614 920196777 624002217 791161872 388510694 769201116 54808482 770078863 323677061 27775609 24488466 240283433 989752127 551086624 441052232 266970312 48042175 706062244 571660008 833040583 214149955 50507658 789140841 277841785 424325147 671065229 478225559 414993568 99306285 901212188 27738386 534845942 642645876 772373722 711509454 810089895 680849789 470944542 568486034 951986389 487805928 619836273 444723833 831502867 548945901 562254610 781396595 771165163 600236500 5187189 439856069 786057048 729192316 890568639 785862277 842945612 132413141 8887628 83807263 478560300 19936358 712909866 420287443 239516751 928120775 981047451 478760756 486491266 88263208 642626199 227214506 103966598 225072329 647052360 98070513 883431313 265659264 51245707 16581272 141220553 220653366 468903798 293900931 426330060 222701674 359164620 67798122 954857515 371753900 183283851 660201047 811628266 376680995 311664479 11483180 81995522 147780104 976077612 642685979 316319712 723114793 353056136 668451628 783997411 149096295 581016125 470555578 538048737 748620600 181003212 486388726 223761571 836040741 389496293 22430819 851317604 22983501 770947569 132594264 30996054 151667169 203916168 989292673 431592989 669351334 106683131 360189791 954643793 56171894 839961035 37901251 486980353 6655935 630108975 329868631 339903275 698475266 605531795 273596181 231693637 348679253 143020052 987835341 247742135 407104482 722820356 614071460 663104862 316240230 870580332 166507920 120660491 979699891 197566341 425127389 34833154 644795950 703759934 420201131 695378044 165856081 42331578 188505453 266639653 681252138 507237583 995129451 595615902 34121434 873333383 300905281 154349052 70795800 927646882 864256862 229981255 682194860 110372883 708899462 999616252 46578164 408179583 47700817 847848076 281248610 517369793 885629865 153631963 962878715 163224169 475817296 775369665 126423769 474833464 556289624 177783180 641853099 94706597 837100968 251505533 631974960 886319451 148591998 160551494 771342784 706929337 681315816 947420306 391184579 534091856 700674377 84346749 147132983 285111401 898796763 867184408 68960046 887582077 170036519 866881767 786522445 678497978 698988174 387153506 769385295 952412293 729581508 798097271 502002560 696902386 833471055 636031750 600950851 84895822 847009036 52707684 124321933 311455126 706570411 23591129 658998887 459549437 593811502 203346978 738056559 607283306 160971118 467471599 65879895 771629047 990398358 66078310 368739941 283892851 330149286 241400734 658639858 815528417 305691377 338066981 334311147 702191095 935601055 711072379 585682515 900104352 331074860 78038165 914181055 47357563 15129319 680333915 937664984 194278233 73981556 834345001 179279581 62642370 536991819 927583570 906042142 642515569 465869878 517344920 452264322 168291028 330881495 956019894 753917954 817412493 197867295 931757271 758617132 205810163 213277400 608441115 389980065 72099218 407758621 226957081 581421719 483192998 159633885 828165208 472562775 451573924 21295451 198602964 617692608 493605554 239152816 894955904 131975618 246321706 592897096 977064638 855073764 547748123 98329185 898118888 967276223 736822984 365872527 275282123 595980929 774971431 615004987 54938663 774132587 417852514 90834975 259079216 556086355 507684698 380466891 394992656 582781219 608786463 796037156 580452194 434911064 260382073 348405727 435969721 739968644 246525539 309859082 538327575 576560844 484756106 354081412 916894070 645164394 135140562 851187072 301424963 577525548 966311377 521317894 869087453 372714739 989343314 272782706 357438235 198368309 444706260 551120115 479747779 702240636 251540745 301112845 569119508 334682853 152672855 17104152 780205117 683157154 413071450 952192958 281383395 718694776 815072864 963144065 406131615 596744002 843483371 997484595 878978942 108391276 186510387 630715003 281628799 227666808 446260898 735952471 844463385 561746301 73367894 848176533 572027826 171036835 981292194 928514648 572307240 400169896 627350669 877843353 385888076 512305502 186858833 776808868 811389283 120366890 207725533 162977431 388416164 424705927 290154068 791345382 387332284 495714433 328741004 117968346 771526732 575940155 463971984 233024525 890424682 463755625 916843807 941937135 476151324 791182806 679643178 961038916 34805984 477829344 857852249 120562340 993286951 292859895 93868679 657955322 983290325 664517410 551613506 957339910 645415875 388782969 343593548 272259291 405264446 538738092 424798237 509514593 106560901 188532346 271030110 469556692 650019150 273223483 841848943 865854275 594064705 722506839 202306786 858906386 360633724 203062733 14034941 282829176 650376461 196021165 418725180 340767746 693864571 911861918 330061006 564977678 508630078 302401113 28186131 709419857 676014914 546176555 690106916 253335122 514967913 365734263 208392267 833122540 246201349 567962162 844010118 452417744 521291874 378550630 61020168 522281473 81940538 108711855 411603897 466142038 6974527 780674497 265109169 742131451 532175508 694566624 777842881 849619696 94228308 314232678 838149866 355515272 170880778 966108992 951680995 306911724 10457399 828442226 345875095 766342806 310809808 590885775 31181989 768421846 268969661 773203009 234112735 656839248 826336860 643176391 899535307 765857148 770053627 510034290 78957605 880643109 346558817 338403111 741117787 7282411 408347206 32031200 704007183 638585537 684003030 794714667 788647065 619122031 219178034 917375145 151331715 31731217 419133166 371995792 508853259 24181654 784482196 935736362 453417124 666889538 440609056 871856980 252637557 133776684 787263363 18510848 902921944 470934721 825165857 806575283 598232540 526566207 703052882 883575047 240197828 246932027 496442852 884085802 262702470 497655835 609217431 324099422 27273805 728887453 619992480 570462327 638847992 650568015 4171303 942891104 418877592 36006932 554007497 365111702 928369654 101537701 652603926 182138539 25209866 868698125 603176980 772750020 881040261 562298156 200192186 679187484 841710664 989856054 836287862 31894655 191812587 995394353 768303784 701817808 140335671 509634938 650655268 376957571 495084460 6647361 863870388 153423907 206584316 589550088 615483796 836434381 165941390 538646056 450679540 562299059 450064124 525809995 837319802 819111067 924838293 369158643 208740029 119410782 997973980 307696882 126637771 175614569 319354119 583337968 152444068 839598399 357417601 434926569 647406012 729651188 701666920 547713964 225972605 745773748 153150479 35578973 932434371 913806650 292396157 56797171 91505502 999806809 660196077 300232635 614075027 845027191 684618572 675943123 702807451 56533773 998116542 433562800 536707875 754559784 167202842 311927192 634492107 368679659 586137705 825106217 564430247 376830987 793128299 812834000 865863873 352131409 47726098 973077075 158673300 553705244 491479812 761884744 710086291 398788572 482266909 290459291 359388576 79211672 241287659 79405836 34061461 162553193 645266480 637021614 433784767 931219965 890327652 123613034 482363997 747173397 499473713 62587514 189896485 98923527 258617333 197875438 323675840 666901820 372213571 986651946 272304714 591914675 730403170 113576038 166028755 706733437 855346380 535898413 270978272 434163519 410934449 407977439 819763434 761053875 471912818 71282479 760485853 917148711 294684454 174465189 127258267 476470268 292305432 320992028 604623223 179673896 917204294 342573381 569525435 40103349 483624676 515558435 244183842 57499455 548292823 132575117 607926366 842090362 340555579 506643632 298398611 188095658 22360286 241250954 25471450 194177578 289398210 758070384 31460543 794776806 283251103 507099785 703186116 79917536 780857950 823082576 478952412 959284910 166038175 478431509 407544816 225029114 258336308 633849981 60978526 989964289 442727076 889915646 799128436 304922901 395107241 623369828 850732793 324313115 361540530 258636367 708473509 250462990 632857698 668016818 799521701 268429178 961905935 541612630 28199448 709708033 613611332 775996757 315395988 824735194 301425471 437354399 339684769 968633677 185575539 657573240 537348156 571850808 753702919 319221752 125328470 579962253 21147478 847138186 915856467 547891409 443129453 663330413 74263692 46433951 230877329 750723382 379086797 595211043 536198326 233887564 200273367 551573664 877212680 132636523 580703199 188046827 346377830 57407522 374672141 642589933 390995682 511841365 190768383 60376868 99880002 41638331 511774275 131101218 635755906 269201248 38996192 166168589 55400528 41071653 465234638 824721950 315752847 456850235 581050489 662624546 902607829 601793708 213657922 745336316 455622636 921904082 544466942 837848097 527459156 227600862 547137909 989444122 134201536 737549906 518002404 681418245 657549973 586651015 530891388 570351125 969565550 955992360 786668512 598954766 277010586 974523573 718146219 59825354 557440668 586804226 356391656
917948598 29808042 122108853 809057688 180084821 282314287 37204939 764904240 415691196 501854538 774510611 271320088 678357524 59509069 882550961 944353581 986276380 761686590 713560221 643080255 137716389 585443417 784189986 944890516 889628948 831970444 331677023 697563491 407481315 204491513 387698889 426491994 126787359 740339064 663769511 105046553 114620651 783772690 834537621 518016181 328929789 588958087 890014722 926469174 836128284 637118409 484268209 700615448 659181736 575398527 861878332 540561102 13869330 269135235 650583436 878564922 460607839 771215204 680782178 57365559 719427753 887840229 2521298 766455824 586873246 222032508 933615043 163824133 187768063 761411284 905933680 918492109 896805410 413532491 108911849 858344207 908444529 813394805 920644499 227578856 849960681 885911703 761745828 27813736 75410076 606691884 981424808 304562196 203833135 346713188 812847103 729881702 882815069 896419488 432411996 515332936 111673714 243850231 144177479 842282653 463948240 46572981 114726300 658899897 8140653 281014742 217518602 26376675 55338835 863613327 52600470 337405146 77055008 613734854 641194517 905648973 623632003 325406101 888067765 456173410 682457029 434220235 337057908 312598832 521306173 406078058 179876775 500108612 569906651 827596586 661002101 797335840 873136798 680426485 372002906 645209527 752806174 61416041 174936229 669529075 32910595 860864345 295521529 123714864 388738443 268485452 259566800 246650814 133756424 1400061 131574003 790802274 334921312 563156953 278592515 871846869 512407436 355673220 166764788 780162884 333439513 554754388 723776908 187861710 382080170 710291668 571838697 666074377 223131763 469111363 137364984 827816574 658689472 634239507 41177087 497762344 992876140 973561962 871644948 43026425 178630250 920587684 502523043 249934166 717313088 611735759 663496683 194826134 924790151 635318829 93057154 990772358 272059244 151718838 964379341 439291112 373381938 10065811 868811913 89225967 667524270 107026596 53658437 35279044 92879050 452870395 928658661 728241925 361788930 26523743 554531361 329292609 948383466 715465930 390616323 216606333 927095974 538858219 541626221 847589810 140619120 267989157 2638225 939402828 10958101 67499918 518489207 840996524 736885112 928931185 927786618 4085415 244564238 282135757 691144139 493814790 524259681 118794579 122581229 52777732 697206670 758957163 242574135 653269203 843895494 941653936 940315989 445145623 506196688 244048239 406716872 758189929 282773637 177157421 369711457 127573973 818771 423832606 292969930 820981084 964335291 689665454 476813309 629216115 373681364 193366012 459867850 682686850 636439237 131855962 68514646 172540775 980905550 667208143 119637399 94211568 502034240 865933717 250166489 819187556 349229568 438548379 789679163 674181115 257341960 609139971 428349235 652663393 955788390 852582565 367310854 187428919 875886652 596538763 581012561 725801618 513351998 458152819 373024131 512774778 968043575 126358864 176112480 173769068 994332036 61633993 687165567 590086105 383097239 340769209 137949901 941257637 216099701 71086765 587671049 470381225 289915193 420760425 248364613 419740977 302883983 211760228 296272491 24073854 763585849 392066631 240664758 628171589 390651278 474188913 807935797 939093550 880029942 286633846 679097419 152545878 678383215 112982939 469496626 197949389 426655499 722508124 175201395 714821145 856247920 748237799 432334447 881760433 99130198 290192286 416180697 613725571 305417229 741994649 551999034 891966831 333898484 142207266 661193836 158342346 331727619 67102775 905169696 517579228 935459394 408890379 118938968 91130722 599247440 790588037 704112365 619168524 589286621 187598783 612651786 315310080 650527792 756148872 666042031 796138838 62680993 236325603 789508911 900675225 31538208 656905350 850764466 94239820 690905773 476510044 970255028 821348963 784815837 542177283 374705284 901003462 181359452 221266511 399771078 737922002 947827301 714701765 178000113 133200599 934584908 54832161 314707922 876726939 840891892 99455440 277473800 476975061 640639833 264663159 833543045 90357171 253489160 941344106 105185555 413580884 178795938 534183989 67109069 730329935 635648605 685741335 259926689 675663403 333564290 285394306 992165589 108986597 529237488 279697053 388839551 877553773 766854296 130178498 164869644 631996712 306948863 134649600 673893818 956098927 766526911 495316377 646503965 147124751 721659654 466311301 381572766 906061512 515422997 403697390 686510583 526473934 61588162 458656434 934204600 863321419 954023414 317955813 678019526 67029979 604953136 495857740 89409750 158493454 680448257 461689314 24311030 50306281 190652046 223030615 182560517 91693925 691240977 84286860 909869110 717807343 997562968 161111832 991342225 404515559 488954949 463848646 862117746 37756961 340568908 291169301 255371784 46837094 466316792 680676790 778429399 628880884 65189478 218020882 135114039 773179898 183362248 767799746 793509330 556846877 748171747 148940309 241487658 976092918 717917073 152898445 903373073 743066002 443468096 403656802 804205102 101752304 627140210 274101501 749640319 656268935 476539195 172288126 736148946 993230269 366102214 942623031 134799946 169660017 781150672 91921199 323973344 172137586 102412075 396200609 701057504 761150725 723918397 833584762 46697832 753020259 556844926 27259614 7514092 393842488 844761854 113672611 428451509 238942502 668897500 499565268 1377373 295818048 173210064 654805807 863426388 773287823 507496866 565126312 117066334 639267473 143173040 698480356 897350419 167357364 115829100 889833407 98945630 760742880 833019612 307052998 347981055 971160554 900039449 123393726 170796553 213903650 186573008 337047579 940230500 644529606 228444356 627486090 374232140 249231756 393219658 378842471 910457808 579558940 729615307 308312391 427946324 187160980 777850181 879471728 616164623 316811522 433823947 473938524 117137038 969956589 850920192 933126458 731271983 416463821 761096096 132474477 233874599 841157262 723857400 388749067 394065277 412071698 751380329 740977759 503771020 840449708 218290153 362179175 575210117 962566309 141444737 177855574 792094314 478878394 281108432 571779347 721389589 120061852 16632454 261692857 908698031 993937775 654161386 746173973 159224121 79749707 474889813 203936043 997273350 135133374 358500789 358223282 970617407 478935625 4971531 6823059 941885790 942555614 543072237 999255917 851303091 292075625 758927109 129486612 271341282 810715460 894661775 959218702 175074147 452482752 749497823 687031061 494787329 451435171 931547865 695543191 923355740 455430309 642428023 828209721 288222823 412919538 236073799 261969232 432975082 29640875 853745642 528151398 522293505 695260261 544818583 306316219 427744155 253010088 394832021 21772482 883052540 821250673 800402116 365541535 130940475 54330288 871330837 276116912 799171525 234769355 534070029 292485889 584145368 42696729 825038151 343421142 956076553 502214248 980723183 607684389 400059582 264079736 533755975 877429273 626888629 606842750 238029349 594692752 745762427 414286498 951163507 190463134 943987446 475861889 120441262 61581320 70851036 491635115 178311784 258527434 83768121 677298214 441255367 390257042 924684013 175430633 289769475 662358594 412475692 526526562 477821163 48788594 642626300 46120433 694524001 220004331 331590842 312303722 843203289 776823085 286458005 82074519 738680286 646530538 976092946 758669236 777334926 908479881 410086790 819115505 894248473 904557988 772546719 203869428 531700293 265206410 700357340 812332884 544180717 156096957 197120272 788904479 529466237 112488565 150575843 922492757 902880632 105911836 93306705 74827882 416798451 349565649 693026089 794204872 263720983 965064677 304660367 821857867 624285858 149769824 777532026 397352387 158601319 121343357 607167799 112321397 192695753 411940649 506019556 377379227 545146948 469837960 383253238 426973407 6527717 83879024 930017715 179950308 15140045 634088941 124467385 229387965 995812273 49409723 35192693 619645300 638721629 498375631 587192237 671595653 589791020 629472719 348579831 554196064 890816146 365034389 852329535 469194986 703288211 455089840 676924997 640946172 679863881 211601890 542952988 901662179 733723745 850611619 226349741 925027294 179878302 374342300 556333106 609779364 686628437 721312302 514460859 877079771 89136624 505629929 814092972 164600226 938005867 454020373 803236157 818031880 394953690 542430508 899129593 871652498 582076641 703729245 401161279 38115769 319330106 753004811 573226948 196986985 2023219 315172172 64012047 921548676 476454701 965728619 277823228 71170909 969884190 899480167 654118458 748933694 353412112 279474290 241575885 402101986 868646048 186252146 289630092 889217275 688314752 446813571 506563236 273280429 365275893 43563890 199971347 290985489 719517273 518428996 450689838 148490163 459749018 340471981 286684699 809585941 467054777 279262618 578795096 791497258 454566989 854569640 305476914 865273051 359231997 921958826 442061903 357015942 237125129 386212902 597251109 841715066 980427458 131404249 355177088 260627836 250987278 1450799 55249664 527521860 509462245 70223307 123047320 824399617 683725782 902421765 6044433 927904209 705050499 506197095 29544325 556281930 777954336 931334703 366055140 188696052 629516536 961060305 632088946 333294797 339463400 495119986 315391559 971900867 237893858 488913774 457892302 748847933 880274540 747543762 725058118 338036627 222154782 968226274 693421636 668173201 585002536 974651797 566647087 684167416 883003081 305667860 443151811 588205821 708904665 94764095 232034959 741950153 203927616 825612839 852871799 882042871 2708092 407793557 576736562 438881560 362384672 310451074 134267852 153682482 687973455 533729693 185671462 54327613 584065861 989646536 532374641 638917797 981506767 101695387 941344695 516584395 745063373 847784672 585658962 482736004