2000
546044460 878278015 126263119 661658098 521101301 75484645 714532445 720188408 761653752 967291679 333468519 538243067 616327320 453198118 914562221 28821403 760128480 737562866 201174349 85363359 168953797 977662762 332598997 868595599 688862160 527840624 975869502 100053409 204673758 633430349 98157817 467339225 184824686 715295626 525822246 950551314 332667116 579023264 387250959 324786328 43732288 787554610 336055248 764987888 214891559 644062901 583376389 995175149 97557517 413936069 908576831 629310840 65013973 500307173 708291771 637527844 844833878 6636006 669769486 762250877 306289528 229943850 933797736 885115183 409971582 678778624 226180837 279829313 792221450 98082189 542472437 871649927 214251080 989841305 429991713 800525113 94616895 796495091 133602559 247770437 493523713 905376850 978539476 717638343 170069366 877613707 654594504 618084678 172659934 249810488 494361082 530982552 196833959 3038773 893500709 142905575 291835795 80013741 396200437 292431069 995238443 929351906 274536636 809404414 236006239 225427144 457357378 755223219 962538773 430526952 212027966 723449591 509463668 324641355 675138796 17657287 942519679 880570545 35111961 619715712 141957922 315069736 746637684 599755833 860884343 684044799 757385005 673462681 597389782 824879515 336251885 700412592 501264407 967831793 418506011 711926529 902670398 211945482 539142629 477886152 611227990 229373519 145762447 959510940 477776972 523285448 303835194 443543848 862321099 288745780 425261476 334600384 57486658 802879295 837813688 887824238 494753594 308420373 251610128 3376119 572863155 206339309 838642194 295104563 141889180 662837540 858415840 551884484 446790343 503285890 74688111 574961577 964545845 820818925 335200830 30855890 825485712 420580815 151672885 463169669 820738300 26962374 341889465 256260013 296335021 783470123 301195018 793628942 566461447 28571413 197002815 497805159 143656198 618538197 869505691 117550817 729350924 889262779 255154042 901870051 118269348 714364512 108279044 184791226 372072816 748644814 512797052 333685045 863392544 811762844 670071947 177825887 43867332 66406781 989109050 409089523 564816374 814827371 917626641 788570588 987209633 129394795 568451813 770740367 544061930 231057122 999196267 531638857 663432874 132430494 914824922 785298512 603422486 552215140 575932836 22300455 232025684 988279289 624180450 289004945 744220487 988485919 863992294 306735457 625353367 366508854 732375276 796398583 223187921 102742155 856666154 395118160 129213188 108462343 953460541 414741086 210909932 831663069 188205184 698541976 482746182 545123517 326630308 837972894 75865796 164367893 241823745 563198581 556692850 236160203 20631331 889042493 624499897 482611592 326968125 630907178 669790267 582140070 734777611 266526090 543532424 735359852 117225992 534984673 718370469 332062636 102557738 250164557 178708268 529560389 147462198 424791179 6518868 808213495 785601862 129496442 156202321 570368049 592845320 407301390 956514969 617613450 546987590 239628642 281272364 881227933 485826492 866277694 474640372 994332311 652316446 498013418 361335105 943227138 202465829 309790688 485849009 137396471 93376170 975000500 626916319 92998948 385024274 189529926 359393431 253879248 433868882 420915068 304662815 677176174 140393972 129802493 265499727 215158884 830145602 960225314 866078635 223250561 41381900 179356177 1346369 699081079 70076595 521980270 810795564 366571872 167705848 847719239 723166574 971420214 635613441 996153179 773900723 557495653 13212912 860865201 707854033 285054908 617118142 193288816 696845942 585784883 779632018 634576900 726989051 472645650 343382586 736682416 925736868 850987748 606486010 495778065 59551468 872535868 514885472 762521341 816948737 485165034 153869822 863399612 409289768 187535666 915888171 505822206 247015215 565253535 411682736 820384470 887448474 867680247 504771516 203054541 651876348 514116698 515246023 750541171 667909984 149910711 136730662 511463867 161037185 930572191 904350874 444415030 55414407 243258423 514261517 424189419 595127685 181350437 593318093 741987707 215729782 530767437 394957203 947565014 871781944 526942000 672739899 462287659 551688759 546733941 778371902 443348021 724853680 422370736 203224137 531074086 610041891 326897046 619292510 253643298 943146914 491893656 352740995 142785031 861359513 492010154 807405153 775689338 924237673 689047030 870850845 638925791 796901283 620543988 610705994 937429205 64368298 263267721 303976335 622350074 239326498 652453834 504371390 360574308 326635686 931263785 860626785 196299446 91705500 559810042 850288277 310180192 714529555 358910436 329090474 583227115 638613149 363905822 363534087 667135042 63621018 650253211 775975234 326053591 420026106 45875435 504251152 486939494 673259049 674093370 699417433 447370315 78089759 788027184 19515338 23359245 690333354 294366658 275631333 276141366 468713885 746173822 428609302 191302491 626996267 775647601 859835046 501537659 451587482 739693964 789669055 360890691 440242944 400464364 190675151 482273530 829129610 612631501 448906140 914775888 115875727 653470243 866398939 98026823 824125930 912128154 201830050 173210569 467248882 966138426 540350751 485665305 561701613 938575073 792267461 403177943 575470170 968561783 7244840 318345988 964948951 498428602 821770725 816054144 723879789 701690031 185959731 337596437 296273861 194281192 323121076 921051566 407425824 964573941 340455384 233757986 205395881 415190621 706538319 220290444 945234824 191206197 853905051 920965850 329987952 894586138 972624505 512924 441183158 754045370 468572570 508575754 830338945 311592678 609183208 842622856 857256535 301468473 158305017 723493830 517370495 611725174 176828912 516290664 796505371 381694129 465219122 257122705 256971513 135816470 911656557 676483393 789358462 215540163 2895189 313948678 224488166 624223701 439422409 142523159 122990478 673315603 996750955 895743972 5166762 681959546 238020469 191234332 589996337 630206135 605052015 911728660 582930363 829721042 627088260 303228844 742951937 692953737 132653340 911308656 26528712 241363348 388190144 54746785 244544210 682108298 199339744 630893806 374485221 809992883 848650261 780210300 892921666 832092201 684991018 530571955 717394819 569639093 693798392 698204027 798570590 41832599 949485047 646335325 411411997 108323619 779140541 128232449 386502124 803177332 615579400 294878205 53132375 449355675 817322070 286200618 859474375 953571179 961247354 304809808 425576537 356664538 58443475 92683312 95385938 133869426 92379703 221185050 680549317 172725669 784413669 722193302 981528809 984796713 711602065 89719330 64238643 921502710 821453615 496910127 807143338 363019656 538274009 980971935 590001418 95438334 259421486 317308978 617657416 475842013 672743798 4900064 825777484 461367409 345662405 953064258 445690599 827810473 243997359 90659681 102318424 474123062 365627721 39971845 954179289 403061978 950820274 612148240 163572530 361855345 953095781 634178858 407857318 735154160 225012123 830163530 7970899 359981893 372502321 481118178 638845447 802766147 953893113 150415579 752441358 26616253 363826050 599022230 896266277 984176750 371965679 197355948 253560840 230678414 413536815 734016285 449395721 927273749 185458446 1338552 195832634 155024189 974409711 178713270 46399009 752948762 597747183 186253304 412115270 671452562 266300263 470650554 952954922 283354278 216672661 266031933 192053836 926886042 435745343 134128189 659627985 694763306 793267935 173112398 713475852 364151799 893870382 577055903 749192548 108521038 442613664 953594320 179631631 830654376 775333125 208285364 581100728 248515881 567457702 778423870 231723048 744311745 998585163 388677940 191927225 875770961 605583607 941522980 372155626 814876941 818224202 953546377 16019342 364454990 734971776 27035820 240773487 674330640 18743590 851583379 367989881 667698093 34954780 733814354 489635489 533888920 501238026 599883080 612249907 127800206 251710256 63698902 795198486 345012243 533474550 359790679 239352220 830595303 482380200 199006179 564093001 326899202 425557558 794515209 280465469 739665582 42139644 922618756 357273863 778879056 848712371 732687100 131963885 786387460 869470694 1892774 283935121 49262832 502192850 79301510 327969216 572863829 330378792 470013085 293717678 643526590 597888092 495751514 464547269 1361794 873038968 310666257 437321272 338610857 18503613 683626432 37450780 278612313 655075697 45631239 935703138 489394849 437286158 357078862 108000386 583584826 327383650 204853592 156566643 431512817 445309694 264441066 526559171 351023353 246871580 458213531 262509273 776903796 287388239 222053972 657195392 578115201 728801885 586577619 375133699 528185061 925217852 733027816 872700945 246972148 483930674 26531916 761331873 527205185 8133555 574107599 254512327 482101330 387057460 318822251 434190334 305625469 6555331 915492564 955189312 828274742 122404680 225486721 706818105 748358552 347084348 785286708 414870848 865648199 995551163 638067507 825849007 603855743 561225637 26937259 230903198 373772416 347082149 751113312 864118741 107087634 486269165 459587538 837306111 81337243 810873301 161085910 904565147 705769067 684630247 714411702 141125710 363275989 448559785 854280583 175080671 314169475 142703191 861498823 560532764 1087924 606664020 965965804 829960446 653246547 823016628 169329493 669628483 315699438 560416743 761748921 674081605 839795816 40777344 769974434 667380379 413464408 328510467 827759059 672110406 862821809 348228672 546803488 534813718 215018504 387257904 194825041 302200190 251272306 468813245 581361466 304499791 318146288 813716783 249359703 346611483 874150111 499201987 668319642 255194482 417484321 672336158 933928327 627100076 823240523 666528536 974267245 243247988 685186749 594080868 363358810 816448697 725958653 143594933 567543854 521384864 307809610 77561420 591060551 318352743 659619780 839242560 215909762 816238029 894967027 299551192 557444710 281359346 225486389 268504563 273893006 313739581 92024443 44039930 469107321 841778338 151057233 169136923 513356121 108986642 519691335 353328784 405442606 824920126 491014254 436638753 966779956 914119013 677522774 995927172 13357591 735885395 313733493 325911057 149690695 651325387 728325901 108104359 852524564 93399477 205518281 213278268 594152490 895464685 597095846 527165458 148346538 453270845 686515918 650188767 434217802 745913256 418749358 505711233 382628906 701298801 866233341 384016348 414802958 149197052 24522963 272523369 903532509 488336759 438366250 596988732 583143180 334736851 458145897 22410749 721795794 283435819 796169651 258097464 124117030 634024349 138309906 798432470 484603797 350325665 316519292 535358006 724896327 691887889 338308624 572268574 154864660 631947302 207576888 720607391 450333329 840404572 111429957 882313165 599124929 451030872 17640818 301936798 75312712 396324912 586138051 692101513 914092853 111002755 590433734 879828804 455516683 607343304 939229326 779573433 771163879 597400214 12368640 344814585 498430319 689516257 389983120 73714019 218093610 664775653 591863817 255407810 272191815 61242539 215825701 883044402 723346774 131358483 474965592 63160428 268454212 220581652 102688656 895313877 900760586 378148213 697310881 250555910 375709543 202314190 589653518 793488022 593629112 684740790 272954719 195507068 204785885 267206843 505334473 710455387 411570303 635854940 105820115 572697947 132378589 455087659 156904371 533398438 17196859 243207910 302438383 734297316 741840484 683788130 780525892 812116416 422133728 415677470 691454665 487894103 467217435 826044137 638354779 581082755 709181278 827279205 275507970 339947939 832605817 677146023 427348445 604780326 713222544 583399155 558505079 494044763 191718183 392657652 421812969 457453167 93491931 851507362 167866482 659782203 609016492 745394183 206479755 459911762 611669110 511878576 482513108 945022621 158740451 968374970 986121558 599921384 556035239 389897581 787846432 461988490 193621640 280247742 851863563 366406582 747220734 260738579 26460375 612189157 240901312 454497638 467953527 143074062 269179252 42757926 868961823 10665321 12964763 747931649 181168322 652516547 858062097 856986470 354804186 905065193 197482470 535389571 540286381 560811920 537875550 186328259 70076940 54477734 280857785 989069724 762246801 401520771 271633337 693642648 399314548 350405117 549422543 383664959 174448578 279358201 886602005 137800570 226143822 612764275 557401778 79046171 274900114 488460375 694641972 688389455 580208624 374134496 992652731 794924360 836247088 494461397 199136916 454993933 13855867 807976574 735553556 418168763 56723391 489825869 951805550 875112068 34968730 533257776 266999178 203784178 238696043 744698503 838674544 725847648 352495381 553041790 154199108 95084718 67127337 562823492 253288295 251388769 880695502 529795859 322524601 427131832 158080403 547254318 684982625 101080764 580376893 645453066 491635088 43668085 539720287 774132162 316834894 446110436 365051370 740299156 960360563 912362316 385579533 324722144 963130379 794530195 20895743 226039493 308248919 739232373 923705969 582487253 32989452 71807790 187458263 940281113 260135697 93725129 704737415 936256818 490569169 551201264 911703447 145925879 824369780 121504538 561651239 533110957 503892730 411957195 988372360 880351674 590210824 367436835 497709910 768188146 587113941 200548743 187360749 737027706 712033426 322696191 709600140 228942805 25203027 245921674 749200620 118019082 50278879 846395072 503770292 56040788 942148059 853740334 703430049 799664834 15614699 257136827 449894068 121402804 715319938 32408430 902846316 683877790 209965076 616486013 170821431 421461724 268370214 297660575 547353281 876556378 539465821 574092638 95068934 467525230 967907034 816144188 532987131 797350563 497331754 116885986 873240612 668841251 225663477 89673153 131456626 594507776 207866863 457297472 721730923 322908547 103978064 763978822 920264990 781769944 687709341 912028165 29812916 681749921 812928539 757958636 808832524 856691041 452450675 792507407 540618201 353601503 136374646 992712267 784313011 993072779 757064413 382750040 86775559 17019504 565844088 865592932 347326300 59712010 221757336 931744283 164875730 809575554 278743109 603670207 936712370 377738954 246776825 753029102 745640877 578260740 810028840 401764610 328014816 70059533 309704885 121757215 444806131 828397936 36230146 170899969 309677965 209010742 536236793 950300956 339657172 635204843 501320682 801003241 361855193 386228923 50818819 741735206 859413790 951248035 221097880 152656459 113245190 217686251 545163655 69459845 477625149 905906955 819535691 548738244 459460436 103236106 511236417 81316429 106642611 967149036 395361525 15206692 905931615 708061163 211480730 665652276 55383337 135460702 715086668 870810096 909461146 699057410 341336223 833768747 326508782 118436353 920709282 428183899 165604918 884282580 610768875 699178904 353856453 611443644 983221111 16110372 264168826 581279693 207804101 371155744 905042851 723177419 622625538 291649116 159246840 231923003 280621485 529453248 475023702 603532503 735319854 559287443 75860030 44974893 926490487 427347769 852836017 360040936 496619528 181479932 494505065 529464188 926947611 370435077 271990451 134998068 586706908 735132695 665755973 166164032 672701083 575353158 597508774 220701554 677611028 867139083 64524216 689498518 747284543 357137104 759309283 670438583 942951324 950757467 775974928 156877936 737395777 288659249 692372459 577356140 101908215 457563609 933184298 646462787 559146019 971190126 234326116 676085611 436729478 725264799 436428125 642168965 305235903 268719244 465591160 223190276 248971162 919807027 945437912 865504551 172679715 417875645 703998560 816476215 586570875 955886824 713791042 236787342 698385399 82099507 773977996 737221760 22356156 647045899 281674436 172480268 41374945 735193419 453845661 919484793 838731320 120424083 352295464 410867158 507066273 238970454 501886978 540493028 255328032 103300791 755646981 913225781 935459130 866706026 398358362 980673424 146542245 229680652 860980848 562274760 17238569 246589382 473661828 476125830 634906581 60275688 454510186 304310191 994341093 595117365 748183444 558850364 919719109 493875132 180843624 814172084 912345178 776907236 507014992 475642125 146719033 66424304 253431704 7883791 975031455 727654072 126412014 458352787 36209792 971381058 110205643 951799231 173291708 907059064 610785643 185252205 726979981 94876855 307492148 485244551 184656794 398271209 888096157 443518912 370086293 800119967 715047557 422891249 198778514 189654181 641202967 34297970 959210550 8710788 815831195 174806003 766333669 645978666 558943280 269461719 793775556 164414513 366620715 739251644 139124633 851941633 128477217 846985166 972307329 970805133 558633411 962177997 317303310 526737827 910376215 145174832 565673943 731637098 849088193 972368776 823268946 535869338 481169014 525290274 307819494 834610308 695203820 428073682 176729570 204146036 416580331 614664370 637948035 347186048 9275099 850532278 271073902 403976488 606846499 693883796 699602283 795237797 735199507 764257015 10664876 429896591 495243818 994432376 756122068 204515280 455370838 852745228 560460964 736593487 473961216 741276734 387542979 449677204 683493995 847376901 595340885 7152728 407575852 96442037 952475771 635113929 437210611 918119043 907003530 909635523 196542210 704242179 180614069 983163804 770058843 633647866 726875357 620876769 315447418 676811452 618458977 452767828 918709009 169646414 551163047 399668690 781070735 74631404 508905403 762834155 250867584 103281134 711611097 393122573 971395135 22956735 357022651 700341802 790961047 697627605 664106924 748388905 739443748 142370193 158378217 954994432 374334874 757476163 978682723 528825633 748935084 543018147 509340362 390402465 183619339 698378832 276582683 956909580 462293004 249450872 281373619 240402153 352949665 490419663 629289401 511599007 975775701 347240908 355130903 207407612 224518213 248540115 158571413 396947569 229519768 455918624 844858869 751621367 239995190 931591340 85610379 224900862 853756454 826630445 554613240 568559684 417100889 873118659 75677030 197873368 36309946 711734579 535392954 371484624 800890732 396736317 862735623 588302243 233808648 59002929 125253646 714948897 840465105 227327878 272395720 771807899 46863106 369953117 57964751 827992190 754900042 464867565 333875663 619246508 972078560 290611156 975663635 35103730 191575604 429922801 895734973 434164645 322656706 690182286 951470442 450719289 725055737 877988703 414630293 100216968 384218692 443113758 841888841 178828505 707188381 257238234 802992747 599455955 58054509 624861132 188667181 529123069 855159267 39484470 38165716 211068655 300410146 347002409 108364737 851324042 308278886 739719055 297572711 396147241 404273575 3371519 154718585 362161381 379029589 566905565 862600407 532594855 719662555 36428319 968676458 580973201 989425285 403289104 695840083 46782902 398372616 409130468 103328748 583443311 328893608 707375900 661226401 29864134 943346995 675133560 38807932 485811477 591162531 225192456 718506715 6719461 985543138 115773194 941372014 352135469 417518229 401357514 409025196 715482153 558298214 640161781 823718129 250307223 209951914 445681221 153266689 309044077 486569639 515931636 236110020 999409374 626102098 130943476 306252489 21246399 605422546 561422168 985989321 201257437 94253211 430920642 810169967 447134514 594829658 691152186 444688309 740705434 596662446 692299269 674737479 887303308 633350581 778812444 367214187 691320873 721835994 591370675 7630517 503850144 305944549 33216528 727438105 445887470 241299748 578368753 30546001 798083676 451824049 563160968 802088896 962539138 39249210 982802799 872937799 169813781 379961616 193328905 544327932 377335178 725113396 818538390 490498886