1999
495684509 716451666 569528458 636220532 544480127 663198676 503312843 331490722 993976633 332534279 786626433 493421856 994201449 141645931 202924601 168741756 396000094 67303680 688416408 757341818 729745218 147988819 573617794 411241765 971045509 887003695 792746206 180329115 620317531 317664382 723759711 465877816 750648879 375742701 973110247 525662208 405242856 458259017 747589883 244806058 180062437 674883151 160512007 51413110 167593722 367989096 768950225 925096075 438667270 386500672 426299124 100996201 414590540 154110103 688756965 430793102 259192423 864083129 396421474 996585635 212386467 548203669 30324358 336512619 142424874 691813517 257792299 263194531 501486989 626036252 900122667 320754853 622236614 837733788 547605713 414390749 642906461 461885531 694160311 41916753 300036188 196765287 373860235 117373404 220423904 20690685 573122768 990058013 618446358 517530553 441725243 178759060 916833544 548254526 345021095 848457225 159947132 106250385 562941523 167036794 483752523 358454677 786806909 414542035 782185628 954266456 620640117 435963076 157703038 236158068 888142657 528343091 995917647 937668979 273570421 198815145 76201623 262854297 676686528 42625381 226319896 446523258 597063488 546617120 807808055 589947714 245290918 569225173 64633526 400074995 679726020 867753507 387583527 684199144 552223421 791003664 277065291 767852795 849308053 300150018 90237282 302995794 340696938 386395734 562438288 234842337 440506911 151253800 427491800 147040022 200671524 671489130 455082415 103318474 865227010 263805375 494560095 616443540 720704018 1472775 261224564 956602528 457966937 858156231 106979124 176684885 7044154 747034099 875572924 193729889 140291018 374312845 443936264 764299314 575609390 509822107 46967119 884161908 261412113 742228992 214571999 335165924 723693081 187804310 36082377 202664980 168672445 795120668 340548863 886719088 177172369 465617068 957600190 327960230 908279499 613881146 386420699 562777645 510194113 905986308 352585577 906251190 856525218 399802354 355493961 37120855 134115104 468879904 981629702 94491476 965438773 64637104 735141491 848501701 82195103 363226806 34750960 654773137 532650878 478321724 508039634 279374554 863744497 139534569 101448479 193804060 902644957 110291426 864708852 626610272 600589751 974500072 958218830 3611265 927857618 931551440 552486191 867249711 172488431 593743450 679344522 65552594 383979882 74153801 201875651 60530535 432017666 95445388 256173090 580201197 880338542 342943652 442790604 178475203 948816108 520016406 607924632 5087450 952104145 494189191 515209083 311842886 665167163 676132753 987166264 226050755 581491659 664643521 392812803 523323557 494801462 826399106 487601247 183295604 620712569 159121926 170207087 249122478 382230905 751525060 119126315 646980543 362597195 361053119 76606575 36821325 475642687 724582442 163387696 238183813 967760313 116452975 169063679 16824937 733197147 890881260 79823279 945497266 273139370 135820725 342364778 158457762 987138072 640815298 910305639 931825094 714366490 125660112 867757428 309523890 669468642 150520006 995247348 360620283 962341498 677459652 578895048 728215251 867618016 707466126 301361002 237930584 752936841 428272579 707501019 30564995 436237397 184756371 271321270 845324956 847356858 118766038 956995778 824763951 57839175 986780774 921270318 91000649 178456320 391192973 918672291 885693264 411694805 349123085 504499031 30235823 912384525 993245226 509034066 757639365 231935033 159117816 202978890 813518673 284224044 618905243 929395850 525529349 801446736 204652993 948394217 426289887 165538498 384080896 38410201 639487029 575510881 364702364 745017832 679235641 125573997 472847951 570628084 216148838 734203798 862881273 819023632 29941873 501623607 644210698 693991323 4590290 657193896 649969809 93152691 8207617 951275329 881211767 95421090 976465588 749829086 27765732 439562452 153045736 781082545 830581679 627419299 427850611 186568727 92017938 204221830 268331386 551024455 402767656 51868318 316034941 62373857 248227853 420747515 249898657 34339866 485641451 609269219 188238093 206143007 98658361 659527642 970525284 881265595 491895894 496354457 864417164 280115918 340460795 656771172 949150748 929827919 522150813 429858100 765762511 671237985 898976541 557714628 905733428 234195349 883122660 973678798 627175779 101088090 931171465 976015164 328581535 66354541 633055160 786541248 375892350 165172033 860005966 872723655 457335127 707820687 418975847 960482764 974499706 604672238 754056439 561375776 492472695 384685872 175598403 25808396 434305065 245108604 112813468 736906020 620685534 863822935 425234133 230855628 300812147 727657333 924987467 191714357 813857247 197234230 629899837 167729582 734125807 858478822 397988972 225587593 989808194 596099854 791171920 515837338 952083164 695848852 776263462 431953749 469516907 523617421 410583585 978586000 770439685 473937247 108247054 435152418 81102108 958192213 569921706 102157136 219908673 928736121 595857973 605307627 177531538 859641535 892960790 692890255 684120698 485523346 793372293 413833047 377130784 808700983 7180119 964067122 958847246 716128403 662049915 69232573 911723206 567955778 614747614 305349731 968060552 609511518 854718703 242247252 580560333 993809445 312784821 548909912 615062935 798641282 760285875 21180713 885452492 31601395 934209390 700027437 186344567 837833184 342822362 439521810 323212622 891709729 998345382 630387617 338907706 537338193 358578729 438587965 385112503 145966622 253988310 172561769 913282385 378296913 945029299 361498997 955886413 972023034 993746137 866329698 214666735 26925131 386661359 755866825 635641221 746755854 139238622 695446630 199982207 202764490 487871290 956525382 901389114 430458856 121645689 103210492 387947978 595409634 833243533 874330233 788958017 265850189 871895853 956434876 627129040 933902364 687783660 687237333 530406213 744801865 193528510 323374478 79055691 223970999 485545549 780961861 244383736 493938998 232888737 283639851 470087753 315580236 892435650 276068959 423109396 127228287 943438883 870078004 972012440 217470569 296889286 904151373 608568564 743821690 955689080 554452198 55678958 604531538 699864777 933055416 850860226 476936143 130302237 589563967 835025353 855155206 118074837 181348833 656287871 159878970 984420394 376270782 259277514 871241430 637556619 256792046 501805089 110791137 80225801 350943716 756723719 998168676 130750103 755957724 553741426 362164546 150708843 66053718 222189802 365368704 868136573 765938178 568826170 47234892 796958662 232881174 489184311 129138850 912756056 410116883 865137879 211053958 713194899 277155192 181672455 119247312 343369276 112641475 253030115 759000456 546580184 746564185 15080591 678982802 232716240 863321239 298283386 604384984 880246631 408525875 563036229 87498496 95497914 988998559 432734162 313821829 15251661 797087449 746498664 749471450 50200842 508846523 621765897 3714755 467065758 496258931 751084519 967474129 469130474 887064598 599570990 668802582 335618807 761085765 343853163 584631509 187160371 783550442 591211981 271226053 849276148 967576830 31026256 54730208 809819520 912564588 766813420 63047492 447946010 189600976 237241720 944708894 514689761 660359397 494355641 643521065 416729971 905516127 780424162 524374887 131552875 621441814 794331949 136160910 125107356 943612383 727457945 667485515 136377556 694227612 581007660 144382690 788861179 854496688 165663437 270410352 467158365 649590963 986988576 55975445 166359398 534878637 809977716 778477444 746726934 84552178 397991284 605717681 324079743 426811066 522615035 14399701 59437732 769253 518891336 404963749 277114024 768213382 433169498 999154280 30152996 926596182 632257505 978230879 66018872 412099096 355877664 128684585 141114725 203130441 615547621 200790664 339774474 196277931 921610952 974953564 309838926 414715852 154442798 208340314 475506005 651881722 459935058 806721834 935106718 528896063 675187676 740463341 886246021 396891187 84112453 479242688 773393081 854660590 714249906 446234542 417117475 478789082 772464283 158411991 445314185 339744162 505225020 965485382 426626584 610664240 529736197 731084448 135126226 100963346 164678295 305543513 493390091 978310205 445111409 740771961 122649350 394849713 615490959 460268768 380619465 595941869 740651896 346014044 310972951 369461365 639042484 596349297 504829926 387695459 613620690 525113432 301264891 85745231 737137495 718881028 761429252 399686229 537212974 518775188 770541576 271373279 554052110 364404626 256938952 265720048 106267798 168564079 311360647 426831254 420756542 248192945 64136371 713071517 486883687 808989744 487074991 224242628 449319187 468927729 21768714 478405990 237960923 776421456 740576532 355934785 713140608 414298485 694319387 564396334 121076920 307154453 189491997 125511687 556645768 912561191 692082179 984915442 86398095 194636459 707556398 828846594 126402009 723781394 511412441 625267605 653167968 604604386 171840106 121777056 172940404 828586300 66235610 913811151 39100362 126998638 925506410 89862783 591159431 463003900 439481942 662907515 928006974 72402532 941210325 228330572 149940156 44310063 977396817 39882124 36381627 518239237 112883817 313739031 140059360 673906688 634625720 276886666 235334855 748805808 857346073 117370390 645781204 82227310 712453050 754591350 58162238 119015082 138221279 847337560 782660305 77488171 429118192 745492089 365258539 607766264 60779598 303353897 771982154 259073219 294124207 662317949 222403745 2492806 53984493 847227451 270330947 650700176 604003247 246013158 267449282 159201008 773938547 850781174 643862864 778540825 964262850 119918638 321605649 14669909 665725381 412200965 470399769 389175336 165731428 225057115 687167059 19179297 5610887 113315214 547889329 653747530 370254677 55223743 79572375 614972934 863953667 119130099 42316142 961329169 94400811 595750526 399314658 935955482 497848414 269219770 152867716 538295617 145817125 179903 374656730 972950309 212933459 24794557 572654742 357476471 628166337 206983617 700488334 696396050 370426186 331638725 757315039 126346974 91972918 89283522 665238548 235725528 500373404 368542060 209487841 358346577 78294301 516612677 346646316 852806458 102722382 397867972 370060774 769345137 775315474 296300021 93620673 41198331 100010669 661727245 920190784 396337349 146213312 522067016 281242628 441467282 94372858 477801338 356679247 392898328 544958089 639148545 285042248 557437410 146200926 670796084 23749837 514280573 400681942 893243014 628787007 443717723 641259640 286435920 437572836 475288830 572828912 296268042 52960105 64448323 468379445 908003119 948362023 265385865 488807826 449862158 885476395 407867353 761485697 311257384 560086252 649138586 970370187 849003129 699555626 966701829 195885843 357738876 418961947 903985735 764280020 425283689 162767243 116232981 189898864 264729865 115767136 534773842 272424992 966334768 463868916 475689700 532807937 109031973 353472848 388163347 514937830 61434868 900125215 344014317 907873980 499379929 56833839 666908355 225351962 53602530 937249209 501852533 691801127 304877269 112566175 793438369 565849705 727687819 807525520 558628585 731646137 958050785 505250896 44636380 472858023 836168944 797173137 429028227 346571681 454631532 786776515 359942831 974734064 284957045 775977301 749872229 714019761 665510879 476888533 41175364 888210644 426233060 239482049 611521236 4384375 253553946 668185082 322861212 824701012 681795104 355979745 375828832 505133906 42607569 717853902 128544225 310762508 470805900 901949987 485462903 830000695 133881422 65100632 32179654 800100170 606236525 141355441 721025313 121913528 589654901 242315873 402773580 122217419 642339773 862534617 186552917 449401520 453123519 144352024 219245100 872981700 930333273 906769063 334383154 401808140 967917111 697160312 828272793 750147700 843947340 435933031 626510055 978111130 5345535 489143744 749679028 90889466 894604671 222088490 546888225 703963794 182998014 411790120 843791961 941863511 174666185 588491932 347873199 448299924 136958394 459645908 432112564 419464909 782125773 333371181 555979712 309392708 693919114 645225169 100678180 145142965 348002050 665643971 533015331 61007627 686511412 122920961 771816115 201662248 375926841 615471967 27590218 160058983 709047436 872737457 842810850 21962669 313206118 773070849 116484047 537607201 754387882 251818497 917024882 951970185 792718019 80836903 161331283 189127984 540875901 39424828 135558291 796677875 277731764 473211924 672534711 482935484 928701802 702155024 469280368 783538864 642288170 64084645 562479264 804741553 871651580 783961554 209628319 869626281 826015073 89686983 449500242 487684724 931292301 801913957 707577499 481644922 838780047 897419445 248546813 780594368 832443893 995151101 86614282 332876393 956532217 122867459 238776041 896497230 257709880 984332280 321085807 303519616 480006087 323199419 485637603 651963819 760115663 898395157 905635332 839225915 326688077 660214688 487826419 742555939 656030617 488476987 197410597 817971176 545965143 36029201 738043416 843468794 207577824 953384819 554910413 425818403 10832453 734247620 42172586 637628086 663833767 541923042 448654777 364342193 643481233 509453153 525546669 363185446 501979078 157079326 841140510 480090195 288869349 379473741 271370520 128877666 162681873 126996917 250303344 821306615 499125483 703854500 65842575 858235956 282372107 998274406 613751574 734420434 801559975 4665319 468338477 679754165 762910552 669954553 240527705 300007722 641534929 378409439 46065465 647082609 466340431 655431643 705609981 850850296 419595971 194255358 892765568 76289552 216738230 821284794 462894862 182771164 139458136 329127960 664603784 987282948 157413458 162179038 256716986 244508298 57383738 872153375 132459540 242518056 302286409 826249261 582784140 346866992 367926962 474405373 324665334 534718718 637850437 356461982 155349805 274653195 221407666 430167238 530429736 875879455 344998012 709565470 537805648 929342417 47046416 369925256 625567320 784505607 148456441 611802446 371906595 2183372 542944004 447657680 384187759 128846983 954818465 476158957 675754919 53871188 160736731 651148357 816222296 823711548 843032050 154432843 651346666 527593291 732749406 190472219 404538648 781358827 715819378 340126027 82876479 946642802 63137553 444486546 304361940 384568702 737324718 752130502 606725619 128986412 107815136 27314002 865003465 524143255 578520654 341424117 523600365 494510604 641270087 784911474 100392381 68345080 330534908 155792726 191222235 717430129 212287795 35836458 166231746 504612705 995578597 569270903 539299449 707132821 488068208 346725574 637819291 100734196 217722959 773626192 109084610 540084756 480866870 981902861 432432579 475270657 652954293 958601601 727246355 820996759 452189592 923761523 562902931 77753448 636044590 159466044 412781673 271790173 176341570 887703365 687602852 611491601 587375766 268565889 545999599 273914306 666527499 102045196 290900593 17992499 474111663 597579849 75188039 177367860 784541779 793972340 492544255 39699743 920451457 411486801 767838932 501560418 177402721 634545790 654013589 220330601 551683170 742095343 239490605 892291183 352084545 435000274 88939543 357597355 703540005 592423619 69381236 12998219 614002228 687480892 80158779 428390375 462805722 50827596 992173085 903031122 856682271 107553104 961360389 607115090 804417573 791277349 432181357 53846057 47872338 761352960 294258825 236999442 898297806 808881764 920293299 89615695 392198438 828027397 425113650 242619382 484664716 60716813 121236941 525294930 430815949 704260374 500701984 301941376 431172659 716251054 135064622 258791369 657720299 853006453 427843760 467105886 549650885 716620267 762898288 12968380 889430201 433190928 71656032 451418239 648483224 183630839 336046779 231195075 522558217 829998031 56183491 423500881 118776910 269541872 785410740 47836839 275142120 332573423 283015247 17316333 34247598 701945100 309543161 152141848 502740468 350356955 913450028 757350167 797293838 804443120 274285703 302950578 716807802 397385661 875364354 54976133 726998578 370894761 665549727 424643206 565138249 128160670 587928088 436824736 504062758 874124030 823895741 390638288 748808982 86285051 993389188 85066918 340292714 542210220 120079352 497871531 739129113 622918086 683983918 305605310 426576744 429447916 664616309 868215059 335562242 570131831 535328037 307636178 835237596 73088683 412074002 619028798 797959657 217526730 576849825 747294855 588017317 807001967 234252048 196924893 114603906 654800734 379730427 765962783 771119763 705974214 745432258 450398062 663412244 527693345 350735692 849098188 917536625 910683610 990906798 963984380 796452693 740306520 335858025 340444156 506236290 319374808 329280852 375270993 735596605 391529602 992035244 271876481 733752394 141069469 105236456 835959543 806897448 563262014 876103378 959434410 301775022 333720026 297755142 80456929 635176338 420856330 310811426 574032604 19035071 453766258 423531883 55603073 616482389 658846858 469144678 562129248 347262159 195509292 481913854 166955069 779880149 947388097 860566125 3511148 817044070 971240390 223617771 957929637 518675957 453934556 337340602 923014679 810974770 676994345 489151860 846071214 719820563 852050151 389801555 489176087 899554020 181631492 880911425 905312841 130549307 421718191 805096907 465937869 699796190 120684655 235203596 842016406 123476578 380017475 621209125 357197350 484810945 903197717 131963752 420857135 468779988 742235685 693430915 326336431 160222556 69428248 256854210 235271818 304624370 768425743 569167957 230036522 160164218 534293997 600358171 361366954 923090472 612008242 489300315 80638039 870155297 776992624 178729631 739326413 328071573 872731005 995816405 691197527 936353828 146341836 934861403 700229008 833189756 202242055 473439108 152582936 216750224 826487562 879800354 636054860 595944475 932951620 771732608 20256772 246275784 351685930 38510392 991330533 970252763 640833300 682273061 277740673 848509071 547722924 364512671 733364515 704283537 815441667 786449807 31742027 756836501 128271314 355537773 443260729 508261114 791742302 364417067 594468891 84244281 733611065 404810856 505553507 624315024 987571470 912796670 182068781 712521106 109537408 690310758 119148982 756849010 524027583 162068346 394888406 410819946 328541309 141737617 708035693 6415524 61985095 980028635 444271050 535051501 775383106 198157805 495572189 613430104 483476455 692905618 974642430 323089708 375542133 529119033 901359553 945025659 76907943 621285063 96379563 625141383 190549498 813768031 541102055 370220737 754038875 89861881 632564790 979113777 167464058 496241000 44881745 32825970 603098900 111013680 266027657 615380604 577471030 454863097 675847661 340246531 796793339 537905774 40377048 720903426 861197317 193025235 21256606 387794555 208970521 64027125 252481577 490250882 589535388 11268149 322364459 52139396 886352166 887182825 611161395 675874513 306363453 2945371 106407056 395735574 206165410 716116171 977584155 844836411 319721872 371382840 112296126 219422178 31819028 420880824 801403489 876727806 959226910 471455088 878406457 524323296 406438395 92411910 66207039 667172540 11993537 624196802 695190342 749177922 735552559 322389612 269389125 942691812 36225658 868010053 116310280 381697505 96181255 849674409 440803560 760098086 501306438 108752823 721884625 345859395 395630640 158611688 49239677 554061514 244823893 943237978 890775283 629994662 280171941 753399720 888033695 532237484 700201388 67606313 265491114 200141911 45151178 895355395 970408675 431677949 618041412 445831604 784988690 819164464 588146763 410586966 319852165 120180399 417663363 850755926 45023116 403995509 225376059 841419731 900802331 240136469 710270321 62715185 300631878 7885807 721821523 774413659