2000
157301415 160806925 46958237 616191747 583204936 774422443 884082777 467975500 593365467 692410185 726751221 883199234 887257177 796606567 593819426 989951542 191465755 388744876 979490888 399682839 244525609 881397861 905448955 579305595 623256483 529774116 398448354 434023786 586812581 627016074 729599803 597728880 378301474 45881819 971572984 586142878 877656056 937424285 740547532 23570418 246477088 197846287 18320307 628374008 214173397 219747821 535883214 389921701 93422928 941356275 45692869 779967470 393137462 500840451 566139642 756653659 617324309 142482549 444599750 112599713 718775614 383906759 644438004 250979089 434977834 616147023 993077899 318499994 305013007 409740185 230139136 147340233 559297278 377227416 89078373 169132330 700486906 454044223 344758813 866069524 391242250 747498056 6162875 636597710 549422915 403686065 404229938 920244619 702040830 266525169 246380748 600889715 734712651 742249885 941872022 438916009 811848485 179717860 708992501 381828502 897503861 956351517 768476422 403435892 220882631 642240428 264016651 40969699 7794748 489814542 562383905 800106555 346679380 541976193 116230367 897650248 40126101 48002060 248855729 510590725 438305286 193961469 913607885 940310352 146493408 85673726 986874511 637512779 462517496 848230365 22215033 551100097 915652313 195628714 296815994 688028445 367107503 7403918 826355477 842382168 561415121 892392987 6626681 149455548 892519951 843910194 15847180 596795400 991186211 392305993 536432277 524764797 444610848 760703896 598823025 637408192 855419510 991104414 965058312 960802874 738654286 519036379 212041341 415977756 437037987 12748867 698375816 873446466 709270381 22603469 283811044 707130675 519295214 203782578 815302390 631066166 542923472 162733234 718471168 59634295 812728282 287031311 762038714 923440259 706712775 806545019 115153966 204070631 463332035 282950490 700940750 718567515 382562758 767356128 496210172 464917743 751555227 720413509 34583701 440562413 725343142 858090593 731625307 465116713 105659212 820106117 167205111 650710033 263929471 565580970 747856423 527440225 475024739 319639952 816777425 346964489 372028502 988591553 989922802 74903716 16023690 919815385 258472236 609675249 746222596 793832842 957276808 795694511 682678658 21480403 516668505 654090654 626379880 900520919 530374593 297875978 104563136 927103138 750526612 643655644 751199812 409685334 719788639 462048565 369166147 956230759 581076473 341058466 815759305 535027285 535048879 439278658 925291241 629311589 592893370 17817356 670836713 722607184 363242588 555481324 992359739 771457567 776402676 582783372 220508480 740290416 879993244 23916185 834854020 821145183 805721661 141352042 700880815 588768788 459876895 465658591 915769523 285710524 382509895 283449547 653508219 629985890 438746123 124820856 220785571 55135692 867745936 642685466 632789645 878541291 310379890 313515262 961357987 861006309 282998537 732537457 882695124 556085626 23801941 507204433 338421516 733387851 535955795 959560927 182774064 878565642 656758216 564156956 849426830 224703569 823856643 538546581 867071231 257238197 824793792 929390255 789392036 582652204 681474266 484582470 814762518 129922462 372965713 915708288 600707848 646670421 29866026 221375573 19006857 502554245 102009135 252197396 148307020 329920585 720892185 61064862 26385726 950763367 742576458 584902405 5225721 957250668 805075473 406810711 751081498 740580600 181011934 650622834 813726162 37220509 417325086 751225844 882311663 553992431 890232188 16370375 480032849 699815228 419420336 593744101 365643934 788906550 299117457 542941409 143305855 542152959 600698591 61193462 458372669 563017658 660653509 279414771 481052848 742774020 655594471 369552705 783925677 538548786 714518746 26034846 44331027 666716677 804013130 986699495 356106588 598979144 383504734 207288196 428178724 727854784 346876783 672212774 664828027 743989737 677859818 94309408 322473221 701169630 37758590 335491497 542750301 590380681 85225483 810988962 175264996 722896715 446274588 342687749 70677927 113628635 453060048 756057246 337082164 291226668 209464566 467181230 79584766 689746980 433489037 835104384 890697203 47525699 161264887 881669951 518678984 358304785 300469132 61463622 638044547 417870262 424579602 470412403 797961563 732264605 647182133 69283825 174075163 652532828 418527249 651475465 948561936 784252730 304560312 351107465 26948183 328754973 565903335 792006271 923877062 952322381 672763765 571544744 12316699 825698138 521735352 245681411 28435506 547623628 400543259 668118404 775247811 527891643 336758193 537074375 361956502 454674936 983920597 214454279 483764125 760766923 246582765 70758821 91990899 356477350 726500003 58503163 695934529 145380565 578180355 373644859 6050130 527381209 325727941 378693005 793061481 946406579 552954108 999121711 655284226 626668341 168094671 580421768 671625042 994380789 266241166 488719780 459648254 196149295 548466122 384518332 656195793 383182693 645325542 948029691 68338355 964930390 104236039 62937020 221746558 330766870 204483680 393259937 417296708 625144134 210332857 525850100 84586496 318211653 228280433 788322673 376317283 136743917 11535584 919839857 625324004 152738554 997086894 758200783 573481210 677241946 689766001 661059347 250771819 567672765 704809714 985336230 816479150 903741970 499307747 413915463 753772372 881594190 507218906 846934857 604180187 526227315 837645342 566965004 773561772 161029580 616217718 42048498 206321467 85233500 64268005 728514709 824008286 118208835 608744952 529402408 661003233 564927677 603473755 925753334 133012597 967221444 392592383 320446000 194095619 936791264 544311723 636195736 368322540 320042749 558744078 652631700 438603297 501714860 308606992 144014405 668720151 23355504 490770373 936398133 160191527 51590849 383351549 851515322 129616378 956977029 290019639 897055923 635201064 74971164 976830008 417896926 48891224 96272133 737140131 255315617 439137567 815392150 466796060 743779739 955370043 778920995 317749575 279536553 292950216 68138440 886056092 174368371 598570426 525231417 264259928 377861021 644609188 259262472 534374269 328994323 759211029 486978269 132095203 543009817 681673624 293413894 773387235 158466322 592864979 406107273 499978452 950956639 442284356 437620177 632526647 917490841 566407148 805315689 25332025 35110192 442898546 250815624 345259245 714984506 153660622 268560471 138642543 608354256 264807237 21780524 953893329 991742536 941515546 82184445 604543965 420554871 261856126 506097342 659906842 319622629 458659918 766684919 606794767 920590826 636847317 756830316 706356570 383241229 721817375 213232444 567628193 621343525 755385504 461858668 763835104 522260345 670552287 973119555 656531734 438239616 251458806 624952147 935246521 376371939 581829288 379402731 246051302 128436630 570279644 293969468 381236525 88088812 992299770 706657581 854641221 659019785 17354274 409090929 542256234 142022053 375674716 696371735 210095092 436063099 571196860 106672548 629989961 467400125 521402732 24317710 100160793 497096758 673177578 946835027 972200014 678784537 303739047 209578149 141709783 707277213 459155809 800644333 640551255 797213109 125614930 734791447 811389731 672095908 119887872 152657536 618737699 414365884 868376159 393152458 747115445 705823639 106257788 825693259 326139878 671907753 923178771 329715686 275019576 66701519 442389203 713927159 118960953 508139544 900036866 734311781 776122205 260984040 498873250 534185687 372278152 411058935 902017066 624749658 318469117 970489408 992596734 460955983 83126786 504965976 540601447 951356640 427500100 26373220 657873509 632920934 735643676 73706264 586380368 517610130 772072552 114094502 295806670 657277440 201829509 451057882 376544605 555844259 433522645 591954206 531075504 696227483 762075608 571227788 575737107 63967053 733399553 837226993 868010488 122324775 315286539 353133674 238686923 513060295 385087315 638228037 654833073 65789650 705786346 473513121 448738506 390191957 361618395 805704847 939738911 86930215 152699291 439526756 762310845 218991927 661255207 814396214 901441856 785131987 714578908 408053615 704221770 281573457 359408126 104709693 25580968 978307950 627396159 852019190 360662334 137508445 895000331 729198329 463216590 332551457 666418157 853052339 185767194 359474829 844495656 474172634 151962680 576380826 960670887 338934402 41412207 950023292 613101996 855786739 433983561 551079224 815944652 179052297 304361714 675584650 748897900 770465478 961639150 994737051 137034377 54862898 100078127 306112163 298294177 931210263 932632436 110892475 883346741 882044044 487449672 84464271 556739861 324416053 384828646 723520397 847601785 344495876 463501469 811821745 496813269 118092159 286813394 553646842 189036851 268109276 485395585 616137367 965165211 81683418 943643351 513397588 161349580 794134887 185950082 709297273 96644668 833313752 714601973 491247282 718786901 847300214 457524183 276968848 891990829 255280369 994120747 81081350 116974921 173478035 548907894 941646553 652759614 930973788 655731263 713518945 466968801 4635986 877806237 852637458 977611656 668130910 632669310 953883944 793399912 462159393 981931053 371234545 174692611 2548405 518974143 299994232 251503663 3210674 84499464 20229255 985019344 125334483 695249325 513432968 870567953 918461856 2402794 588805712 841308536 200413622 617466160 115755981 286247167 64704396 275353623 806877775 833805541 382754516 205297594 73802089 122528741 102140729 175864209 504729798 306276388 828086231 681459068 811278113 688906749 834931608 592736471 846887174 778595436 598459522 152680528 857627488 639776458 343535251 40805096 318460318 702461806 82946439 994051891 747193261 176624314 773148035 768297650 132657929 850814596 939502209 639382004 774171811 708107389 85557143 497894422 503207216 240927118 722705869 742122875 115740871 336092757 429923852 344775675 4249434 117450166 156120493 690605041 203773161 101333855 457802785 602385484 103581952 337859742 876470711 898257548 168345672 266874685 228293135 942873818 723681759 420175808 428939423 842163968 409550506 854441457 111838933 43987801 27333474 581200026 14987806 976040057 906504655 31365575 712658817 333708674 52525063 605527262 602364505 214843303 897518115 504267524 671831997 678175246 853744184 738693170 775282367 425985168 223780467 385701070 77810084 414635931 19491424 346469167 384366824 825792518 283334014 855675757 845528289 353691808 470446000 717062955 145518175 897751485 91169860 77626520 164085550 810490606 610764872 467555643 789206956 413756619 494090688 749580517 366990018 787441931 183058111 445934872 564435464 783070110 116465723 675845710 835987177 166926317 844068444 663925028 149378979 944258122 693198984 31190317 485281968 604208764 223495629 277881371 992513007 179879009 372969946 595650617 92182802 159767585 665093120 16626801 386558584 26916182 182357091 371476974 269685974 656415107 861510010 117892623 943998074 469728283 713760751 725607965 789453939 962624740 264312260 419777282 223688702 515734404 954588086 417331321 190045325 700327919 417109523 121483313 706526648 29306235 439660442 924393186 524566996 575202440 886777700 322897328 317596321 721662690 901043832 932443162 914847991 104720424 173219898 99510483 177888562 748489307 424079463 245577175 333685294 926185497 251456912 890918695 338133947 154267860 274550417 835676133 884857313 533710453 424675310 473955277 900680447 603788649 904037552 171477621 605504512 362797918 717254781 115484242 811031160 118959924 935483942 87686045 377788180 764806720 722654137 484106988 887915750 427074615 397780510 805947661 250542062 960350326 562410770 689943422 840968602 722507867 372186123 856600265 593435849 278989457 472412847 21564423 457313158 104786883 844621784 475029262 21546352 993812241 53829262 928449410 118208895 578215530 668999876 789488521 748022608 891112266 392209392 415377909 387020926 417079686 944910884 645161244 532676449 776396613 1918890 524331104 827531017 78929390 877548208 496569848 335566680 833206577 753746466 850534840 165476140 912424093 570970448 206204474 408157736 886250571 590066321 183684927 419090706 188643451 170527657 116467527 638589331 179306958 741052637 160115528 196323678 970905124 57477048 528119345 55227007 924998656 874411588 158665561 954348727 770219033 813955578 865276134 241468965 796006980 681433870 924743222 72755800 431213219 519022143 56750515 250350998 186545819 802733752 345376820 161370479 542359343 876616240 776397862 558250622 703043157 976648624 596028512 77619652 601560051 920377518 725543085 447130178 823146090 624523934 436264383 629099709 545449038 245581372 728236095 759184091 2012135 129734071 572243300 424175720 836074800 915592953 647375547 460633763 925901154 477284820 87788320 840724752 160184893 765470057 888368272 222373358 327581488 436893678 365408556 297602564 92191138 94747213 983507111 866166572 616066187 371924776 500261297 265517699 958196859 173730172 420768037 358465383 443792445 922890768 114147400 412134449 597693891 746889640 593422654 591326040 638357220 489583163 271174511 625799321 7715275 757728978 230789886 960416759 661080511 4098241 841583036 447692038 934454000 887560428 358606902 890180262 488081217 620697712 740047851 536108575 135343419 475196758 606582441 131455699 385445204 60311621 89008134 599008133 655670667 981843603 353270740 749357663 733377529 140404382 238308228 920212609 625352654 148426444 427845326 345347061 994336855 589477737 164971283 256795117 142927787 879933815 37532947 272437942 208556644 279683987 847420599 959507487 138033480 945891985 432267919 84285760 720837639 494210641 294914299 267963347 837089140 586415207 34005243 710044999 7788737 294498577 102583280 95419670 662696113 31132548 955865241 529401448 665322178 382407458 605652250 314955877 691050737 437838653 592558222 452806878 785593076 41926704 983250460 62268622 207295849 221577762 499535144 831558790 608957066 927412989 816277007 43838880 488971354 711421916 761782091 979024792 899616439 340654983 656998529 265598946 563651419 69744945 994157581 809111170 752249058 650574634 811502237 621189029 640753756 407467085 978024328 110534414 777661535 300237543 197493436 823891853 477811395 205251181 396904812 403191600 105707879 571825231 549216754 869470043 843215737 141987043 138833515 484603526 593554236 871730786 26051420 432435475 746482539 31466945 450356081 105457267 946201962 9820179 310518933 556800992 997153673 11398905 515581941 682679826 429647266 136870110 739788517 184618881 714465474 748212079 369630420 768455934 505669885 625515273 721670680 564795827 794420489 21131845 760114715 940451976 510434797 177821952 387271375 908562754 985548334 244497493 531016726 193561942 112732999 236339459 675319583 440970403 650357625 901792347 609453474 33772179 46158021 104370548 423554743 403633677 870864993 78897589 255675200 245076574 624898198 861471984 238733683 438264731 301246922 51394775 486459471 933917457 996967409 364554809 263156787 642570321 934375130 366519774 749229381 703685385 362866292 381659771 388247113 664751827 374341535 179168929 400171821 958374220 794736596 359718677 219690636 91651572 759729556 840296603 832388479 734602384 136152225 406092864 338144881 516987219 858096785 215191952 666155108 267209930 676715527 796526557 606819808 768345144 838288182 21907367 971532781 595833811 45449805 809353586 870578737 203333602 488867403 637333407 834741938 494495343 594685527 535967467 360742720 572868808 143835845 313188105 981831846 641756698 226539763 769751726 154060268 952326336 724172338 985287786 623842407 433076267 35784149 52407382 331911478 310724085 755689669 669936120 969798170 706458402 744896589 609766952 288481516 625819795 273990864 329562772 821887717 446382154 475938000 348263799 980729123 931880648 461760149 620549436 733116063 707952120 531084673 66734082 254467124 455845766 162685123 67923964 257943286 272341481 618205403 811375128 177608426 788498904 675690691 590520365 475198049 93859913 235213940 997683688 162518167 573326187 453149068 881103603 951712401 82229632 468155733 164862318 420453306 560378641 532495222 557475429 602833945 92403500 255886927 491057419 48365654 584547341 690416828 644740196 27896335 327666229 141005578 290227198 307999245 37119763 732237951 11600252 580366653 150556172 897018539 301866048 693612957 879908762 901245783 28678142 100122409 637141850 183253871 636908433 232493442 81349707 992867062 748930606 868356080 557561650 113095410 23609045 916024178 600840678 28230788 262458773 373309719 444132599 987173556 827223780 125469108 67544921 580753390 525539237 653260718 779733222 171882543 751833445 403899711 74027305 683180657 424263672 345878668 40801008 741632753 691939001 666910368 781906332 530608839 588091717 866110012 316017820 861833747 973579223 149418911 795500311 853782287 119608962 720826023 877572813 735372784 847365189 863157279 553288134 862066555 174262527 517797255 265663986 93470684 882589340 232199736 479784807 535678098 226339765 513111830 26004779 416786011 922335531 655376743 82632311 341759798 438175664 865868854 751223925 307459160 927097247 722849198 635365726 203213384 994016940 875653537 52693396 974797926 994397134 374354483 535261328 941300973 366795124 70505963 474654612 922508261 707994482 798940858 207934820 762198921 342128134 775869707 531288248 291707076 40965252 301439444 175892912 823119784 944691759 206666973 148108013 37574335 766947951 107586221 911677279 281388779 402773225 941248162 144945163 477165875 91030080 273935495 941720258 808432663 195997134 357688249 332389466 856046955 985493348 40784189 599546142 974694976 281944333 887163232 626449500 214388040 984072743 632586245 605408786 220257212 682471155 202739203 235446588 712188457 589509977 856928647 927044911 844268797 87125463 645720850 282425455 174158588 552880644 54643312 962900220 527161003 815887566 409765359 589566898 121744096 693694115 863316183 728331156 679694842 980422989 830247267 635452012 558114151 455770513 433174074 959673810 976897667 226534897 533690539 95193944 385078843 226364095 62500257 664487536 181218411 689747069 946276833 172042555 554658439 993701771 737870243 454097994 139200832 203147210 248294772 945845728 39763910 900108745 158272952 984943221 377637183 664019245 609145024 167876303 498634323 993698091 829313206 540424433 115947791 17591665 496127936 136721998 431378298 621766725 669843021 556246071 190470825 391026405 658317767 510213522 247023748 906349804 859893279 478636552 135963295 229161032 449489296 518797673 752125166 776540974 503040199 740604653 901337133 392134885 82203556 146990811 309189635 999686437 720209673 843031428 796665512 994077360 706690803 153342963 56318695 841207869 608756808 491863737 107333246 795410305 584144545 88275967 648234692 448803209 177016093 792050383 837388843 326649503 842381356 715175989 319732639 240826122 332583021 143657972 625528953 515487671 323411234 332277470 722381718 101576500 188311667 850318520 494526980 628323479 886529148 624627174 946818990 893795071 331377604 799543556 833529433 272980168 321833574 349005487 615568776 31769609 930538551 11987438 154425300 523939216 45226784 964212263 184501103 647326942 152396965 686285601 287203189 966649212 333412058 902573351 597239274 39809798 615625395 123879268 979234209 136641517 501495593 110522552 476447535 751845417 368798306 879822124 636672980 10795164 627280887 387857581 260033559 559683738 10511592 658401582 99501682 495967215 918411522 436687857 69040236 119596428 609671021 453341761 148157330 997379277 406646697 154872532 111693046 82097881 673936635 412685952 507736286 934293350 755341271 661756967 198240398 628775108 19882360 750645042 220142637 288852492 248854376 383625659 54550826 484685091 578441510 708535527 895805804 687757825 529921175 904478897 149296271 46824671 248782981 973858427