2000
539898218 974386128 620906968 915253698 787704317 297603939 296178604 986841937 154378961 142290685 816696184 964158139 4829428 442772707 657893401 480182613 779964894 330226251 741344249 948232591 397657418 369556547 613379166 137049598 982616731 491226254 76757293 453545371 774159443 856377913 2048479 755780778 788664714 728919639 491812734 806825678 497803820 93815529 721032146 337367476 589912789 710541850 153531746 903756493 767221965 153510254 46118712 687926069 100043100 893749322 362601751 737500031 220398988 999476221 128745057 958806561 185069571 200823148 27471560 531149119 967992847 183348770 804346674 888137744 455233214 232984128 656875980 436738615 305740696 697923735 324057749 929047584 197951514 549579465 177714088 430557416 73258726 261141778 300338919 396041556 782982511 100606886 348746271 943036489 243783622 378433871 372962586 324515175 946299156 505052290 785048717 675542637 351149239 882601436 918990657 661461523 500897390 720248409 950693720 411519809 84278723 226063581 218732302 89952136 562883188 561702719 239178314 924871482 231269218 118882285 628891280 59771610 86412973 992455091 372692730 189621341 412551264 275672671 193517944 765517954 473748792 488352076 671733421 767417684 247252891 511944288 338659291 90148404 784714177 318312940 27555875 304037462 945144161 704149498 378436329 840427320 165606162 965335460 101216851 549699859 390622040 215493754 429837161 823988724 410897977 193544218 445446260 191474559 21065064 190156941 884605908 539537210 206578959 453477983 10816089 469731524 563256211 585298025 638392811 420891553 560960589 785395813 557974580 225990807 544714296 58360975 134442502 207188384 444447201 130223915 888708833 898515868 155535857 752925578 920081795 963472915 12219844 863973311 227175307 392564813 523732550 479814241 391640731 577859077 896340656 16709578 406138775 967825639 683345780 567041021 249485989 232275738 750381697 562113300 988515889 234002154 624449089 878350063 271588158 892006852 45946451 427383726 488311210 260961393 918769547 143104904 220421315 128987425 113364536 962873240 267318585 333101626 264149219 558472334 344648345 436452665 906624731 55220630 625871925 167163973 938769734 616131621 852429527 784814579 29445364 3072331 552766989 82857171 25350956 959566788 452909945 457830116 301092098 692163767 87059313 824534957 494056700 596126588 549418398 616995700 174685270 111869920 684482708 204933490 741223172 746789382 853156108 30559689 307733344 662047259 517910636 526647099 48338168 884128517 597064225 750551639 9862841 885038442 781488283 827781339 737264792 210091079 417973914 433664062 627811571 93775472 346861940 817017073 39815796 489894718 87619825 438601038 502640695 506170633 137691255 25134777 109992455 16353078 516067973 192567255 972320282 37349907 993845394 181306912 538152274 284171303 899015085 946970470 304192691 166462906 283793161 739123092 926143709 543576173 751157768 757394026 586343561 761455541 794240217 377533578 37875124 108210202 206210994 103014576 493729461 772387209 360750363 396851123 314877433 707702397 242817599 338345418 668053426 97192496 152148249 733798835 469897594 904644691 230183456 617824407 745977616 831038115 877101250 23556686 187651449 453141521 770528444 175863248 711251661 859841561 5432553 269357916 17937351 5095280 625683198 686974036 954173452 78986993 235382547 5352240 46001879 872735138 938874914 949148002 615709855 238638897 942571590 580191143 709503996 355608113 142360975 706155541 938590204 998161602 791070215 264776770 908909396 787183963 187100599 254461302 367375514 337257960 888354792 685562738 834535384 982339674 407950142 47339444 128163658 237080157 129925539 234992555 702314830 145687737 157475233 70502337 747906960 407295597 701975422 957878317 853270118 187530795 426728210 564364576 716557900 966341556 850698556 669802225 565695467 415720148 592289138 215333198 228750093 710723945 997599880 924014876 45401856 362713930 135877069 174422444 943067916 911372739 42722195 157522993 157279039 126613281 861461980 41177047 526032549 251097848 484084327 877899275 881796041 858943120 269284342 72027548 171938479 80782167 902469843 622277986 600284873 128185867 79552311 50222151 840953351 847162628 905719635 906616317 994395846 697227869 761106933 366024881 37217878 250113623 440864114 590490637 542437318 399538436 663144441 200724933 814614794 164579968 272451810 679048322 876012366 455900958 810936101 415116933 132587723 65310351 816762142 283677474 890812651 887506551 412304941 689777985 802794087 575124495 114608320 515519642 344244831 960803468 187919420 694640235 422389196 92216495 463172796 436101145 575278326 496059634 960694298 396661941 359822406 577710748 660737794 937981175 115404906 687792065 711608468 366603668 542128027 291075121 274560149 563578130 395950826 806173445 436769788 204843222 420854306 351213299 755273246 161654622 248866936 153357858 144305899 813632202 523875151 759825854 64959304 624860185 83402507 910994692 270010869 808628676 649290738 526706477 59049784 10212563 866823140 17216355 475197808 693557737 83122437 384759171 921438721 791112832 40360011 389181380 314039647 966415058 750841354 333962433 716314636 586535019 655334275 548739182 22002783 139447768 272270075 19317549 466604152 425683508 844300460 532835125 491188277 916782297 79153414 827870957 367385970 437110069 732213946 981487319 521884023 237193264 749262978 397409734 491901848 91545685 103143071 664548624 840272934 836825776 155336771 989710853 267919684 808940515 197492273 410946529 782172341 702814044 763459384 453901037 131186742 601821435 682901639 157099655 93390675 136505468 683847611 985614244 710481434 318046480 237182178 278570004 327518776 718613714 121795074 145005030 513074111 346108302 200605038 946729660 932631583 322945775 145820222 749505011 789490086 966953116 711889846 578164308 791893303 191808496 55681301 108919939 566232940 703794956 167841052 730777551 959362660 491321971 752872882 231292387 309032225 371327816 413475390 536877629 640714874 107409088 870382296 942586293 439286740 226069289 230314892 269262009 554256714 846326899 586755844 338567343 324376848 919819184 700758845 150288784 641500930 87870975 782097584 489127691 133551554 299378979 997173838 331666377 808777030 248210852 541209275 468525867 309723512 86222602 502852944 996838387 974480117 429087339 967530958 722831977 71426000 57862558 673389678 457355331 278907279 859825220 483221560 342655732 820052570 543128551 182154508 557774367 146018179 427135431 666703885 307293435 945812811 659263916 838504171 425977458 958575214 202098042 825954049 290225164 242921458 697191468 978141331 666869061 279973481 27669046 776424398 882261169 602723011 130511979 970874292 800516131 911411732 885057646 937801580 692920289 88370357 165102962 356679751 482436445 955927596 678001530 369311043 263625657 710278881 477292203 903849955 663442631 327161748 742487772 743224821 2652445 144225533 366913540 348829282 177329423 557990474 123960957 659125331 717086274 813220468 449405825 493006680 157726422 693159074 281739402 712421762 45242396 970168595 643492758 425894726 171361304 807165829 530395356 12110227 335008756 316727509 591888436 205002301 750439656 360477001 677584107 635584908 598964465 869613872 109898160 478804738 666442466 212664006 737302125 696339446 830254291 393994323 133681277 261800994 809256079 953045798 93153842 942884535 501504312 276931854 611871430 758376386 943258870 788968955 854190269 321073521 263978466 97143474 917729413 353703226 25178633 705511073 437382918 431614003 645522190 328755668 604871434 777757079 377171644 850887304 708334182 803738947 356623689 543966246 668557535 164939303 209383160 432607072 73097909 406596651 156415130 847620224 503704178 894237026 401214628 808235546 972533861 182851735 705162742 312881565 44064538 682016653 957572665 56589300 228462528 739043917 443395906 468911263 252586834 131209978 260479144 876815556 733932722 668785487 171683774 917715070 495454939 885982959 230860454 726916034 374599827 873214388 435652111 416123159 225992239 512104357 754613404 793501476 63109365 83701111 421861195 145690103 859711749 780753064 63099919 619986085 479270434 372276613 498197969 147693248 770046982 36266598 390769991 808583713 78745966 152554662 281858378 263829813 280189435 988201671 75177161 744068759 649948743 821992938 680535657 232892927 427860094 364461179 17905752 385573547 4302094 46520236 39881856 766686561 248969906 352168542 93572393 809522805 686837165 553756347 348551487 6984645 445984863 23595094 657787108 661549030 96954209 259564331 870977880 587485348 923581815 134023593 42173732 415563216 733612909 713213478 215465557 916100333 32255206 362591181 564987297 26767032 887135155 421740686 925348883 823715438 152802493 645248218 923452491 939941634 893577653 679769141 244848537 914835476 36655047 910739356 832134189 226458870 121577760 249664514 573416141 300892296 179274885 864029486 664934140 101305901 931035648 28972378 106893571 194718110 993256832 806899860 18740772 757006823 196105689 80057014 461702263 55241088 821298110 254107398 119513962 237053274 132535727 289532634 234294830 301437317 239634567 299945641 485491591 761129343 159978411 194377741 46928869 260055164 298035087 486302012 517475843 528448110 444450622 329453525 726025827 587017283 948041000 507250823 653735323 726947595 652004758 689747557 466054112 497059479 201826555 761458764 969461400 493296804 871724843 358221357 433853570 212732252 107765055 69359101 283220739 354469007 733077364 975558324 218358699 688978517 558243760 572310661 763499491 717025855 9247033 275358999 712210173 47107030 718484427 781553475 679096833 355001495 106109122 315802360 583618787 930502993 456891768 967910139 249844683 862639308 14896021 52737608 877605689 534268301 507923792 133967978 506444540 129673847 632143451 97946795 975246249 654630955 79032575 606878459 774875518 430716533 550057553 1212866 297590594 401385437 837375640 22334235 199138847 267004772 498600023 781896509 205340893 152777837 978606145 377661161 379059995 100669357 506399552 877903082 484981185 358861362 129934989 695457894 455174220 117089056 551878467 668915816 811949626 663586821 756478746 738503246 367018806 250704923 648095046 674413599 924547407 402362367 329420184 242200138 891382323 258971312 51112275 415202717 333450148 346894013 130473954 405085107 868982200 482182214 613408276 831059651 928654369 97500871 119185147 327385311 427606700 860386518 677244222 127453657 438668370 74029218 417665926 185929546 580551879 256740026 870724900 944473466 100106474 93742292 115729499 413334458 470428353 72476127 884633807 701958778 927390003 467802868 237080256 650278228 187760588 175656200 532447251 786651016 484599041 715453633 198941817 337646022 686904549 943611968 432386844 615329394 808496267 226442819 498274041 811758770 619479072 21812388 992992603 192236031 586903952 531744918 620812649 49779240 414598462 157315724 357893730 947770695 947551173 435172915 826808270 443157859 857547661 712622764 126347824 711655145 276060211 349216812 157666497 388768850 335227602 571281139 319276462 40330187 924528157 696875424 290561668 719561613 47360168 745461741 926663353 220858527 489960448 282760075 341408959 778178453 279100383 939076547 398064785 358899822 184626382 14465031 349181183 306511411 94652136 854678074 572330281 682668950 138237810 793445454 964372472 787913435 154904293 234457851 615653639 500469738 738503871 573363349 357629875 873870920 585276124 586373616 957786620 957568632 313524736 13111081 727830273 474630624 704288281 847173211 776183546 486034315 66591630 897381185 527957879 674216479 487215512 434270141 770122319 392440371 196321774 820045278 36914699 934054875 480528448 787559540 836247336 996761069 327154533 795661118 772973223 324512620 845167685 651458914 542715534 810632129 752272658 856429506 839062767 597220965 820080606 367732458 237189593 504603454 571828091 423519781 219093627 456062891 229962459 273088089 630263965 185923726 186537069 950593650 734529806 139564107 431505919 82161095 362232551 231953434 60072653 147507928 678162798 689325082 697664990 96359617 748407412 344761604 171133960 322638420 289471556 668513896 132837046 939872819 82303246 401611340 138645083 64104506 346079413 525977998 459085272 237625260 8238036 655794358 581406735 674845760 53977193 399295022 176229003 460737334 702810896 329291301 89116143 335782532 883000772 582691348 211789407 682310121 39305597 200609090 280187544 828435208 427744873 684804809 466863458 705291361 383083707 880607989 50676927 618631830 841266586 105607622 855469464 460770231 585932516 229291413 161393481 856258740 626104295 195932756 123791604 439562028 692306281 329874558 684935793 492737886 221699048 269921258 150884520 695700320 383121649 744283662 281300896 103831923 294856638 478352504 766267421 29481462 828903054 461747662 281351883 940017854 997088989 126272516 109688264 982897269 332274691 783345050 869470230 977028636 87295646 731989843 132461615 928429528 80231170 863834895 43159837 366166012 672179804 494349674 179532258 828786631 234583303 19059851 984430857 424224820 938795688 947084031 633019041 360263988 282583304 498339695 559771976 596259379 820445679 336346167 678413521 318320997 177035700 120144338 647164099 508179830 772819335 417834390 969546459 836480928 352632286 549396283 778209565 847391362 338002759 659626054 567321050 388199485 498679039 84854780 190172535 134736332 977532624 341529528 91580789 858018064 130374816 506284633 274054177 885871208 342320092 943889149 241058542 282692334 605789731 469971815 46466889 859499046 428530200 798479808 917837117 568546815 664024607 4109986 330295407 140807233 920192965 495981681 301649746 14509234 245601749 35032431 928413325 234769168 732983158 725541831 817958953 71663049 886162327 680872899 896739548 379423408 555767213 944489234 624466123 481763203 584654781 975839573 776140569 792769478 447321543 740677998 417941524 768589200 573123701 722135637 289167930 152065946 497217663 843238552 525730366 580925866 703359527 538208533 229013725 216889502 984701978 611302891 95787980 279395397 953230284 367934365 863848058 283833527 31843873 930594153 872932092 20275595 940528997 363898150 241802609 149857799 741562515 241032937 486900150 154296187 644550210 8299198 600666342 944531326 726095346 521372139 461427045 386884877 894094403 943352678 259848771 376100588 337956723 837529497 608065597 29911881 300321324 654034620 741029979 916832150 309248090 738728026 110619272 87330257 485653625 465494989 567316207 55816912 348109845 196702806 537437665 39727909 980550720 216724329 980587830 726546698 442684832 518866948 691964413 374293585 774151257 362416409 517208920 929265145 744181707 766969344 146015681 644819367 651593861 298611457 423213194 870678404 798826681 503318327 92476207 823122222 186241412 995736716 813213264 458911821 591149036 127055522 458284346 42688464 754310886 660879435 42281322 676439346 522356819 562070398 767298825 180824793 382751455 486669543 180824077 556548072 247170982 247198654 487560529 144787877 837646748 222169609 689757148 904592983 162134491 890382542 683198619 271154872 364092812 245645987 186163945 362367503 493711674 921422617 431651391 485952539 107763831 829851872 657773923 10146468 562374111 619125706 220050185 745843788 733146150 482685722 854165101 23910394 998401878 688683163 875412990 973745299 465373390 710366116 307379737 406339898 322401357 513051984 39659570 629255615 440865752 260499565 471031985 465252182 530667102 734254000 59887442 474971965 302759354 688511373 233608528 421862086 37250849 312791923 600425330 904547090 38169243 184056638 162366295 322266662 818257133 145790429 979581333 250197094 934108270 651376594 65336698 27823452 994390646 841885105 321081298 169076073 80407987 197391141 966801596 959923385 73438977 564407344 708795832 522099283 348081226 683664922 703931100 643991358 608640835 539170196 508942143 421007869 427107805 195491819 552795946 556955022 496757418 666529774 272666945 149143655 563684371 743843327 415997583 913577520 332201999 112210745 769202044 123309825 670609395 926526342 39146174 502052853 925256447 128602487 11554671 511695717 878618344 500078278 952644426 686396757 620088201 805536195 801004586 314806326 758081327 278756314 342407495 333357667 937172796 342130762 266589999 262388894 781110087 421572693 999766509 920080240 231545298 858648149 534336879 832694588 753840519 754570569 148774602 633274443 105916106 661773993 606339619 265780976 751996112 443994083 285036088 274808549 822735944 141883968 796109662 896075979 988163246 78894807 263436142 475612770 804293217 821666614 414541589 753035642 624313827 229184622 547325907 185949374 324700626 156572219 277544965 989147191 254897253 159391544 835605841 673394055 821697855 430560964 799098663 371017579 52670575 319914521 296282342 650596928 742675588 437925249 779865410 942465306 676763571 813481162 435421148 196665384 381092133 419123212 67717154 887151441 248293900 669246880 438827249 654848289 902704662 412588765 105867770 808372525 915847371 248080210 681067677 580293938 647658811 699538812 448055432 343875379 270740882 359057965 28283270 911166382 51337839 802885334 905287020 509259220 833812220 951114802 487703189 523541409 616732794 358958375 849695 399767199 867230283 914491370 650862265 538434284 478144190 106876515 184532537 551431305 417264425 698758193 430537617 61229886 151852041 314826977 356237272 563775518 965137938 585264066 299105727 989116588 650459463 834542618 568567722 596443451 819555964 297903462 105980722 913709010 246463507 877764580 581534019 601389378 301840405 663225839 250291904 243159095 707129164 241953661 727811182 865798795 863261233 835537610 221967901 325173606 762959035 328265715 682606240 502308178 929222859 153732971 547742906 788241744 813981915 148838156 976246563 958673354 574553739 268643354 157433672 537298988 706330473 437907526 91731634 638681090 966098039 970130648 629016550 76950811 839502608 791888195 847855600 394413713 552165157 361719107 409622649 1330510 437208074 149888489 443041828 955738387 757959712 788783116 869565771 565142155 90235263 415650552 332059432 977375003 149320226 696959611 328398656 901398771 571964918 618787159 5535096 118218820 434038157 995424581 21920258 949446467 578280890 953132409 795339901 534106916 282059299 283299111 989519990 96564086 744452887 390378695 549096181 527941632 709524611 550270845 668548418 770413577 663525812 953336140 977935645 330967348 405732623 268898274 701749822 375130939 16706954 576923594 858671527 378680171 27720711 188743679 233540056 422713132 470376136 895743551 892433901 138388348 189320949 999497023 617591438 718195706 459961181 544253970 777863648 683703458 769795987 957171422 75068938 843872186 448392843 803332102 292102957 691609308 277953307 945647666 768822949 318833646 854070508 321105968 993111752 884109059 755850453 912556289 191267326 520149530 689074004 326032845 678844269 116169929 409508101 363936700 477272404 411228439 550118635 454173942 673518576 459150410 818729444 67406753 549693639 232255457 825732893 919725882 952890494 435549765 230284545 948530147 371824899 357027621 433119355 652277187 144884635 132173226 909017420 356855083 298227392 835953149 155639421 376113695 638899831 109149592 359385191 867838209 653091016 65027333 584578404 261851649 611624987 159818987 994358682 922926582 25535550 846042328 547932193 444609449 358486098 836530515 125327617 940389605 942261674 839863467 356267644 763508166 802397087 581541083 3144382 51875111 496636815 708960038 409583291 247712155 812715234 462054888 302970302 212590291 207583968 933367340 260842783 82655826 351475180 888699932 382545809 510286989 126320872 173258321 493191485 951958369 842824893 417164394 98227133 389295623 741083053 731247452 680620983 404760821 373061478 582027513 344344678