1175
740507924 790215177 783164616 109338710 390190827 40353948 225424009 107707906 39643204 155728187 795361854 910016334 866514634 978566257 228636205 96438447 811153666 691750007 203462996 864387846 934502319 57049757 129346662 832978492 666782751 956210502 598144465 821843832 253284584 9643811 520557188 846308862 652375342 156238157 808163926 42566168 49108460 33587935 150274075 941268019 189316122 945635929 851284352 908347110 776718539 932436912 857301911 587872205 624186918 60764907 304776404 411205590 970331019 286639420 244184081 489630123 242849921 694844901 163990309 348650859 704488712 684547497 194959720 209380407 693302009 3123645 251946575 742410469 889227935 254737004 536194841 78544056 52889287 239995546 839407520 829607826 172432457 696709431 269996384 649135729 609990692 574772788 60341319 432838064 861412208 157041754 774984541 956778483 851886655 938974850 305429341 408891720 476038701 352905415 618272127 169340709 208545415 870218703 764267532 97773349 124955706 300462372 28833760 30361347 540457918 868241280 859969174 565406730 417467064 129965557 214542458 879974110 557254700 127400131 165328527 271183261 284441886 940313069 227961744 136328540 879287918 385907439 545220261 207842972 738812855 16008741 377183681 947358270 886227444 141451212 45131618 863699505 294429938 926481733 894060852 687404211 647239367 606546379 252810940 64706430 736511937 319869752 797196895 146282990 447269884 962525422 417466251 731711770 902838490 645427995 868040310 634642762 31335434 265776924 842485734 622664643 281785666 72185769 570022912 20529463 66153335 467670884 736745322 213099628 246668971 483322528 900503839 893908338 89868906 5831132 811131122 678897197 325700884 608328016 825180187 772970768 423369792 242646438 504682537 178724635 740590787 225239201 813367397 624442575 343532479 508369485 247107217 625318145 433071608 669646483 498363963 499224943 137317367 235109284 712324571 236502692 718431812 465344763 130411029 660817073 471175895 941542151 339714269 796876780 402386521 17410810 569847547 825756313 260057248 927046439 4480947 648034 4801993 670364699 477606964 348334472 31250537 724714181 973652618 464322145 246877018 324532934 816063442 236710739 559642218 380904367 473213431 130590384 846249130 603624460 791407457 317425025 397682964 983638080 114301804 652585839 1048889 536665705 330858505 113622491 316228497 187855807 114270526 321030490 858220506 444393844 669364963 741987397 21624378 495533934 58825895 268501396 820066868 874889337 505212135 232225439 255793703 978425566 362815823 102042833 434566379 6739633 271984212 832249344 990377714 238802370 337351536 843942957 627984429 668210042 957565449 944212927 856065849 924352329 265243416 566802708 368746172 934608379 308790104 390370550 282658666 367615999 658871947 102725533 95021689 16600435 334950973 350815393 995026002 550283150 305374580 429592380 557022784 429875146 114358077 399916851 668677516 451709614 96376161 149178298 119919655 53941609 93391224 828501858 978293938 211150995 395304565 199556463 145759373 556611023 442443368 280934394 924227022 101315314 383659927 19248710 117915749 571127254 222580457 965458105 121410404 380471391 247566839 530949542 810346537 361924916 930866393 331540406 666150884 27242553 480718705 638586893 933700518 574109929 467088750 764510809 785260924 714909669 964067273 783536652 271520691 259026994 64471045 48264066 212858662 300647326 920029132 183290765 871774581 142609588 148748870 845701339 375597334 396315709 376650880 185943870 610756979 160033626 517484277 276907863 39792533 998202982 915494756 973493051 424829264 235099860 590520214 62606542 950009529 407103840 698659548 74046574 666130834 615646947 122310640 878989496 916294273 894856126 62280260 640585207 889982069 63545484 338802899 265579402 459861193 715453779 304039626 70618172 728003759 821523903 200042389 767796293 672243238 968053499 593805697 949588857 55669712 36842264 12195398 5679241 443946104 563371300 932242170 110076937 179018246 907069164 989066433 947828873 801925290 903863048 440930434 544423712 967408532 779733333 810003114 279786079 347703466 114042739 202920605 75707224 788082997 402962994 696019871 312842588 223532846 142341922 114947798 279202559 179184186 127143196 137398154 623130291 543030850 69640323 733207228 722049096 976709487 574790015 522394323 631151130 331169416 963324757 28091195 298577947 743058089 838094309 578364026 90761554 804653403 781284631 18985133 445252753 36763978 715005004 610611695 260296825 857346926 725559494 539499384 36531112 705219044 676897538 512177757 248249894 599054215 97901338 822815344 428280055 672691353 345209666 59431185 3860768 161050776 87522380 154955070 904108866 778133044 585835450 847386774 435302800 219636435 718888261 733071907 256400413 286409619 343683601 369213592 143756544 69243094 908712976 32804010 626978493 438126867 397498121 875228387 37181081 495399460 550560084 317977491 20607166 895769751 229925030 24467935 56820526 169963764 31939359 813445746 948096808 617774809 513348874 235915961 837411244 84753488 968987868 946328012 371163107 165187823 315541603 367436006 86947271 76770933 252756370 713925764 367414154 650254492 441670504 257111590 145653951 992230589 575089081 166261117 740516693 805014111 43245406 649853573 974977875 75184765 315815673 775591037 545475929 681680901 11506997 235403526 766434389 833011220 34247891 137597496 850715397 349789495 505033502 937662668 279076782 757789872 504104786 646490936 260560717 798291644 903602526 406214668 643038586 478691606 424992140 236071632 136222070 468237546 885925206 111199945 395938666 54257232 886790982 793930949 735938133 750814333 29334474 354888875 436341906 63582366 492486371 139573656 265888215 850036227 77236324 544964997 460342453 433857464 43972286 720903170 84665461 947574813 127117838 727704048 278782772 404626332 963775680 415004843 872863878 702217239 526204788 121318897 756474471 265512123 915249846 344928957 868842810 797100675 699817833 157701070 713199395 44820557 297274726 831603964 894856785 227027404 229085314 207715591 660884868 273057600 928618761 745550330 220632412 908252953 325770731 499415185 312879284 289546410 914420028 38259516 991763650 293141169 12094767 600754474 411169646 927344614 798199786 280012455 576961642 350533972 437713525 142677390 395354529 734988252 974281354 142727667 962015656 55883021 350443258 475416878 328940621 131578373 73483561 549573034 39831325 399254292 901504573 205226964 541317056 668440954 243486480 385597059 961582123 255581247 986351534 225268122 35442214 637067673 505280577 464920210 987601645 795510457 607597600 235472527 383015062 434395307 378200195 197547071 490278328 581159807 672963949 819218950 712738180 598963864 221308337 752569506 998218156 122812909 957796470 392051566 643770217 53799303 777648625 457868693 161896904 616516512 683136815 197339119 253584184 40933745 662259329 93702182 836444202 122373283 329174710 219459263 409284944 707374905 417006335 899563273 141051065 942486638 571298576 853789246 541450502 645123267 458875105 392185011 620452530 269187928 784236577 264222746 322987231 414401556 722091439 484884135 30918067 257744607 534739608 137018606 298678352 49515291 230720788 135122554 171888574 559895498 207098171 581173518 119786756 624104506 333253144 260837822 419107498 757068074 114627067 960558000 402191340 573502172 205259364 22643869 842690100 842012296 139382969 18193684 256413851 713990762 355594173 139848272 971735369 890333782 276866878 270413721 939849073 507587667 258052629 111737646 67483164 465150800 545427518 187269921 89255306 731197017 448107743 360879158 488265090 415251164 173953511 742972785 988753336 379212875 618133008 683959789 73741524 757515978 554669827 330155375 324023093 910264000 470003648 295758462 800597781 746870526 418688537 592963207 106974546 676741166 557217207 174457711 141891965 102644725 214243986 83663625 686358096 662351729 444542783 27139539 77602892 618496294 770112324 918872582 850225524 388245332 455348724 923967048 998277664 10018550 106638777 322300756 772798904 576642425 470575572 425913039 176029304 889264109 18876245 283003851 566005274 576093453 309977916 560413594 531254532 524221902 644077219 70128981 39089984 941136357 97268520 116692876 412149004 867380845 888081812 262374527 108142530 195946889 38857929 106420193 58481793 145496706 281237303 831280697 722139131 751812876 109710089 750684789 641076984 128586335 33688639 59598612 557196142 196182909 620012206 88450673 720404811 116605778 11096008 759494795 57742134 108364528 728704025 322407493 975745373 469302190 584782020 83887902 665249079 623639949 42824449 576247226 769136655 324061753 260044277 343792139 75874628 369754366 94476928 569467966 498340701 980681922 629066578 55536842 29381185 101595137 996503870 749785996 70717270 7599877 509280791 128459404 115964406 90501169 303383251 944226133 559803360 888165272 28114035 77568792 364321574 70938484 653816019 985974584 247516591 913860296 182283076 323391219 283614661 129276358 892859186 634471717 109958280 374442117 542524913 139339465 328553609 391545137 741641815 399270879 251661368 103438959 380246637 220142128 193940129 683629889 164368261 753743489 424311514 44998650 831312281 788633088 968453489 485128299 627124025 215970080 251504948 809407102 391877653 535119610 938683460 137253192 22107680 901158094 511695310 564632593 893013913 840248919 956177730 634655728 92036151 207839098 738094687 472282788 427981226 932034816 155912676 444865841 538294658 580224190 489864491 369606939 221373632 310834334 707251592 848497657 526804414 958756541 510421112 918682067 346392504 449104572 55935259 368500184 202779019 420146923 933132777 95792932 112912195 889310507 582965014 204948346 949665959 173576054 677231134 230163538 105610870 685660165 675029380 496421882 118400708 17410224 866028821 339774340 328244558 425796767 40788351 855048972 384553307 551209463 626247393 730945811 852830389 534699006 99445994 55609408 807362283 885095125 3918694 920274478 626921985 586883708 977739178 576587943 760459762 507486665 806751482 718586986 193146829 334297215 215008868 311547538 351707439 933554043 503838232 679951998 359350809 544626583 387517323 596420470 948352401 13764715 179882634 801182789 400980075 131844982 709308551 60858711 16940107 713227245 981133189 643862092 300110952 811388720 72966389 60570714 318875385 732234225 631674054 364538568 66531439 846682922 676086106 418238878 632753319 32440692 98190875 992104128 577067275 338224553 441040952 377936029 204505622 620923586 31635172 605485698 752768569 740943723 666344409 769708676 454170968 499993952 266087121 606798274 163899025 191569864 519885342 482774410 923804089 151559396 847312979 990335528 850758672 375915438 261090760 483511990 408356130 211797989 328132472 837939760 550022542 769173424 215875788 754528165 242613363 247510960 212530216 995381932 988454684 731390979 617606961 295142005 83901284 883694083 901940279 247800310 75263946 274341975 730574720 851584390 425901371 430404052 694436271 129176396 658835845 955527031 612688387 67191974 19841374 793337213 757648088 422380270 415026990 973523877 29424788 657640353 73551190 241955004 653022285 914522228 973345984 123145599 62180586 57247267 6839681 964120866 157563931 934619983 90979194 888138652 638720726 516880565 171059057 333156996 646056961 829894902 141200381 111261701 749603231 13558109 904598914 359767672 435938379 172142257 185807902 465363168 829782611 259359093 707318172 335321249 26397674 533180509 458466848 88578261 442944131 317822884 52699126 600508062 104959220 143678320 341163067 743679946