875 366
950381749 863024839 428911317 658057529 620480489 326935744 412222637 681718248 62745910 199900096 60994016 285459586 942064051 451032236 97229211 908132894 372322403 987352663 422865629 486622933 934357874 582510861 422540795 827327648 134309167 640864910 83335302 865896388 691943712 13799728 943286874 856277678 998401463 319985366 82176063 990421763 926533411 108350157 826731146 964659997 135065156 272678527 989952371 8545787 400782302 566962453 931674761 189161651 940687238 84714694 861620926 197424971 399967938 916084810 45112741 785082278 153196149 983538325 261638607 167058918 46334210 268038916 341265772 191796543 166716022 580696767 425392538 889615429 350878107 461989418 974095987 281749053 250993859 269528901 616870986 657680611 539269186 804866221 265791261 92304121 253995899 207603713 86130461 453919443 159028010 708762941 54664385 932437606 158039554 793635661 221026892 555436716 202937517 417201615 760264178 441923333 572436114 307489485 795058328 307147124 290794248 244727961 239412542 578636676 203298567 89679515 541004245 594348193 710241804 440105127 225959179 759805999 449194565 790507815 424028280 426401129 555190267 813816431 759760458 540007107 718913513 706859407 429014529 43975467 753230919 155402818 803110670 868434670 923025343 272462114 835803865 606236024 36394600 670556666 299850385 296995593 901899405 388956371 6246953 771887832 308791550 719878970 165537013 830734384 33877416 519472 288030203 47355989 579805987 600694619 729997263 269470724 880397598 134849437 387718769 578410476 332087246 362876513 907267684 436667960 772860045 982427659 683485394 409394062 871627080 169472187 140445748 26698625 800106749 108617714 796049542 232799202 146800555 150969983 829158288 804239106 765664326 486905456 817555567 95049836 59952195 491587370 300760159 125087674 499502007 180725066 270973804 143445566 356047221 419337801 532502033 470314718 809844510 488114943 33436382 547469643 613020533 727473855 525018972 36656584 548810645 951121810 569346882 792701842 988244098 381052676 295754780 473103199 26859078 403353819 523302816 503236089 76062311 380573334 895812215 91455781 631633909 882987540 505170779 420432837 349349998 111560181 52429080 255767432 611940692 546180872 90629981 836060561 564058042 909711232 83918318 799387358 349179778 461369983 623634707 619623159 963519686 459037125 651749529 872024488 653231023 157642921 821350789 969875138 993791343 692296616 58051224 769669274 689871054 616645805 278358706 9168433 71928069 581732433 644081273 307638859 592879327 202542512 161592133 160563131 282250520 439041082 298627331 505609123 894800330 978809939 380859531 372555822 340893116 835656 841217536 2827456 964191414 973136287 435963667 257682632 626097780 71949066 38353772 157903640 220235422 283029337 951816439 30931260 436022295 335442587 154302393 267955245 381123669 468385264 196170790 922587735 3518148 538579523 213367197 776591447 303876312 441200335 203390546 797024934 466648493 473996180 792940885 21346043 588064516 876680509 148976766 675235974 704539083 666296634 421963497 352999063 374543856 883872770 235334049 999268283 666097419 357492303 698055300 139750000 297862795 60764644 12574425 533520756 246358430 858400420 714396759 203149683 990442727 379674507 742718816 344657281 320761343 596926779 82565186 592157511 155277759 245393056 557857530 202754901 422327498 793899998 203401258 539057219 41477502 354774268 844449445 490445292 491436048 698725800 879563686 380557004 574024408 14811246 807620212 728969118 621464415 607503421 985466307 418021409 457394570 540396375 603243533 438956151 661306961 469957897 866066763 674442705 945631778 896047428 985280868 926723099 16148648 261469283 881398905 873181710 796970146 974588938 333133741 445354783 101275040 136997859 282692974 795870205 978998097 280593311 523022126 946704658 854221042 87608298 302430871 292948345 810797834 511764404 2131638 762770253 163696456 373916924 348621497 793960109 171458770 1532799 783007586 833333525 524113492 126312882 427060638 558990869 801796971 738152884 923535679 874020648 364776605 859871336 138701807 989397679 956885327 731223744 705956615 277495845 527007456 411002877 274234667 682092867 83903931 303072781 169605441 488026875 868894508 978786935 372527332 461510752 433172358 858386810 440558806 179219827 975894430 640398602 300441434 323503487 770323325 948179666 45490609 635667249 416383246 567400609 55140401 585768462 443332870 986250131 878363944 541603750 600511600 35574460 773747661 415834054 228540377 569089828 720693502 226850971 943717262 968702152 649967510 308219714 980048858 213049178 225983929 507318203 62776171 389084922 807797248 674529334 795239373 348887021 250515595 190550052 94388849 340571274 269234337 633644046 497063482 710048041 889475013 810648030 675947868 892539688 237355637 211849103 247269804 457085532 2256099 636475396 229226681 823930899 986554598 997995754 561525417 427700757 509820485 704281628 71935524 951096031 245072052 75962861 423596438 360987999 426928285 410820222 422649271 954966335 313330017 451854616 885233258 865829967 907344757 556535466 851905764 115084819 211489634 8223403 193823990 312746637 243528977 910941030 220915677 214859152 478907372 600896942 280768798 544291468 662394555 230108587 472217859 991588492 575894669 884433876 509339111 45391892 512087587 572101099 827860116 994613370 150582756 982459258 582074652 690124170 755814401 663350272 650530360 323431272 217242955 291501898 463423681 221952575 742735573 85450623 606575873 398157209 721284559 411460191 367919145 613013319 536240250 997828866 176520720 681511612 886682824 454948985 633413194 287683631 645799364 852902889 406994608 472472539 648310430 395421402 946511958 194844234 969654043 208616284 208572946 7273015 943987309 106571797 375460160 267877905 272142313 422614949 431644798 383131009 423145783 630946210 484606225 221374679 41054069 977875686 76691712 326495317 753248608 48624867 904110804 397767504 594206059 3683034 94582790 915509875 250216757 278368687 236041325 616256073 957807558 151376779 224768879 359994536 449328136 319709510 212490427 158557752 93616619 307874910 767037605 832059334 97186185 835649520 175428956 341044406 93448597 369366434 592381703 350640052 79379176 204619152 838328918 139689847 754791407 166686542 622721077 312946295 660825749 202884625 626094613 756908343 750616079 469385227 705982737 19960567 226692201 819848711 14389262 464804961 418701160 132082468 685087955 845628222 485178904 192615096 517455636 509246254 188145073 253531849 933226421 919222804 147741215 630905426 557383517 401949784 105280056 844076131 81057092 387342374 221096778 714421178 510457483 286731638 763950281 851448761 261510547 398637322 615819135 239662226 251076645 751012822 930273076 109238878 162816374 360219058 281467783 521825236 728661797 911047251 849176882 574880603 14182674 596529152 704103583 288130729 460100207 459450108 147714989 377755413 595633022 987667117 344005118 715441319 393812689 214794269 855594074 917789612 530743161 627877393 297543983 150987517 247324887 617244797 948512952 348631462 224925795 748381150 498691463 61097718 722473607 788361268 548942856 606781359 562708419 135737314 74924915 729047016 812092748 906821351 341278926 650030905 14921870 901979747 534485123 229543232 656266715 961155119 243933373 172741556 365790735 771963673 196522645 579979704 517652935 581443587 77665482 625197953 276432393 864118333 915509111 839285176 483743636 930339391 496470223 408410843 529729669 869442184 913422897 180656389 378917214 582427932 163036250 517387921 179428007 699962175 94171777 163804242 907435582 750647061 715812997 69438831 176688429 476530577 478056272 709384436 16500772 348463514 849969730 899626297 46593043 709113348 801733873 621386382 586198999 728149893 428630134 521915313 138018331 271778899 411874161 716198019 544725603 632269946 925937214 435306727 390427708 597823271 201236151 346935187 982358472 187010078 73506797 144915056 696665888 92571597 956433856 382521350 27872836 114578317 15627029 986414921 627349956 814344576 235076328 904533894 527203874 326533350 839843350 54090992 127934778 567041102 994563937 209070929 246374661 126358508 64361561 959120339 722752077 990440391 60834373 767241335 354547087 125522123 850341952 408792777 157669266 724562967 168918357 785921327 100391570 103160271 590740057 64377159 179265910 149458765 105846609 286590731 56587378 786897450 823918882 337248518 718071213 213954480 924612729 20772857 715089411 503273935 855167411 813894470 416451000 592273147 359724071 320133647 142342336 851103662 195110720 544616664 799908295 820224272 491988950 477463945 813687204 119608423 788045474
543766021 271587484 277138932 14892286 602868828 7425109 513913637 661638503 99634786 18196776 205303774 386772104 95939847 506754473 369141869 794943626 768289288 103920894 555480569 174946005 103108447 262391862 745725183 826892001 390875524 559817809 122393254 458166973 17360630 453594071 669351055 512012096 990096356 678516078 306004230 531936894 981370418 34640530 260748311 575974009 332707296 952678719 559124677 811132071 369433289 244444219 558581302 91216380 259850441 741388022 696419595 545840953 762674032 661714992 900873446 614007431 573578989 489946175 978294131 299887022 52938490 144127375 521474273 489368846 426725669 782670248 710651498 840097691 67631364 254967397 388728121 456860210 647998668 94901795 806486509 2222433 447808839 267922292 574743989 473089691 320308601 380684582 357303357 891240269 751991067 405657613 570248412 991651453 891453464 848120090 671397834 868548790 424612646 676996896 70758580 963589865 421982195 681903525 9625093 713639806 847283478 69152105 725813606 195602670 437782273 76590142 768641520 812889896 299418923 880475314 218820755 26183433 299068472 155137954 71020948 690356885 133513275 497719254 718240060 707609247 376833935 571293669 569023621 367362299 594270724 275211680 713281094 46936023 99065850 49356024 520889783 653855041 488987276 396323928 491056716 34479092 156722212 693159239 886941192 286170485 50461875 74363394 484245884 418688037 807073545 65067496 309209581 178141992 771535898 758135596 756311691 147697740 607281260 582933450 51524137 275257802 133121576 226671778 626565332 516722598 413692532 690226498 449799874 940229754 87374413 870844449 863225695 286835189 165668690 840348941 984315218 244691929 73482053 750280616 498514897 478133289 598577999 281829305 100415225 242502896 312968956 260060839 842941244 225781077 345867993 955380915 347466046 271416320 418260210 606387270 684020576 313380034 10547251 776857507 209744012 747280140 55126025 960974409 716448108 60008246 577204110 284285567 475078647 627530943 864129394 208712583 354460419 960061105 732073750 223552152 393920458 123782116 835695543 391058616 595346151 654469652 621196284 769038470 201627288 61546376 17493979 985208534 730392473 717407405 671959992 192921074 588092050 5849942 53275040 905131162 820501673 865598660 869021055 989951543 862833614 455250542 180534838 750578423 70722805 813232177 726159252 260681834 997388649 475807978 412649683 409806515 214125174 680715594 825584009 976869943 693362054 427179210 32333882 429204969 276552357 849759344 986018487 674043069 713717123 150757247 653011117 583446687 204429240 555407248 70220980 574016312 581945178 228779690 531898898 574992733 493915928 350671924 24427810 830285181 472585022 664928055 520926192 261862646 376318610 40931942 939208353 422149145 567451944 519475117 130499516 629421842 614263514 46150306 505730001 459042219 92521997 416834431 149965684 596470651 83669334 684971892 959988945 11261016 675947261 876572113 162953833 686581797 587694538 818775451 17742187 553467465 50272404 960967741 592338713 145583221 514915842 697459705 354677063 112801123 767051493 413752459 917681521 740026544 14512632 697694890 306934274 868801565 921618149 745639077 496679161 391086921 829382848 110860746 255348896 966743528 605642835 939808490 387352430 24117130 31592195 85438317 581840596 400231546 296826027 663149774 525036074 113649195 424099182 725848067 86809833 508672856 639212972 81318138 287893032 153898109 562819418 386082384 458833465 490819257 507556133 138748170 703770367 908731128 130417930 593130626 429526463 504062386 123698309 226309191 938889784 627708049 367763488 757484840 9629606 977292394 265231018 457731419 198102187 419219432 277817069 286600448 141562167 165390617 723244360 955095324 382472955 826604140 666376224 704063461 416523115 671793746 567792060 828368627 66380735 997411701 905071575 904832954 4213220 206511104 234034757 614295821 199041510 671271704 355107507 540995608 546818682 853987520 760248259 190153547 394467749 398301407 679337095 903861417 166351075 340036980 752277038 840146856 185219706 974975282 227283422 53231013 861508350 393609906 353717395 868198606 751153510 367472060 143582713 298739476 280090888 216057878 438399545 462723903 862785542 525011760 316709238 528509051 757443438 306987013 699589003 230521325 918969220 583867365 105167486 654196469 95322756 985510436 66007817 373056351 63477529 566837717 825158003 293824845 719937396 639792360 797862686 336612252 906816795 692222872 95507843 798052476 561502457 774377217 187754988 858687606 914544115 853669522 142069571 152015976 776714572 278952092 489054701 965339300 78915366 313620905 901707967 296063629 166109096 605499108 224779939 208481075 839397207 222367175 978370704 27755349 885794973 837840501 439308243 406950018 687421282 832825132 12567900 496082236 326996963 737491906 362714946 333739491 518397885 236923325 714479064 521723348 810827307 20206028 945809931 929337473 597444518 863586845 959471250 863964745 615846496 44593635 939794788 977676620 553008204 551882509 905688987 298502605 300391912 906489514 929328269 519220012 305236272 699940119 274785515 939689226 843863014 362995316 750512254 200566481 655368682 835520434 90431110 431207085 917085165 8854372 418266467 360323964 448718560 276810326 756045274 559296279 692990205 217458601 632933087 799250778 77714042 661313323 716838325 423401035 763171274 670899462 834523122 873988463 618683549 28646044 591024037 98725632 280018902 32624887 960806647 708970212 30826344 642887138 254852265 587589986 446649315 585743821 449522843 956666860 909466208 113740878 824417060 667815435 809945872 981742091 397142810 853777179 828316033 276843570 159619906 498995477 934436676 747369337 791778728 451166155 115203111 701068716 868824955 537319121 289106356 992992997 86791001 144453304 798694513 20260722 29632903 788996761 670985856 274448461 765879707 406481602 309229700 58036419 401489148 737357033 128406930 79527016 479194621 522409321 994246536 88983342 888918041 822714243 824417693 232076387 55032798 441367542 77135806 729411036 510858449 170008942 221801321 496647976 17572682 723092120 489304447 130220072 337786384 192151807 402642955 20220334 593635823 149403337 681168425 323022418 175488501 836779429 588278750 711734742 31948112 707632544 18341941 524930044 228560002 145524550 820726901 85719078 542133683 894644315 38032240 50872726 934794674 276424094 901460726 71436280 497461563 944161030 588506165 455271394 919308738 585507356 129041496 272126452 292699560 998376791 504184955 507093813 813003008 974478000 461691339 707398566 151087170 92121597 719584259 700491342 128467415 738163850 436026415 886168142 586184394 2048010 682506110 208926459 591553965 846773580 101329860 882606504 472728523 555100780 806855511 905036518 817550729 4382477 451557402 391084593 650909438 599185908 405111232 980795626 604800128 940563753 702243818 297799634 996117555 257199390 53551300 330426976 34662018 475509117 532883771 957211517 567549175 992092416 36464903 823700137 55393672 376386843 308119564 581917 449296165 445043458 953861485 484245859 728236432 773066444 411344460 352125211 896697689 263055609 828998537 380616600 251153569 963629649 272775812 693502127 45916538 280054621 740443008 413722269 241257595 491098582 146530399 34335903 933468550 844310244 655188157 255942575 28464839 941156513 565417704 240957807 323347829 189898198 972926605 586994401 767595405 760330070 57626368 854050660 707502053 424507394 665845727 376959098 655195565 62386053 177133450 2060275 215732685 816704418 628370948 682268887 756269 28625457 448097418 81837763 56820468 937824344 773080612 622573551 307180225 359519564 152091925 323934325 920204463 284021174 540080593 408633928 803603000 986492747 714249202 78911679 640254480 796108194 753723275 733846457 772115675 30982823 547958117 218835687 7729825 472028101 896567406 263841299 514772436 21473458 24785533 684006198 138197285 534920907 415875709 228915566 518766067 798850357 970705202 423727972 61517488 90180745 759899919 664762236 734855023 385406094 32611171 682476612 542753202 672343602 249745407 623260151 951429828 819478907 389241547 600384920 866395985 565997077 682075759 235304979 349489055 615227088 27109151 669896200 277228177 129055340 989680953 52967054 82940387 502208998 67317148 801542813 981710504 134687080 32506052 696227334 416669008 994189401 360860927 266983014 638221460 341657609 444697200 793525498 446653445 845400654 681933575 269131335 81152222 883901154 319441258 739188978 337469832 822403432 164267497 519757193 556689780 896378385 204650235 807406507 526392863 59048950 31749310 869712054 787281208