2000
149673711 661481491 546683790 996625756 920015883 356782398 619939883 856326149 161478595 844792339 523274218 607032290 197888257 386131046 299050881 35471814 164330808 68123626 990245319 669778921 475402199 273247505 99655679 4450810 182945329 515549975 142377165 640425436 783324514 229470262 954659440 172317547 532245204 317183336 971076602 187569204 9953932 880605873 59701805 547148751 52969955 881254254 542948375 431828594 238134438 70684287 991883162 81027858 1915785 253219343 29730330 931700200 476625844 246943192 783006020 184044816 48504590 822691805 379075317 257386879 269960575 31044441 604532155 566116541 453595825 868793880 978305440 368194057 640433896 520109827 495637263 842556273 253081331 709635426 913999123 631255190 495222529 323178780 823359078 192570299 6518360 790047470 715334248 551833301 285930087 368315768 791717444 17678007 598243570 601896584 741715444 939173109 769778594 136877336 813920727 182229008 845904138 480327210 796901944 440815364 36271149 919089337 581334238 885892753 5949461 159359204 435254776 991974782 942822181 122651323 193674601 636980760 327698601 966415862 922292169 121948073 813960092 644328054 450923155 892636319 261528470 862328198 891478233 622244072 916223366 644989981 783202403 868839243 719193525 784663296 166148636 763616501 647423109 962340236 285672978 916159190 861248101 3581743 557831790 568024476 295417858 80862723 459601059 417539027 668729731 430461858 190359103 118309310 959652880 50978319 297072468 829324616 106891176 398632172 944864316 184118886 608611307 928571215 582758443 990387734 451477594 520164084 933091163 947042327 167232725 568695078 45660646 611223808 512409179 750727175 35506639 42911767 826525056 102191319 808074215 907962519 300123044 900498798 398214258 650697500 428894285 752280021 117796956 326418702 84471773 708511546 484366044 672682631 124837179 742632199 357455736 520643734 239739876 698148267 997737043 402475031 427981973 642637617 1616811 670231250 149077007 637880284 218466114 526782752 618172308 443927318 146033416 430414590 707989774 743978089 315516767 702282243 540626562 621588012 101314285 542125607 894673289 477218623 214073913 279005607 400335866 753078211 837801079 16820494 605924973 282887366 701624850 649302572 251938945 359766993 894620769 656250167 890755044 786652404 55157940 663262440 707291363 293180063 49009806 323667507 747092833 684703803 878858060 639055389 503803362 108156129 279402026 564685641 646983103 218525228 70679783 842373675 317336963 64282234 360690014 927729731 618484016 340696612 593783161 672503150 277786855 464474376 251678704 115961504 188571489 241594649 306451897 756289855 247736187 369099620 787356035 426323376 806526918 378544255 199792300 776764960 212189775 695118650 715823419 846257927 408404100 817808039 618456770 826215594 465930072 913456136 47204550 420884325 24195139 422133418 771294400 21122609 377069631 630548774 364505106 950124118 466753146 510985438 546791589 213857229 715159347 986196093 983852769 7490039 391370522 877485274 367311243 673122505 314290211 894823548 968982740 229995713 826628993 344475454 691998459 404689276 741164105 107474014 704021618 855099534 176974491 22095033 830878413 39027987 758973283 725137913 995789897 833321090 107607236 808661299 448409643 109559798 536527746 473391178 269437074 91357541 722483953 392760279 155455650 675908367 390775782 627616762 864808122 775519208 185425230 948944445 165821782 525774167 122138333 338975995 365528661 179168929 979981879 401735777 316316196 872757966 184499891 714855341 965424813 667292859 567104528 508041219 189993660 849337200 4886670 89013425 142715194 384601906 593356109 264592692 469658621 69971696 522091283 724875386 645647924 506911747 364760464 61112470 632364106 189432130 861767049 999230372 700697305 928491907 657684771 308655648 658878929 439108863 247272246 918074377 50166508 804064624 379467675 680701801 969292210 190125354 499035373 41213504 313375056 603055947 718598704 242391444 805432709 447759302 944528944 722708369 352622407 545799903 29563236 208366621 37298659 393119531 789907959 997988323 929969833 103829786 41107318 471170742 510816420 282739799 39357039 780441783 457010214 941034144 948994579 753529612 755216123 980410081 143749801 490964669 9494823 827433036 85440890 913143326 874584990 891094336 715108300 565135952 339675212 661393536 292473846 35329912 845324202 729407182 194066510 972685181 680992195 411085982 293359058 441527046 635663323 497505784 732417155 7253062 105774691 537007551 77047480 324069352 218383194 162649104 886894040 982907562 907591905 320962487 718372258 766663795 646269457 209845529 990814290 255910887 591995926 207888716 96093439 427441074 639896048 525874538 925191809 691699586 122070272 385517856 519355649 28004595 825677748 942152093 325103554 586828675 535137655 366184358 777013084 569094247 909866922 986593470 87680746 453718081 640930882 654465476 571498987 248443985 348163312 192251182 136587116 848857990 534481721 827243231 741950054 723491811 139073235 90635812 649232076 70416147 250529680 758028111 771912588 576884062 302859836 559023523 810218069 719660938 122207020 29749738 775435685 931833052 625216291 644255287 740427864 264310714 772832105 596369535 86643905 414202931 587691718 469924661 362544362 201897378 676876339 689372827 665944398 589350084 158029777 369652200 23693209 631787856 824506374 239765293 23628543 680896261 606028761 967524184 378758816 336231564 492427046 873124446 688965397 946958619 372510899 891150542 465592305 202458178 988347189 701110538 969089311 685526777 867119251 677401206 484065130 81325919 934714400 189045718 37230792 560218049 530442380 40672284 884910010 86649700 691945938 408105809 327657032 99782752 840988004 938799666 777535986 676807956 585136 198386086 780837552 91116321 774180538 918723592 944373460 651627440 980844287 746783836 994820068 236824920 32325878 103841250 522980506 347912381 73328664 989173237 71971244 191892980 667071693 931221096 66456120 169865222 664827651 559232549 750238408 551654598 882735372 836103777 970568028 12067483 931549420 778898802 381845900 633956929 876386956 787798807 794946856 409406458 903585388 473410440 828287163 114077510 559792866 738190097 365536647 244572107 314478569 474317886 498655240 899499918 281085229 344665532 910737020 607689607 264465826 777117184 493502642 32883279 715656204 357031269 663019623 442778949 305917009 182989994 314870307 344033745 916124968 903957562 294003804 792910256 679630506 653382298 286536992 864955554 208907548 399348300 231088910 393874268 484268579 227354864 698976532 767943573 545962178 981600427 720874491 83722858 546528576 106371380 906422107 675292442 479921436 151058805 315354469 752472071 246463844 640599696 15918666 526612441 978434792 119137476 263262801 569057070 36637429 439280952 488172348 662571992 877760768 68210940 875061965 748189704 231471973 837890011 958230953 299861025 523089217 864063427 774922616 12257969 15977907 986449193 211348544 321405784 32497702 705844214 5027653 448004992 441164918 59619299 286637510 517574645 818799936 794080601 660361854 553734240 653668885 912520131 707509317 648244219 740471561 678318494 255052733 696987005 123255046 81171635 807339546 370667061 362579614 101761605 75126240 990062452 918439494 672267577 541053581 485277149 16291117 520316575 198319466 567619967 152620911 455251473 854779258 323398224 580852632 105739156 102272201 760008947 255680401 836121893 467833675 668023250 797818002 319997671 172225358 476727430 718383450 349078592 445811278 819276999 837747409 977848746 206004407 654890718 281048133 804416280 752223866 479888595 235519749 779497414 925344197 392240160 408477296 655787261 996734195 673079687 670598083 876658612 923573643 413446896 416912032 827905915 824553991 451630256 257645093 914546362 494427627 734355667 685060225 754698843 114952431 116251861 772335278 557032750 253783542 327815555 661743325 580758728 203562512 957758855 709302923 606139746 465804228 986062225 877788518 326509518 603066519 985942337 993979433 831830533 16793566 457537743 186003390 911625173 209512328 917137473 208547619 703464078 83732611 600577004 548623906 173974641 249344305 353751284 475897325 588281129 258916855 766310702 322826416 447980737 110378680 116408137 141074462 948091076 905099856 820914263 617243485 640938331 552490078 555822065 833571320 415563978 678363522 808338170 263640851 782558078 748776111 804128686 399373284 903179534 33129779 18863250 260303526 433176624 682052987 776005578 476802284 245116380 56481712 86219032 143564954 123782722 355926099 959361811 503542603 471211101 877568274 458532922 959604387 146621826 146728156 895030440 976253895 286146596 387778903 939729886 338029275 878324159 703235192 488661340 328331851 528978080 966090054 145058344 575566815 799870538 954287728 137624919 949020597 360325775 143280510 320968699 947563065 88812975 611658833 503091502 779936090 13852410 111686285 531753001 398949353 553090854 863636388 306711464 881699023 55762805 641922989 306311621 972875496 266698088 432363697 453662896 933784185 704200788 137335151 917115849 795211116 281175306 651467992 401942729 129443571 301626869 518147871 428181782 676813167 418655929 612213050 640557159 177189190 861958494 829959834 632805688 789837492 226165768 695264501 636239797 886854656 554671814 89798033 249985565 372685023 830505167 532641254 815609272 36893230 684500643 123569568 252436268 398872062 596445397 404060286 762961075 340430406 170424414 177247635 67592792 163002287 839495014 932258479 921298019 529941998 82170423 28215716 102811025 721648525 514707483 768634497 198837375 105593938 587824389 349878063 196569938 161675099 395398690 937307467 473426950 663872627 828056798 161659469 874274693 713837324 658460653 483405456 967007403 151285342 216325887 216945399 602733328 589379895 970828431 755147079 563265513 246124636 70306094 917586179 795508166 368300938 661387130 503922858 806080739 794184643 54158242 595261594 336852130 795688071 409842362 402855201 176267702 46858344 958258837 448246192 883374649 791453475 467979810 973024852 376999011 602474481 742513359 251383903 849841173 205174739 76831258 520543740 678143776 498981590 395430699 310522648 745831806 549259903 491740762 505190184 863183159 985666785 708130683 900931399 465477863 534521032 128712766 131398996 290408257 576635675 744896535 551951100 788723508 590142193 847740479 535855204 380163324 504294374 894580486 423075928 744054843 770944941 230389435 960943500 358794613 350826357 387362942 247524040 705362288 378863164 922036948 173683994 247541274 952137159 209635365 716666451 958277143 58368182 168592561 417187673 517348993 165839472 328183534 203124385 548110035 597450216 79895229 667884809 534944248 715566929 513430454 474191645 375420792 399909421 449957203 53873363 884987203 320021423 934369214 917905790 649774649 735812671 791380684 530261829 578355381 579813095 379423512 500227696 661183828 926711499 421707908 786492877 369243540 354865305 885089902 740981967 78662398 681898619 91413226 194937325 498245792 199318750 443128447 429539315 227626154 116107936 551868143 172352749 526738693 539502453 346811587 877508287 386935309 266930964 210512155 353448782 967894004 908001862 48817783 320174405 503274201 703197504 648639266 619160986 124578688 671286283 971920825 117577516 76010696 82077649 974918604 884700938 801063005 407584694 977300163 214209091 100753891 338543520 960484087 839550161 315103030 278787056 867039089 51684311 265388644 149776095 349134012 200598862 952872108 895500805 275531056 272944324 193521426 74900138 626940434 216485535 713140061 27969836 324200594 62273559 576397985 100418071 759749452 304645543 769926717 910952300 39806859 746912949 992733378 676925144 870381366 214773242 837695942 220345101 742033443 361701741 944721920 885233225 252072798 292557914 465389057 367539998 107798843 28025226 590015850 405962214 390736315 471275571 278423692 218311770 599715697 550849252 636106734 241490865 447248600 513327406 496690231 243482167 515814515 81517441 62310760 700134503 489617500 472183678 971418578 574008989 279039608 398089230 162947430 117946454 48462798 410215654 207157197 373940754 155605200 516465863 345786324 407448612 507798613 619725677 807252961 719481561 441736575 581473960 771087535 577850737 858486100 305270678 216973986 654665960 947748338 220241554 926848335 452446963 313752799 120927673 662407144 601094119 851736839 374662312 108621507 931719022 459477959 904380168 412494606 846243027 986818031 318183025 591454298 442714806 576879369 818239335 465077031 96733983 507495869 737044976 711695110 852726425 171916847 291538062 480426008 236686108 881534784 666537152 675078727 632067237 947945671 660961837 565817073 468082690 419190310 293014644 379915222 960756977 683120203 173693325 538958042 259990063 516387287 464248810 656606955 44160734 700504113 227944945 463924067 690866646 325132267 841123135 86551486 952326565 33031252 108120435 298749733 198969831 203967839 532681816 849713751 134552348 815123876 532420148 770213222 225042414 727355149 340039531 710107307 196228006 60405698 946376622 155247327 866126654 472876874 146573425 442340228 419595155 33071561 542657725 513217455 452635070 76586876 737100463 944980083 277511502 971448938 694462519 692256334 562255388 648833567 512364532 346416986 517569341 97186857 197739902 657090247 596639131 725831247 590636684 217255560 879959934 192905357 113727238 207157318 937681090 42174166 14960538 167766131 22110900 811952202 779418436 576650116 21483821 769071320 509730773 183151377 557697184 227321747 234470443 700807441 702796268 355504326 891514590 382758714 102370814 51055496 401119910 192101008 396709508 959370922 881587967 351212238 865999773 753640962 149889228 788690535 175819753 645616713 329528212 543960555 910099811 802400413 237528432 32657832 513707201 813888339 407578711 65032225 241275561 72406218 918358952 136516058 484709160 890248074 201971225 821337851 922189118 648782858 604698886 139597548 221830227 598181166 262546474 810570495 94074613 539032694 32126996 143869416 938011220 994785692 714920169 960473299 27725003 676409719 880807815 511939000 253633844 672862523 199765990 951037285 400461538 911388783 758931776 59314846 38692322 376458233 635079074 760893707 1666589 37660446 90516928 781614409 988557486 364122370 383213479 908306654 290543657 622583416 884911107 153394722 231556473 561495505 602382537 553910562 320554832 787156093 812673457 882436537 775071588 225747339 506551621 557441709 111119831 54460995 502110923 362217953 848446302 270354968 226984803 737830061 311575924 360370162 786047357 91432283 926134128 469113997 142495819 681987424 577156339 869852937 472490459 19901213 15784429 958752991 961991876 3521687 575094327 347271100 573000866 469319237 626897467 961039595 729020839 59519953 159322203 793483789 250806755 544254403 989940799 827966104 233479224 863481656 619262247 450929135 510392064 187961084 174030118 577374269 204987549 459273807 407841082 645887092 666014932 53224904 568933068 22355588 708418698 184915075 548159928 739632509 603544705 852715657 647790654 989069468 362061266 195128184 86443237 299143450 549747304 962361811 749156457 104957219 400133910 63996196 879255236 755071071 807548465 136610487 900232670 912864776 387433573 508194166 962835928 842065058 77020363 159716593 194466117 53517858 594756677 213648061 388665961 912964848 511963732 519659353 226893276 428268375 197591622 202623514 680213791 619748292 272625106 846941543 622914918 511892863 91503760 548809912 441044243 293077930 286267335 787961522 413033669 432364733 799761605 677996864 102460121 616597371 976557640 114431792 997096662 625406154 770999804 121560959 204440179 918124160 5772447 296271257 335606348 767694875 41869343 825965430 210173489 15958834 343273207 673008446 559732208 517372449 765381828 841512374 43548832 502523423 154717125 708955235 960502329 561357048 673608183 456814926 658169700 394188939 19037752 764914291 620334587 639275343 284932664 617491516 219680035 464259319 114586424 946253669 674490015 735786490 779520302 603087529 540412229 166963109 421523801 967327486 220861847 963313156 201901129 975234331 532153983 992910591 304163906 32045077 743828474 369101541 842286564 278300843 350002520 139402912 482399629 150847530 84392221 616980996 114709407 805903874 207121712 403542148 533469593 485324868 408272812 731961944 318426489 727169090 727766275 406918622 984330467 580695632 793535530 50353703 991111104 351146880 409872066 891706868 829466458 317342116 816920489 609952733 768102463 829073382 78219958 938168510 285063839 276706302 42029017 254920410 235297841 53041066 339691327 185181635 140656120 820497753 675722000 527768930 434026415 656076176 847737053 368842186 335114604 792406358 992771591 972189050 940459796 332343924 276636792 522058762 474526642 643747518 897595385 926860821 412213223 982374728 195893271 930675099 345291699 246123879 980389308 695247238 340880019 915125641 328579994 326319313 429273609 734234180 570620758 391265004 57961053 499251005 655082281 537746611 215890232 494809632 195462792 645501038 434271721 939935103 931993486 176111046 106089211 203857623 280312130 228365082 354842916 187034348 55685166 557683998 735770922 905293006 675167802 31554924 662934929 823636233 398458202 99268775 321590589 619406527 61973976 978727482 790468303 797589721 713412908 903889989 413178387 887109668 948674531 126042802 284055474 482835179 542720451 72791983 771117093 964236711 403339876 517635110 363051200 656396516 196719943 749162980 593511765 858920411 733908833 385326235 895438535 685125124 364632058 906605682 779656595 113061483 639895966 860159213 476852799 290297374 973124493 874430472 534559508 770123691 347822943 127089774 140028933 619949937 13151252 795061823 717150132 533377190 219123910 50408206 458016488 658512261 902301902 985261436 532144115 680445888 555360456 104162306 902864743 978468147 352355395 983464137 50658369 696277875 999109552 639892869 864025817 996586033 702824649 610783974 96003080 648376411 494043790 187637271 201820746 110782114 211760779 295253393 942431603 650176145 836719485 579283453 876202520 15326844 184982177 520484870 380389206 367425856 221342621 466740657 40516925 803759372 576034611 400290507 891407819 793776530 270470476 554525930 340761606 599739964 647157022 661575715 855473720 508589452 998265574 59072805 66289606 798899042 481372450 931547070 21716804 178845968 221543975 731078354 523569416 803704915 791857854 388334559 266287673 317876791 358644638 344117132 389610434 927904214 469242304 702078875 982372418 473807918 993504039 114747622 590910795 263079044 185258611 602984517 225575389 368854285 827392437 48696160 385643297 135668684 701127094 1634159 187385404 42425732 667026450 191224631 277276362 481889257 495035801 286314599 683360220 434228251 832188984 776602639 506305294 630092259 327224325 71103543 246503214 736568727 542100005 210039055 423348950 20395136 528806102 553750051 19585691 195421059 515636540 964173269 711053840 33003069 242315655 370414831 595497877 296278095 370907822 797292826 11519943 411051346 862234476 58930466 388526013 831428132 267746159 541846312 527267440 22271525 708542670 351425344 847805433 162631816 23715807 8795608 935808069 778098366 818151654 354199462 480808080 905489531 58160823 700219244 5545647 758264791 204551392 103642424 832863233 494888878 275902421 823076813 241303302 885577813 228440009 29279761 778642358 32924417 236166956 994167253 558055567 220498139 296453583 308654403 170944779 506583071 434584359 884003437 733872040 793116743 798337158 196340382 96829325 674814597 253206550 256003657 764017091 304101185 162902462 715657867 384923242 74534659 550726711 711969760 370876552 794604620 847922967 429088205 971954536 678164472 741278992 667576504 662969805 545192147 359857410 121501744