2000
340541510 915333080 721793406 803926462 591244168 453600830 354100876 918678976 535366764 931284043 594053360 654408515 343607575 52234601 486255502 954088516 266941983 968063545 837445473 878266155 460453337 400079527 657442188 149996454 168391934 928171753 292447915 127840974 212051264 650287172 215332206 619595841 505352753 178278588 188445955 65673395 370015048 168245839 213756524 794357652 863479175 361330074 89876123 71715885 630018102 294476246 201144556 1352087 229845927 821385948 90293391 669671112 738762972 958628791 985905509 377929664 976110875 86370288 698320236 408633418 998618023 456766228 888552506 471217024 865418570 555282225 964509139 324571322 138446069 49873317 380781535 870956144 807963197 795575677 21538800 283165475 543833483 545653216 448018741 283498718 927901390 21238792 820919861 536568172 715585369 89016429 58782300 470745149 534641853 352665185 882908689 553688353 511640996 579473524 182881020 594820176 853454777 764274707 613550512 292252562 116142828 247827306 966500687 176977638 411505219 152797255 654291952 534700585 418031771 468081969 73473325 165645887 797001963 689215182 836816432 206181502 897187427 406100123 205287124 809682792 351806171 87390756 699731833 544723806 423946618 260079051 529605013 61599911 496577787 23035939 41910043 268369482 251384115 322981925 529839010 397580210 651527734 746704630 4134998 185658126 206649007 959887033 23044712 417566084 849774198 451868765 307508473 702069808 52619978 842933619 754017189 906677772 441107584 413380455 789288330 597147888 172100862 513140331 837910026 672380764 542577791 449527051 363861255 277742888 338188139 524499307 330805309 483766838 92788068 532508374 199538082 396953091 95951473 370840858 443231900 447681615 320027440 486986140 565524521 346291665 343352061 748250693 219954344 395231296 501065773 832230545 647623587 704184277 238581156 331584571 46310907 507029240 780661463 176805905 422165584 175869323 328575503 124088943 729390043 527061811 506826192 194040039 114859536 115904213 50257648 178163985 807374562 72683354 132361538 824410542 693869117 314596535 631280542 146613393 546197514 311173152 950289121 654795294 41124933 381059372 281876581 882581466 935199412 697862668 947018593 236857562 693582320 911470581 126867048 25760866 455207092 437596506 398358863 166836759 277550447 565371261 461599853 342184491 453402227 219222141 690200710 624170214 231166064 172913346 612074079 950863811 758420027 454257428 999691986 431008770 884723093 565568534 745203298 959973338 852162369 309504245 947308604 537900271 9029021 352046685 670582369 406587494 604359939 373998947 969776941 736603024 610322907 865597400 286101034 952906926 3453381 449345782 980442547 51517873 102564002 918656246 460272814 8452761 44179657 615701055 297871389 746413760 467393294 744365804 563053399 27570790 638974455 718969661 789697122 70907576 862343140 967196970 814623102 26617896 765647330 809214970 633050565 897992557 105059468 961459426 864940897 471693486 923876698 205492327 79369943 122867296 555031129 548830296 939293424 363108432 861440065 858856348 331366829 681303603 827055884 804806251 704911232 164155708 722839398 254390635 418702578 767014739 147165843 266374780 855384796 917886993 28396077 129543812 754241117 484066796 355005183 269572025 553867629 402726187 266844769 13282749 652911337 932681023 275218687 195619796 527918775 978623026 938557716 217518847 123348430 323051772 783388467 310071470 391527362 64979579 921066785 799646230 255946698 381448441 594519908 546073056 800549911 530583165 519317308 515257057 338361170 668146637 418059717 710042328 108064414 432396733 727951384 761915159 989055634 1800079 131922668 768276429 853120100 106178094 353304240 255515337 776130057 192394898 830419955 665605740 779320368 102213851 319630053 837110939 307857566 366717574 595367191 593231939 461787192 800094976 130152151 780859115 769205653 743798399 957123235 741993448 924185211 100776343 653553335 133084572 130538505 707495020 586276456 186267235 97554828 356465291 528792102 889553365 797157575 583520191 298524639 661410588 675000265 722492580 180682756 41781450 751995953 795440013 200666061 784757989 447080744 181140742 830629801 728332103 969760458 838968668 879786054 964971640 151262757 637940465 685852170 544214788 402003170 911781379 563208269 659126072 914645836 440493172 186512685 251496584 41023429 92241299 840731282 607051831 998974060 678097683 742903343 415950667 219766426 674491042 648038064 18612687 745951463 190304661 831109872 143634836 543054087 746792102 651550500 122756265 62793944 550353421 855622149 9490871 893961637 583392699 53281246 476535457 722681576 548922958 412396297 883064155 714575317 557666854 151425318 486956836 911519309 376720371 714777264 595089124 18452570 811657786 422161292 422205722 261428212 356273727 882239984 29170564 89509471 521748284 633874774 587294936 991218542 627403610 520249078 643426050 711478325 387281121 932224346 637260272 842580919 816427297 892275526 180037388 969017262 822534211 654276737 606342233 327093581 276835963 332203135 979830285 504308710 17212362 397741490 192584993 912601136 317934470 618499925 272301101 489320041 282435425 771464911 922993792 79902186 199676690 899248957 356136327 599131460 717157304 43760179 128757390 938988721 417999874 897399173 780100939 876431712 831097012 680296102 766786949 575334245 740844360 707788798 425245300 437334455 148754428 117779175 345642737 339322290 214995808 272063186 338880747 109707492 514059846 76916848 454178412 594707160 898932086 462637199 184189169 607971844 330533037 946330036 165669045 483720215 709699078 151876408 986302030 709694505 724182226 44590346 159057661 594708937 80207128 555463418 797758555 384866830 550630085 50104946 860501377 432345043 840894223 33249361 203131545 707313374 392254889 198357784 734773578 142466806 655539528 33037435 671730473 470761966 557872935 124366072 271036904 723187043 881061913 941649324 16716320 919366465 799034852 29429773 970126754 385763602 290472412 78508897 464432172 77172837 641165510 387071555 302903144 27553993 35907816 672568773 861169050 779510483 149922926 750367537 61138006 966126167 264438737 151657787 369059899 636772565 325831436 288777714 717727336 578297135 609964767 802912041 483260651 96852494 593643202 51130722 466086778 66636488 126946182 312187623 997791561 994986608 101084631 270683351 87090342 460702139 365498760 197617704 530239901 412407699 208219139 152321946 136924731 548559149 326805179 927128523 956424743 614019202 338595502 347381512 718350377 198436508 187695544 802677365 600895022 581529004 831133177 807224729 506457461 449894998 660116205 297398640 350416443 71817435 711862850 191748561 688397325 476501262 530617743 774837237 227849981 438461362 224608156 813091977 415149195 576809800 409467409 325798267 118833508 28063155 228207211 716678139 878288937 831254945 443776942 177870996 709336747 77384962 574236715 501095157 789059167 344631292 373755358 574028316 419258617 496235905 850495819 121157277 805940866 171252492 220915177 294910145 992858249 222675265 353404801 687345936 887794158 206860486 742840952 671371433 567345083 850288886 154292287 236846132 283408890 658336730 377225466 699194095 554921477 255324949 235871248 83566382 218442530 126068310 982932110 569675049 860537776 811441309 99689949 487477615 571465358 545690002 680172444 930669180 614899607 620534660 132624866 171869769 577596980 393750991 392409287 558440667 93081340 499473962 75253130 52597366 508987999 295902908 125370688 829654729 154778731 509999486 512118933 311268844 281538288 43159827 454971631 117226329 698427060 775386333 705410223 900783826 683601731 857630033 840023150 321936952 644452682 518385244 446966363 285353093 956972602 681375618 854501526 478368432 637589200 213764254 361902422 505876915 379733129 272167350 434315256 288782634 349588829 957053794 439441616 220125188 912641513 296314365 474273990 188002400 3087332 933897611 484856303 315809381 814515238 609626111 544806039 315500615 890254581 746492316 154201868 415352066 961921759 576947244 650718497 395775170 962644578 837165291 245937261 485729229 239618595 72626213 485056467 684271303 646194299 201657279 484782150 780491548 205867994 138412206 701480946 477047588 588097356 393182704 70556644 670712344 249639599 174268147 170722713 742816698 277764251 18148158 440143992 741012008 319550628 884740701 445780869 682056994 132156995 926706593 529000819 903055560 425515379 603729327 592786259 320113102 16350973 627441718 38759491 699916916 493480769 69233169 955142069 470484642 926060180 525445976 585251650 832084771 428979947 140181253 394480625 883955401 984390112 319680901 359571340 64380064 32177136 483135160 460101843 322771905 105977774 886011267 13738775 666090588 71325208 326607475 255492028 432098294 992098921 761115591 560439913 415198523 453459602 899778031 700732076 785156777 973506407 885385162 273756682 894656278 548246148 308305753 926802204 76621651 408997173 790321053 250508574 836168593 265160429 835871881 103976497 281907071 518518893 246099636 60071054 871195386 658703412 405342764 116485862 309865030 805764162 323045421 470733361 547950647 720367481 383006114 628613843 20806335 769376563 497513011 188858117 858345587 298103097 968489297 366181258 641440247 750242833 984240432 953189125 796020894 851985639 604226360 82221252 168838338 902785656 582872726 297561736 431785864 273201929 848077610 600058511 521711447 909521494 630082128 947568734 213543844 270293263 273424041 667562453 393892165 976174579 135366687 767714518 447699981 142204291 263044951 847140227 485970807 183073815 882621309 883740826 597987404 903302588 486124286 85575942 345111598 747828539 656422531 79062121 337437029 312681271 982086780 14934086 655442680 857600417 589323486 708903830 88449813 903712084 4226080 549687019 567960114 12106725 836258547 806609939 899305684 137878965 554484969 707674953 407664770 442465463 712834187 468492479 381767228 995193877 737726860 81468539 52396123 49269464 397714591 461224468 730580728 257923600 678078314 795414506 188807466 679706476 797553415 239479045 719950066 495401615 575990163 22037042 572451862 728886729 674110401 362027729 823684168 79016191 826604670 709904849 297956335 599262585 21939583 429461547 312140211 553027934 551807918 12936162 719690657 169877404 687517782 714820101 734607575 926078780 444329386 457030224 889822043 764858628 289266385 782262301 965527728 679002358 604873302 464538326 45482985 874333570 448437233 423112511 68564769 862448327 124949856 947854291 599072238 65404007 765521479 269999865 707306464 527510484 108380019 453131839 493277744 798230453 848851372 757717872 80919622 917891723 21369582 986220946 686266572 379507377 85216592 469755038 60019160 28666584 109960388 853215778 212017473 342193131 905953730 974884405 152771577 773089221 471920454 427298989 271148809 300555183 593759213 445692015 192119705 713696080 216024549 103095360 972250097 213353669 248814926 828515337 847235239 521957416 354920259 761732988 496673386 471574248 815763649 467761120 206618962 513391006 107076749 981718013 731404185 98799827 141721510 739525837 238735668 239939269 677871152 655182122 427571492 216450622 707014829 393468355 307619118 974087558 11231000 63133883 692517271 460739272 548232647 289725669 80719645 954694856 828877502 386268402 231864179 398462286 520721001 241075036 519041181 384833415 360950326 418223159 466810841 372933668 365242207 659349258 589323719 167852747 748824582 202208242 717310089 331414212 457764846 585909079 193364214 427232577 932625353 28338316 392511900 722693083 84411698 872944014 838789912 956107476 801828786 45708553 397983559 1288230 707409694 101063799 440245392 903447096 463702361 211303367 608371002 172965933 237210878 553004278 184275023 737554678 852610559 439966451 408402740 867982401 441504447 817256605 75971580 338018641 210398009 402427821 302177268 114376499 834107248 919086940 896455321 177651062 484264240 168536876 913225409 988108935 540078165 447255946 149154385 120371499 659436780 941696157 626623811 442304457 574115105 71296511 425202634 32818616 38244184 693647197 421047898 318509835 507849165 534661162 789210027 461505116 128899004 256636790 884097070 706738785 49463500 308048739 63878062 573147653 809684331 956112533 943272604 570826790 249341453 740487724 317867507 304266727 260254203 620876492 546870205 860889035 607246569 647302649 599394029 705821122 970093722 542999842 189279249 134428998 720241530 601263444 690852080 602205949 839065926 123362540 473563237 320261545 260125544 627861076 13091701 680907158 782350172 645762716 556986611 165053213 504672286 284477528 841510181 881713592 43272838 30602205 15600128 162512713 756734804 460689950 25843095 425693628 791625322 135996345 130070408 295848022 671601609 893367026 168943897 347898810 487167446 243384299 121072641 665356014 425889251 831246748 629393049 95521111 403091978 689007508 132654452 894120305 939446273 118951781 50412895 961434487 363606062 131754220 297222807 77637204 112221177 407230415 526852262 324487848 805582018 299273949 948274644 695838498 129925167 239193751 25308930 937058581 466314506 945252302 61895884 455913594 464019443 808274297 288330260 144042902 781123493 667850051 301832648 985379649 127879843 790936941 715091349 152539849 335909528 352413118 851809775 645679337 506820866 943173598 225804430 759430462 642400270 641429355 865224447 471473188 250986318 492691243 318081635 880052520 387576278 702802706 877307522 651328816 245714913 769957120 158432757 959386987 540329277 244954551 997029606 242266737 872842073 126083545 828389197 681031522 699988008 994403155 651937202 215001877 651055610 526253487 998261492 449221013 208180227 348425448 530229141 311930651 191534320 342299590 784391061 257294501 600008885 656614625 286128296 530997152 250068739 197898491 682081079 357555223 928096552 875077945 110902370 153769328 617334574 226767917 544607577 762232350 581807069 593528065 761773737 960714855 902880665 816072843 339246454 908863513 997721945 524179918 707026009 115015389 439220030 730383033 565328555 391843469 574510673 747761837 654131877 982045212 76801828 447186505 619745937 776083928 854832998 973054367 511341110 294219863 888017911 225892035 951464791 923860718 422032114 259512034 318504928 23513982 477739569 360697883 616879558 77333156 747334655 624510726 880905473 307222716 129600229 936476350 177550257 753884859 959652639 398457744 387972267 100313117 647796659 482417052 230133300 762772971 94356420 79028186 157243165 714993257 535070374 83659088 556155104 716842403 963269936 28258983 903869042 415304134 185962422 460699554 364614561 755497133 590872539 705940632 242979964 319410126 543509235 591599568 364241076 416125505 416771690 91015568 672246316 587701773 94663596 731960816 248529005 566733502 841480480 422661036 81575699 975239965 284025992 282744436 889662729 226162093 248721607 103854039 127690913 458423620 772070533 743431221 430863379 988088970 295314963 208569383 535007573 549695620 826864467 615592145 322180094 406562341 671622235 520891038 721311594 172840146 670914979 933456360 576454140 946362234 333912039 427514496 158495274 305427385 390254004 376802450 932814925 278748297 139334120 662410889 512549396 997744747 851398620 836728181 842055019 344682409 499498547 394041463 497404920 941275396 488383595 71318906 196517245 140488284 646611342 665694517 531132661 744995214 717744942 869464306 189139309 680628735 670209810 66409105 944719238 751559282 10376572 288269842 98445152 746261753 324068326 757798488 377436172 273838054 774929504 213372066 114073754 268719454 557351724 489194710 149598400 307472767 671773841 875447104 658482511 653702813 713527350 232902960 917849985 282218472 6491317 232753519 285394032 431758513 674121537 905718237 890760090 585784778 937831884 378654564 788549778 821041326 913913680 392015196 393286915 758766582 588472050 498667190 645710923 197835124 344445858 810963666 296812782 801306748 415662386 971449040 427493400 983861114 830196004 628543093 677699464 429129606 743643907 643565032 401545633 98738412 64096807 151660168 931157305 494655627 325394045 78002067 904055172 703492271 43781154 833186024 774820943 23784494 211589763 252484707 47373945 972305035 571204039 395242591 760492807 28988845 980018144 759812466 305366146 994915809 770880155 83772889 284328526 753341901 894539756 342224866 936918084 846221597 34401272 655422603 238588505 646580962 66883080 320034606 499620884 687615579 37531039 904582498 406562503 89469417 952951885 240396842 862210793 562103341 843618331 429515657 601390386 654244406 980502818 15703665 530276814 869734642 992920528 702510580 142367687 301282501 618187994 661019195 115276236 989125297 976377589 157519960 965810694 862300727 319909280 167910487 674124425 328565928 481145825 389817932 634808267 492397470 541806123 98931668 933373793 710871303 971700881 42890394 646945432 898281537 851057128 287760681 427187976 107268083 263619280 623536067 445988805 764681719 785122983 304263465 332403059 28205034 924238070 412875663 413282356 799394799 283325693 939993048 949716324 76040596 169091439 314244767 585550483 226282131 758584851 214480088 111980662 906152415 393476330 25258808 719096915 150083816 872518213 827413028 383692231 391881712 437436608 626662408 614423379 227757538 981265728 909586457 184303421 614794652 961627094 233170303 9399797 464685807 923512683 901146600 468583296 948170302 257311277 72377864 408860632 402831188 79236231 627786573 42920086 730883894 297443942 765915987 537761135 783332631 51743123 647299118 736717203 838642984 102879644 35653815 752111430 84654442 198140852 728132504 861270160 170196100 250725622 640106838 203577833 34330709 573568962 618527864 444195204 361377296 163448679 407654495 929443426 370826560 269661582 125552644 675767222 531544905 162413705 234017442 804737857 835893063 744080536 765932712 155361856 323928978 197711855 12629162 608476452 806007319 600618548 572874479 845172921 341034851 37622067 764995011 546144893 198302931 180125880 596052456 552216870 48740228 656437601 823872378 168660595 444952635 726318911 257834324 252020247 644989167 968651912 107360176 18569219 328640500 165620749 476029329 861262960 256795606 852564659 214231882 360316254 562208385 830641173 393912968 349506082 271274208 197075585 305002016 517911654 985299647 833812014 503259419 279627273 278846966 972666959 482271900 160423869 793190468 337183132 587723474 2833950 62271638 558032477 88171663 19216223 761727186 506557367 723173994 292614595 707009817 901323342 731479574 472816075 600090134 375431644 613023040 889819139 128659504 922950218 314448293 377684529 870921702 297692445 843677238 980877532 871573242 88828238 908384257 664512529 673773261 592613149 461086953 285440007 717963858 287972233 656982853 953973937 95957146 913022045 840009397 944357314 969404958 500621728 447444556 719289833 756129014 106199565 140162733 210110291 734517392 193331459 687611635 628713919 798463705 178161813 978430253 40464331 184999276 201185707 894849436 49766808 357606020 863543982 911231187 563113773 968354706 770891466 517459134 976368431 719267017 514558688 862632159 494023748 74080656 514055241 32472321 518730683 541426557 240493127 476465153 102292163 338951702 338268294 153705906 678053285 799134283 448743132 963714747 809097242 703342155 689715152 465435113 715830004 913773476 600421483 451694384 455300969 7546178 282497022 147193148 754258502 485944032 724889303 235741254 245066244 394156733 809106548 293336149 372672196 226162978 605671222 704506821 604547527 502009675 817678711 35562926 380533341 546216102 71970528 410826692 467933221 173065471 788369647 42310293 132599885 11807993 689862916 696598876 944545977 245597226 272660878 467603419 733074426 416690019 945558566 455223150 383083767 867788214 337772090 11929757 474603512 330582272