1999
609148108 168170492 912291751 724461615 56257668 635835375 502764976 334022328 401803570 573010043 464917779 184499911 216921973 591046059 929817456 936025015 76838772 215305261 689417896 502457533 246965544 89631467 134958066 491981569 701696998 58894354 440921982 226268535 881286562 984097245 414227302 236851966 345373371 816811640 246767688 306025713 891379040 577818886 152696295 183861223 956676996 618269943 459462134 276063738 918196950 91655680 616684393 651588120 961733754 623476921 911348622 774209509 84647030 353657465 332437062 482842356 672461389 739825826 451789110 108856969 753366807 353762011 788845547 636727285 338968168 857536675 113945841 226758286 36972844 821283301 279919058 35607321 193198286 632577149 595159031 84331364 397593727 905308021 981872060 843744428 766276446 843094362 282601840 561467547 109710863 446849269 719196475 784960361 180005911 420780482 252081774 355142002 911189410 200282569 498764788 849090462 849471723 972105533 562808184 400739009 835379921 609369915 932760701 511310268 532066116 542065422 41814872 504435571 232548861 505129927 432164597 25533081 250381045 648871404 107659259 67303048 388041501 867046788 650558094 953543425 199888473 436356593 720655491 828709074 650164969 832884320 374063182 565878737 511705491 402438873 875066101 90986912 774340757 490556527 98586094 248444885 572242816 393383315 875193042 103815717 671124469 425552151 129974747 361331458 957327936 766750314 887389106 839252640 786645771 851137276 24720931 65399711 480119552 531676333 823172776 317879597 741881915 23219591 526379250 525321210 117712799 874084715 677821994 686438066 154991601 332602704 826668216 102368899 379982977 14091455 627905697 475186209 600105708 442747860 440171843 127809227 170345740 205603500 969175238 920142385 737636903 891795363 938635254 995840427 982261060 476701166 480966497 764109256 894032453 464989471 917020656 857457971 345785977 29105767 869488948 523761917 619355877 138457650 374655488 242073451 949021617 604931137 162567383 465924106 430320369 302386201 855751300 479860985 85859114 5253362 407129628 329010676 348085440 510426312 420709735 275611969 669087431 433534000 458672649 219919981 678463205 315351359 989494499 770076311 611455480 583428427 898119455 747225967 27399612 989782220 364033507 768343316 95073821 132291127 741383907 347492439 983294242 107245342 728574152 469081433 595819784 468075008 873855462 213558199 376272267 43679532 513502683 591763585 316452451 986046852 228253804 335015380 682951762 462057108 291997322 559679462 522362753 220143740 828198496 450472417 385335449 155176941 610342000 774869821 618263263 360644454 636436384 666533389 505464739 397416639 872891852 283758322 470377582 968180334 295978363 548543555 558223221 486099540 956678957 324472575 292132083 174077660 438394671 716271803 386594173 696837492 773327129 764040780 423258490 25381043 752337193 468015317 578193276 863185883 925517219 751956502 382840093 905888404 754558600 600936650 881932176 571435277 350589395 584953666 771389788 891666941 2006030 779981564 333392167 279370331 718458157 123745573 743069967 794781266 92714560 319057431 584392848 512143510 246218579 691996662 98555050 671390738 221543411 259764878 641002032 549506128 312428299 118625500 425541142 513910132 258457795 170914471 297107086 784918916 863933536 747523239 564758935 83062628 780501786 238152983 862661439 258281429 330517450 473405690 706688958 153172652 371082631 916096602 846427757 361865438 298696937 52735663 891847488 745848065 632377582 71632933 999464420 202808228 203426050 950291992 111386597 656623788 893503807 687268738 546664321 672342816 932449873 707611995 470404504 481564302 158020865 997987448 51980845 758442690 749751231 932891749 502356798 576401291 936822087 826453880 612998100 212737200 429381053 716608227 711843038 190715835 360481522 555690508 895395469 750015924 580036279 674830725 455363313 546561951 933643300 670550289 813846598 702763846 593879993 849864655 188550420 170213047 445712937 535057746 683028067 527597391 220557062 248656670 979360163 60858332 309729982 536210747 57817332 736134696 32189167 594309621 867497331 394439299 643835017 154406620 403497671 978272540 323141119 775943124 76465927 923545545 979619746 700990406 277014124 506936831 111349528 284282207 882078563 904802794 46838612 230349142 269255146 627169586 408516750 487340251 344548663 687335810 935257514 869016962 899071948 543610308 859370725 974845771 783116533 716848677 414058048 114703179 432874726 791817143 520675048 759958936 34591692 387581192 857545329 674057819 54470132 227308296 330222780 259824657 800903232 774926624 884536344 301202147 638470982 809028881 979457394 413987859 185964354 275040699 826079168 822560216 604507088 846276411 110661208 329649075 994102271 782554039 444898394 588536712 662084090 103592193 715068640 595124554 212161305 453602206 530564164 58644939 188548121 203646680 218344922 112660565 830205975 934375389 970373439 239883801 247046088 945520054 764451912 205206348 812970165 339531403 439904768 478138807 550463948 895128518 532135478 156325741 432604620 767800438 712376163 326047206 796748596 430715501 909347745 207151534 381226193 921696900 979690311 159714654 700182489 520432995 714419159 405175760 637992534 142529832 287815717 353102274 320109090 191902631 387585724 945117534 642348281 327689646 559282838 351717231 124450412 818884978 681262215 565284068 951003035 297109428 101026647 183872174 34128319 156992018 685845140 617778365 940183163 890458920 669165059 941804473 977371706 507925020 75993206 418300071 649384557 374948994 657495419 701355234 949856332 694334842 70128631 256841315 405438800 817590836 92181730 75734568 987551163 391309515 736036589 378116827 938984098 225403022 149201382 384754403 472147764 203410857 388575109 623575998 887113809 395911216 172340782 535859220 801748840 733826219 220733476 375714746 159314692 872649351 771607778 295474171 965695505 233466783 231144916 118611562 22523605 332752101 401174522 55774196 51604052 70577991 354880673 300174684 145789417 88981158 715175730 545816342 120053228 894067069 376601930 491353178 823913322 498823739 786709033 529205461 520786106 417648344 885377726 54642592 766026668 103856640 625466690 224693360 581672159 580703147 117864596 172803496 827808831 629902244 5644472 631109816 724478683 888129523 664985700 587643548 173514908 356665293 493787820 665899435 379943717 202664744 803252505 610550108 167800957 748760883 223187687 969455686 276293672 119290242 621843685 640846991 571986738 678907293 390980261 737029058 305840884 319074809 584908511 675071530 23771258 470051713 228629373 788215369 494051915 38396081 254474805 71816834 54268076 533258047 683524747 255189149 688120185 124353497 704713529 949766271 101666370 230811371 833957642 361180786 40041508 157271982 64455167 631417157 668762805 881050716 472874789 791878843 61862564 884598686 926331151 599422885 219894158 637919166 490748203 847871417 136851867 11264518 194312809 693244672 987128561 102027223 191544936 709975361 892609258 135124219 589158554 289008165 526677024 179982743 536054982 305293237 970061431 103733319 249418642 420685833 218620745 410822886 189126398 372947114 593602062 683569091 713011923 784362414 761454081 534573471 214347438 446412511 66628111 6380336 670586052 39776862 837643992 712065911 19556513 165041678 878615131 101030523 922042485 973507902 395089508 771859847 892724087 645364353 492074647 349934593 833151483 273324592 699977087 966877347 20111793 967472893 298748556 576891657 365527244 438837255 350742099 793282225 872510162 43107006 672036133 603678097 860526538 443927400 914957253 230775563 746279333 446025850 829965955 823442271 669664488 91209145 598226580 432335126 79167775 208662575 573756903 279778299 513558390 749230276 684558893 817759467 124306817 732183613 670695337 937860125 436973257 246677329 281876423 861265400 403219768 981819659 976832615 845620799 76760364 778702425 749415408 158905988 404038226 919238240 46177318 259349160 205821949 723781390 712469954 346107371 492397623 822164281 129481581 184991893 123575185 546660124 80228095 395184083 919110955 658775179 374536443 550478966 546748267 1015244 731271997 336653904 594897186 789521887 207587670 412093805 48949337 263810766 673491250 303846344 303540729 475512981 179956833 76635162 300223923 662582916 953315696 826231526 216894509 989787396 122495957 117236193 692737662 13993621 921821972 165803293 131243386 511678996 179329578 165182227 56162351 613295674 649340885 927129929 144703744 563656768 617595896 207197293 5060006 600771088 35967145 899433872 259085441 862076435 999957994 865685259 443326939 771556421 174602576 305423560 122383352 802761442 16834301 560878714 726498849 176910757 730845995 772031244 157182710 981320821 802361082 962665203 349760709 991739685 793726924 345006956 625880331 312707455 620028646 471439755 794922367 874841837 244467254 728424731 705098691 742777003 60260661 912663548 946032459 560762230 761770463 194375149 845766443 350367098 610492659 740748700 141225413 660863650 696021214 76665887 4709285 57101197 591614765 810646882 130036988 644084478 334079111 578044049 263243159 222316053 507517181 405492844 465789099 464283299 658722815 268291243 491454450 236418897 274421395 244963148 434089118 532765930 224582196 504479012 568975417 991230537 125447621 375199251 766531043 372478772 348597348 604735107 331036672 80799695 322232680 696202421 463676270 213471016 728706857 633627100 467871040 92528419 46349490 696993434 554252929 70421881 860491203 931607603 161833854 842141250 472052882 813907623 324949517 420872090 876281925 742423189 47896762 503494351 529637949 449903478 886407945 882638654 147465017 993273889 981933283 884450212 242339925 662633887 108309233 69152711 557634141 469881344 25550210 664550015 39630898 64609804 633763625 495974012 930380699 987080368 418927687 226994287 957246060 618281812 771754630 645021400 976394344 918116352 300035435 684613145 518881551 286471994 974776724 11678258 491307307 610557544 594121034 964555879 295958282 996768210 460855550 103597243 773505104 760524587 840684244 358333098 957088521 961240847 466527408 517220096 824235677 705476932 535601270 795806423 263349144 967712738 731991570 699075780 237763476 993438543 418863159 186106913 993948976 104978600 579496786 920562062 562005689 182521866 683196613 314896969 532224153 804757561 410100722 44389932 555095262 134042560 763267548 353110132 717155870 530129929 507472004 578581537 263218022 959436219 170593224 639260255 984313004 28835534 81365575 168835053 505699329 698642648 112774682 790341350 139116767 399949366 980500287 788525719 132995391 331783570 14730280 798609689 456167918 732279405 816695975 877025071 676384602 294127372 775664688 423290056 175389086 513860172 990496260 249224669 966382703 267053283 134883499 455719783 697643861 993505394 908668894 143617177 434292611 451100433 633988451 569852715 314862432 256978288 223711271 21519404 17126918 560969960 218953665 609367119 296181416 960155325 115247908 267697742 866839571 69569733 489429243 285127780 363995665 27619087 841226542 322507184 619732111 598725511 947239317 470450019 173831889 611139697 668307984 852773245 498762859 695224784 395153159 280405918 614616917 673916008 829952326 157587648 67950355 925125658 938894439 393444971 427592214 361147068 22213479 515265897 909507627 642106435 547376444 809575590 735167685 879288137 400156540 454240203 138021753 828284819 978800657 372401174 822761540 547235033 618432740 984993288 538458643 427564664 451886896 202046445 667767162 874227114 212664052 564575013 527478145 613229896 928517250 906804579 496888767 772956016 295456772 839512843 562028835 392262236 498393008 588054685 975814907 711418179 93423057 388578295 701972244 703953807 878892703 712553922 564397374 645632375 954332762 818197349 907732953 440840396 648236353 406340898 361493286 225863182 922769090 355542565 377424388 185789250 991843875 456311191 670049932 962001963 373454147 563208862 352167893 102291502 694813572 652928220 908885110 665055725 247370197 961687538 547250411 735669549 781397877 329839701 542931506 557448187 393292322 22039678 616588454 264943538 855254241 202553931 981496313 4640602 761973838 836106569 241134053 271468859 787012400 113216766 928128588 880777659 259213454 741785552 584839079 736374012 392156627 912652150 471411639 453586757 288012988 762279017 653780681 901579694 93300209 910049577 661827579 580328561 964874302 8994802 709269704 554686826 694399395 511364644 447122132 436604508 499618704 648411232 664865334 166434555 639828760 115069498 321285992 104599860 404042612 18406733 304121505 724531943 407627095 819419588 409212606 111452699 767217065 329572422 239327912 70586796 467019775 387480632 189527415 542085546 330145287 740288461 98065661 862065102 369994941 38529324 625827078 210869251 554993891 152278555 907319935 255578829 955769758 791978305 38292923 461900391 607548492 690509835 118913880 516928386 910714581 999219933 997682772 946041815 454701534 114018084 218441618 931948860 783043693 624715815 936082639 556132525 233427660 864735327 280249814 895787102 670132656 71874445 143128284 729225095 508053884 4029726 778175227 260836273 917082571 136016465 944080512 744030282 916781911 69858815 823286621 865868653 308445150 994618630 892652314 535019444 98758559 42599641 859580295 319227197 373529793 320731907 650330648 902329388 170767111 561387647 512843854 503281209 959270058 141015771 468534410 50361992 185660609 295447518 922965438 331737741 479587043 446639481 913223036 33611323 368429588 83047216 568092913 550174075 356839681 100873523 559040121 372354940 229178862 82909667 528492854 875552415 326823536 425667183 555120722 901191875 199037409 103625454 463966890 881469541 673433795 257761573 64195240 239111555 301733420 932180395 747290881 25481151 475580625 374892945 159766898 11747846 360940383 907698449 888786987 103111113 254951554 525578664 591745953 283585820 562268122 813856254 353894759 936863725 483598533 276763453 830379150 303774104 81492639 450662580 661855357 149112633 749375727 196626897 735489389 345067269 336353632 762298882 959952634 639605867 391069037 113358026 353907371 854774475 174347335 935422452 495554847 927158363 207254175 970211700 725819922 491194533 193309454 741568540 573156449 182072746 411991952 484873982 802782400 301929996 505929867 242938021 119566718 537190103 14678876 445941 245051794 675858800 488216499 624106549 344191769 747483114 890133441 812940554 860338049 911284262 281493562 532056086 297178836 738124334 291734228 201225684 609703313 177921517 271352641 484363446 623166412 503386935 417702115 812355582 513378729 955413507 308610636 566915962 411977302 475777061 299844655 765014801 716512743 60220557 24698352 935338077 259334239 784622830 247454425 763130947 685953964 202062132 76603698 752679862 55675280 486108113 706222685 128787670 528386566 32837206 430960698 916918014 336027087 562417967 672165561 828886413 498788880 224817948 524937338 927575271 858187846 379557369 648400506 407300209 309643747 591925403 286875443 263207507 359720699 314437297 476085991 719562953 227585740 275835170 738731373 930662770 473698053 820882087 830622456 366961225 187478146 441332726 981334474 170191188 842871692 30802485 515193556 76138626 938286557 52580284 769100299 954749354 146111138 904428675 417401021 933197021 994055459 7942668 781486910 239317676 524873867 675603134 171730680 329380364 380070457 719893823 627774356 980395036 939101848 249159349 867825746 832995331 733484482 444253095 316546826 745965519 616107192 576480785 682534394 138740682 886804768 702780016 863933205 368488067 704279273 801459717 554185260 257119717 149916543 604490684 836551012 419988799 169977468 789653843 72481736 952137939 436578507 516408076 566536600 841199521 871330770 294516508 338667769 954081153 360610695 34644650 692416626 989891597 911267535 506083203 228596604 735801757 80802564 759041507 127928491 759081150 989559748 156301052 898305907 746497402 575527577 382152120 330740744 831037235 792158934 260962162 80928340 15576891 284126074 496397011 224375804 907881686 691340230 26745341 843787191 503756681 851605342 451723931 845665431 326274201 474604045 871747195 528217298 314257539 909767073 226804339 75002165 599064609 967229910 768466971 503563376 918067081 164418000 599428053 582862311 781484269 91398244 913852777 683762418 239734919 155569558 958509589 990732681 435678211 803137360 972931269 655755076 339119561 492812442 426768481 783768472 767968039 424408376 13443009 403738572 186326672 845677033 900434091 852238311 739681270 362637976 742297838 310036417 5142154 692980027 409980225 883845616 426821964 221523953 303107353 927865779 89061677 971156306 199214432 446674998 591789645 684629901 610025494 127706159 107633267 671944358 517209694 803424636 700094954 983922523 426323711 405493988 529709672 173690394 353826489 209349467 865173305 198435702 668005898 420183344 835207901 566919343 510785025 648245919 469014508 350841791 216677469 247266047 525349634 971013568 194830470 941237012 220245682 504225495 107575308 401901425 471519012 988298948 375702110 312156577 699645658 156093513 68466334 759983867 333452900 537134020 786996157 279826608 647072509 670425382 79351799 553126230 501993648 634838569 100102924 481854208 699339385 393901010 670845832 909505358 67957784 80900357 562626735 214114574 921162287 443058098 608181089 930282059 421479824 909421259 116882752 841603244 193041419 758632999 59930998 427450286 447776117 224955148 917125620 990751486 709762111 450016343 646794377 370842892 739492753 296555702 501777034 235030938 794543665 401578598 436139572 256266435 167768167 396881520 396429159 830783709 180961324 813561565 345345730 316722245 484182577 541597358 547073980 345834160 861393418 522355693 575399035 635307529 306348781 135018618 962112077 377146505 857288741 538185842 573033411 281822246 654699103 403598034 287834090 198348303 979419364 401477990 473645048 81019050 847911698 319304149 608623503 29711370 790501605 746400676 695916837 496012372 627852056 18233878 551589345 690025229 867174543 235209979 29106921 703929101 877564204 292839483 754057527 529747960 189363911 806799776 563482792 741199975 34527989 700761868 229988808 414611668 771196668 125939511 769787892 427543334 736191672 565897965 964720569 820268546 500874557 966584231 861506117 552318135 845407132 689090125 209915061 568686834 20836030 363749799 91287531 800741351 828678099 337607195 143319148 497369642 820260747 926820453 701141969 694275787 368830292 84816051 412154660 893635815 65350251 474686661 653930100 894048439 699775700 492372653 961710080 114675583 303595008 621611042 677284026 265260783 319733153 864743280 997757513 399895121 296620604 124752298 879034474 615581944 947947137 129697700 381344741 819927291 221951065 92357896 595042114 286623288 468444365 748865437 962394288 69506353 258623079 293882207 519191995 999463517 968997013 925742686 227271318 437146819 448376445 224878479 697594542 367526400 545864454 229690997 73586201 858591541 16130543 394563226 794303085 328396895 391644561 909566044 665069172 831004208 35819075 495240389 291337620 35334414 170126047 976418592 115244885 171843895 435123259 41345359 947764836 913812378 73736865 976438970 350884229 246937205 424269305 893849148 549061276 359883331 81766564 353844718 70397497 662801434 767077131 930276885 648444864 443907057 169475219 504779727 509916167 303253463 189305034 642660961 835218274 28711270 364520179 696460324 584356285 455856502 865427028 400363488 18970920 764908674 287924056 187807198 203880806 9275532 420075979 29171788 481460693 892475453 760598819 441556183 40912630 813421037 981518544 978418365 188820989 501109084 770694838 924831360 992942705 268059329 90643491 941482482 143679271 149378692 944574101 67308365 375265075 115179259