2000
285145607 415939280 214992968 525212707 53897604 822931082 317037619 119812624 668999574 456379124 642976342 77414535 521799682 775777888 70225378 976831651 302036793 629998347 892893185 282662885 544231449 826943870 246128812 710319840 282480494 311525364 28995830 403535910 394772501 312216132 443603722 366956000 959017451 223329870 492646251 153525907 929865804 655697434 98154106 48721546 734369658 891346349 433830314 595917212 351499815 187236311 669794961 417439617 263701285 340845183 563982357 529950403 300815365 793989456 686035570 970143941 735558859 184739339 681342176 138285342 519485394 142968141 931798326 687479847 654287598 861871371 840086343 495534512 562122005 372787354 756111190 22780151 783120423 647289403 591914965 175614297 221424048 706067379 69314636 5215047 925425180 364046676 701566060 288874623 391439740 47172634 409373765 640544457 681225328 335924125 637818938 198479198 296941141 344070983 846313526 257413712 185897339 171103447 15306753 112428574 62966044 865850558 52713305 970382392 255921051 69709086 460539067 300991829 413328873 169815885 274821586 655829791 549807374 790950297 913765951 957016484 704175601 92301531 298815538 778519065 478311867 151043447 187601352 649562916 334750107 939212428 417214187 907602177 55015367 865402615 143657229 219581900 359852880 309215265 80909720 808099697 373833164 911456998 490785250 165276852 910302789 621407822 837416858 686412173 875486807 318391052 709045694 988038464 37725636 649828249 303717331 214773135 543072576 966701291 639532240 242534911 61401934 509369596 353061604 203990438 917676927 432046180 602855438 443673297 937287888 379892286 302351100 731731964 34705211 922096127 691281770 187989328 621657974 521669795 770688669 714905659 191725466 252190890 310217133 124852654 143072507 319548789 466381864 769141830 476772668 34969087 445443322 697519795 421283538 62721718 834281055 166608160 114391141 17135397 803080144 878100886 399649837 922044854 535590921 557263241 220758213 776509232 107143702 636109992 21910875 699662040 879677987 715012246 226700521 655477647 143435609 922019070 607796266 537502894 545359686 761380806 526330210 305628538 381880229 980580868 212664655 222047756 127690857 792719090 774670305 24106363 587126757 935971722 524066777 746709160 155842365 271045610 130864657 104499440 325433402 408570645 245340286 129712639 969589806 121736391 342504500 542243590 8206116 276162636 166998037 581172792 542666009 362884679 437457875 919461223 96082039 365910394 419276005 45453977 384684686 481985977 406261799 465068750 245174552 926992850 165597946 764851614 907337607 146642374 389727860 196742014 52221620 319134236 237464818 486915220 660661328 654625783 791783487 336432605 535213833 976275463 675301430 649315693 517373655 110776193 538387640 797637855 188407988 142565984 839941551 7538110 599412486 257358338 839606992 391191846 432586419 931842584 542304011 63373916 677162035 351875388 906387938 990008136 209020924 986004276 798773537 318074037 913613699 171801795 947547431 970956805 535858899 865290468 261395168 255172645 127466424 55386392 326460138 764237005 42822318 710149378 15437461 120577430 562686094 608843977 969884500 224848023 600910039 630378903 394562123 159851589 667721676 356162718 104285313 219882855 32888262 671201296 214013838 829028705 839094848 700179710 23609425 446841373 745193790 883927140 248122185 170192781 843546904 286231776 447982363 516430012 129013961 939434193 825626694 802513831 341404989 705100140 121347319 795326251 334696968 945018350 774024641 22762928 258491747 294763900 88463624 510290710 320392152 110358901 683829175 686242048 988676007 183699765 226000403 40950910 609836979 223783570 482429560 176472400 403899625 956684796 831516934 445239287 171776139 728193137 960452496 635012710 615814844 349494968 942288388 475264359 974830188 121047452 387812058 534660277 135858978 396465668 878823817 658723256 564145755 881976495 20616439 118646205 610983852 857687816 760831188 282560787 570493597 413883868 632586487 428949790 48973530 367645285 405641926 728095312 917278967 545864837 430417121 606891034 427215384 985590677 713549656 434478846 901252175 388790660 712732583 871556566 367108718 598543775 730525992 559507038 264688767 223954230 752942707 997132952 816725830 424244463 561063256 271594394 574583838 718489969 301073751 611501857 209819259 999292198 945875874 703762268 634437968 442571010 909435291 565605078 779784623 984573816 130619346 993684766 232427342 178585799 335694245 911743272 818596410 561681261 585080775 435710197 840402568 384472357 937914995 537286341 266561640 795443678 448037485 489146239 115228364 563179666 325558018 647789448 534857947 202646991 865731721 625283470 90374221 294569348 624248378 781770682 593335952 128221378 410139951 456571254 429117880 983963044 710578303 607551717 675612257 335597547 633109150 595697228 135519198 333439044 410922366 776329154 891085050 618211791 451920067 615959891 151711894 403161125 698109993 487745181 129397083 607989355 986802759 412587452 301157051 111492390 414207749 460437381 901066071 996189594 175059681 501856648 271371006 699092866 48827629 119798991 313906462 365359469 326313343 198873304 515144625 826429180 120371316 257964046 831189963 392909560 493908293 213884504 793509885 130197855 728325417 155228783 31918011 7565412 632124317 662203687 278635396 953760824 617943002 210823296 734880146 89410447 967978262 231684223 497826196 181194062 447691096 371021939 292959324 984865457 916279257 965693804 287572811 105061351 103055214 376332626 483870494 905541917 311064800 631991843 85792207 526551606 526197185 150899439 617738200 590024897 935597145 541407463 478840858 421288987 577268766 245094223 369392462 724098709 340947892 301406273 425727681 417022243 855806039 124012969 268499909 37284908 354224159 168655761 763251183 229916014 456964241 36360721 168984868 790931216 220653798 892661721 224152265 677999029 412714115 792285954 704432798 816665582 384615409 337837426 324031628 720261881 433758456 609486009 965635984 87483580 92606113 484054426 270164981 388678213 689199566 156364809 485922724 623789796 182050170 866251609 622442259 78936019 818295569 801777922 481822768 591587308 422977501 484559948 177903522 261217475 191639317 972265085 67867944 450871645 768239935 299029883 432816236 560435212 43143726 695276733 850224497 991407379 678601310 845510844 563644388 898913542 485824662 683718898 765771890 899163482 649784029 305467106 659362513 502021295 657603003 618334481 376133723 484991265 647040012 71486993 980766865 714780547 99767089 831902160 431361092 601428927 281334476 587320003 667726815 911513834 793199438 341792675 391615604 763161133 463472195 846108110 797820197 948440331 863892790 178947589 518982050 957139958 271234873 847914248 259877638 448573581 19181704 24304409 565649555 128115179 567206072 168628183 810134467 56202213 424531176 855626158 637505517 513256797 398558450 535819287 334188990 551902162 66748460 532437957 207006315 554200735 848495492 764832974 617505469 849435308 262833561 761678332 825853056 839867199 932540080 59888214 962140877 576218241 414256023 601545515 634632900 992241166 868590728 986414958 910582843 528751231 64142908 643650017 782983369 237584214 581784909 905102479 68524703 622741457 415484582 532093621 879006277 630061273 403931459 893634736 829431602 466376931 783191455 871965818 163494060 494639775 325920929 656352390 548590438 663432694 789645171 139080578 746042974 243989603 488176159 646185665 989248415 421882739 480137025 672652212 971998199 418866951 430366429 738532455 233016250 257872660 10972822 313259490 604728429 920368479 889789025 455709938 339748870 873090124 960241733 514997771 645889135 191884656 927547662 964829261 251218526 171525987 557098589 449601208 748085328 41448315 429406655 904393816 471747330 721473790 435976800 688664856 170195361 148733761 744532177 229306239 570643684 591943327 88255845 577013509 401454598 212332047 954153024 752061702 249622968 260474797 339044247 142853393 27247790 213272896 326838098 504434965 560706092 101892714 760658251 142785011 985553572 683783304 653591475 921012349 607974250 515852426 849475379 374375252 702624030 103635979 642460843 825739161 856240480 314280569 10483050 79028829 556496705 94309984 575657170 60532146 345888963 853784281 265398089 142256480 408367227 386390807 698777066 953614517 513040894 645007977 317076454 518443738 148673100 20892871 851251206 30495773 461112657 626599271 207298685 682089575 369197604 658444126 394901731 217293457 310689898 868202233 312168915 956750248 825383140 670484195 313837387 441762849 428003091 838897365 485387156 479114136 409473216 879481014 418360122 306745488 485771556 195090614 103835760 651808258 880965299 402389336 769158261 806245036 102330057 849592205 9730689 845696312 625092534 251041186 247456167 115920341 3022427 723391507 220101297 316002887 80049133 658760312 753623336 436963924 808919729 793914312 865798281 412017266 31228868 342722599 755750208 753973664 326385941 768821191 185221740 405048984 85060256 771587713 882633253 90876421 29247575 313629002 183610856 588772140 87597697 371144730 259137701 952804808 242495532 869476486 137194088 738064302 552917034 710917943 818969088 640879132 61341316 990285265 969464877 948844621 295566967 205559780 714553324 367997885 38674618 901756158 601601640 40142591 947993383 537544166 684936010 15304554 497610370 654012954 262098593 885657560 112826064 991090793 221167886 301680553 351915691 399216587 754961191 608762974 147643496 684146978 168098865 978989695 940919742 516454923 751000928 760294939 109587521 163769253 394798199 987310019 86451904 543845901 406834658 398093140 173838728 101626 435002817 300873936 404655681 573640024 824529870 431928411 574794338 143405337 772732669 391418129 637394046 880804618 55400762 483941141 275198316 744082996 78746340 517574858 230771786 534324872 21088607 80495014 272174934 10763736 601034101 317317482 166811012 159250504 351232297 834924677 848157901 283983305 96116489 486668041 827334290 4943642 400569974 392789194 615104474 138583653 748689674 678105437 674213321 87952492 924037480 560923050 964863023 280852552 849179687 513113235 868215186 680533370 74819394 444922032 81551059 159956541 644673481 37965791 592679921 118972241 386562983 197070882 175264306 518339199 86460012 402163548 532813261 867088276 10619599 926359182 410875108 439543706 838992823 435256602 597882436 271858656 764452109 967163277 862495470 870046315 923677336 800700413 368596714 942211013 510765130 907972137 981409139 606729815 673942571 24314341 372406584 366764453 219904928 394976690 94353074 802648573 337416303 599423764 680424703 395233786 226628378 829245112 227367620 128859200 346241724 82858567 935744924 744635261 495893963 195463756 569306217 150604741 332758874 583011939 976643145 668612920 209933565 743984382 457564046 987780192 823114420 499436450 81142695 751645322 462452836 669559332 665428130 182898736 30746064 154000950 914739698 202320130 530566662 467975060 345165909 785448967 498916764 798922397 424183425 659592903 49236798 173705705 712383683 751441975 682327852 638713129 688484059 573132710 260484807 756489614 524736791 490631025 224734941 947943017 724009338 542216631 79529808 159187838 251996774 181772947 408104003 71685769 250222614 109978027 53932188 10919156 305790955 364280056 380180613 552546938 438418991 927604943 978201171 249349931 869578022 264520937 202687758 89626459 79104796 284167750 466815438 460570380 155555787 191956371 894246766 868156591 9610118 96000312 459946222 379679774 688817104 546077745 649303901 607257215 153810607 410763238 27364962 37304578 264492198 895702982 80582836 718468039 397799747 516451983 586764615 622835935 229496122 995280846 620748831 282894450 556634293 952720256 243220241 927996014 592984352 599857537 315931363 36693459 581778465 659220966 30612719 41487382 703974540 889647150 297195158 332042236 864181170 348454299 724444105 296900676 603295689 610833008 65582456 458716258 918675919 249133254 800909557 786309650 635158968 488514305 180122694 92284854 915313167 21712814 811441817 25235599 817722867 747460021 836734874 172383500 303421918 74527917 717177088 709484708 214649776 853187496 244050322 704006612 740121375 998591561 799313853 794760992 674717144 963566357 401307136 124479856 981475299 526512343 909537162 74559172 867638343 545520741 861146882 589183252 776311428 251416773 471709027 190803931 53558136 411753535 800308711 895181924 197119888 946736179 157873848 270147342 499788984 295470297 296685210 195716254 152131947 384064307 265595402 239202675 98643534 810069260 548281704 751945629 544561992 823650762 748609510 556023175 931869657 691586524 174462247 416406931 934159407 909027516 679529307 368772026 595727012 27062265 979776489 7484368 927961643 451457940 275532747 894316268 110235018 13084790 947260761 452569859 574393683 744522224 81975098 279816130 478398531 244389587 14590213 888624544 700649184 951555428 930473037 229929233 731875222 593920264 481198967 288142107 83730610 538250703 126685664 217707741 101193360 212711707 299435769 365823849 693537469 509051369 852827596 337331045 836667864 417836502 594349142 411238990 573589551 303624599 193130230 663742686 223787688 578325684 593251565 320137033 528045322 678058620 403603780 349328100 731045266 610162370 14160377 349166556 608903976 602268391 172251652 961805675 877672168 52726342 203592640 371105720 970362751 712552007 631087214 893650253 213582609 103138030 589653175 642136462 662876511 711925475 11416667 102659591 42091792 212837478 674933028 581861806 256962476 136515522 513976049 984463395 811883732 144428374 534591846 636711883 609950624 121440879 366001798 916038972 46138583 518499533 489586272 313233301 689373792 518888807 638106191 27055652 801402093 16762924 579223724 133712414 825686964 108969217 400597506 139855672 818153778 47524429 428208640 634581054 641793578 807171163 848361406 381657323 702207727 245326975 377729715 466342863 25376990 664674505 692441061 96964261 92496907 287033984 537054767 778752814 300525754 510652082 187976322 173070196 412349578 709352746 262241117 417593846 927099178 882602943 744835062 899086421 619248518 125921860 764552162 562258985 699476726 507737597 350223132 971156227 171191636 733335519 66421496 797422435 673741903 454160023 228252087 803977346 930005951 811171192 844421035 3144279 388171303 410549110 763413499 373268017 909199620 605678147 531145558 492223987 949594279 813229104 372755470 425961730 796993346 161111068 54603487 324367511 732786928 966764917 949046018 71028832 193057126 628592304 99477718 574886771 466144722 602007988 852834546 274593745 323838209 527668063 577631342 54250166 974482100 133189162 486650279 585532252 150544266 786750674 609447179 955247471 765913140 407778334 783375717 234423413 324898066 832101501 784423517 418180155 709174100 455732766 649672174 689986719 652187403 568836233 205935806 358966866 299551968 207162132 285640140 27530784 694128854 384886429 545276584 960197157 44356864 157581888 366709751 368700545 609481670 482504977 882432472 478848507 448081982 319203295 428615417 567806017 303818917 229555212 969327959 94543580 664650259 776872883 488390623 470725500 893100407 12163117 458926447 865753559 384907582 330025310 959279821 117893942 173507170 985161685 918618120 834255821 772647768 658296990 491084381 838319064 656094080 933026096 61856054 44043318 550349296 597667921 323669779 780131969 239942186 262500720 824497609 455218421 31297300 615621387 49037174 111683082 320186155 674754039 688203913 761072338 179478776 181941157 717328463 660487199 738331444 21947254 647549512 473489168 717321696 257295553 587264691 383794619 47218640 661825556 270109903 442676255 561308794 709462254 575463522 336767182 745114874 486521650 381267634 596551688 547481670 70818270 925934661 800579928 193601687 341383905 212261825 598237517 366671834 294876497 589741348 734090156 8342547 117397125 983917383 853657490 592887071 89955525 826987038 245031673 146553119 162861431 401716439 747912246 921788095 261424551 148027209 842209292 365892555 787724724 129766269 863284775 40989608 559916620 889095611 437055292 111662015 188520717 488329829 432385277 546970465 641402513 395868661 114544640 177557585 977640625 917122362 593962606 771403397 194762116 320911115 546740310 869110184 338385372 516004516 855928277 616799215 295653963 243624090 19171383 383874520 602303069 63625413 799043451 204349111 16156534 134547694 191763911 684476 679850191 632464571 705713367 71770610 468566144 10855407 872213072 225550059 259522212 121986862 283455093 242330099 239572902 154925916 753861464 281028283 877518628 328816864 44629248 941424305 505118171 424724763 183952573 655237303 462419128 915818952 182460374 995998561 292329923 89556267 721968928 797243250 959792777 442801092 842884615 912757435 181247927 543086846 61379971 293644348 382628701 142354419 504345934 751733214 55525127 532851894 345734667 508009931 416523758 49549517 937447934 798714785 402173056 921847994 748810661 238302774 385190640 506093432 419993151 480501488 370114424 844015309 159800974 796827152 960966707 171858343 599116774 215746334 967233272 534682090 137426869 423496092 275877750 177993818 257432993 9849453 253874457 257347244 959776869 716425117 650151053 977529487 42246139 817463326 393588440 41640784 896337171 805948626 747239491 727132145 803057394 726080646 826229500 533508301 958826116 217899745 59180514 46252488 645997530 802678645 49944353 268444951 833621819 420926314 460263799 361225148 492488723 339618274 96997566 766951446 111241184 791640094 553130956 724705637 257592472 120064848 866455134 562095095 572989520 371356344 782423598 440962278 182252746 590779540 478634739 893645530 455919755 114135387 983959916 609799547 794353715 238203765 657124972 506580679 831256971 411320564 771735566 570458361 607160316 195342813 412139463 251321772 935326744 305989015 65371042 656447801 379777407 653799186 930581170 392464932 478584507 16440515 69100978 565017986 156740621 474061782 854056754 381566354 884858333 557329389 67162420 25131757 761642922 781382718 565336546 473696559 455102019 662652662 868746520 392631186 492235805 863284725 363413576 744393742 803556506 783691400 8683482 151745243 275743453 346507922 256203594 141126742 248436794 318644603 962902089 15893292 586541762 613831827 807161900 363110494 527302047 445745098 747882937 34707659 183832080 746312428 482612877 511304654 940767081 796215543 737202031 91410217 870665310 300644196 575892188 14770801 551520887 724007462 670216997 275043879 24289544 221054085 646480105 705213485 813386120 56596546 447091706 70257410 860819479 715583525 556995867 513502416 703316170 922700819 895544187 775839343 656508368 370001254 408728099 459767831 509422808 51749421 685329015 266302326 550101394 323492541 455819472 50582257 142168288 91130029 304551786 944728304 374715382 792245784 118697771 572187497 416199989 194623411 719891689 936422391 173515812 858179486 642701419 323757827 271397988 159890686 484059474 776689261 132994564 259592008 701401196 289649356 508697190 639471804 735433190 95113743 73179776 433967804 375343882 359815349 472378108 900709197 334789105 22882564 61556243 243145657 738907283 486195824 919282791 321973733 661386696 726693158 917440 92060684 416011271 137153633 254100677 393388259 306005528 693615127 192193574 373573341 831359249 364282568 987055565 940773547 604406654 594998654 682297598 860436071 192428460 755966119 91027843 509135696 129296096 941571773 177565998 435328162 757375627 344583347 896308234 902791107 605190577 997334391 932087513 369850772 566389408 389862501 739027747 697744868 793606622 476474013 255886259 752770415 273803072 449793701 23600843 334885044 295826752 272456248 770296829 733841561 38632886 45167261 704896629 216653272 213110587