852
778497255 718250138 722114199 402790057 402323779 680157051 899514339 684015496 451807109 328910337 360562762 20971265 342735411 741744716 593413209 168700893 920351632 239387387 472259325 478243347 316420250 888595591 504310397 277264927 27275583 987894947 588058845 672335707 534479802 156415164 55654271 992748392 504049781 211659652 70551687 182513674 670795926 594019405 956780784 196083190 723876974 40135141 764543276 105813358 131964195 774894215 38052172 473955356 595037092 979413328 443068892 564873946 662286519 68737751 582022318 372467275 949482488 420328712 136731987 202777118 220652771 705949301 460087091 670632223 449943998 947085537 333203982 770459515 899295027 423712634 429482401 575413845 730117036 584856679 536304847 650627822 47237229 445239230 186621089 961740391 286026840 963425802 317885315 600706794 25074791 663729479 61505996 851435962 716209484 864170450 48528254 387315112 590711455 451287106 777719335 87128145 566931522 439265690 583796312 538914415 825055684 88329104 919468369 439843461 969539722 511700788 454630121 185420255 524098415 178293022 958448513 339846240 271181940 871229626 866580758 652770480 910941027 785877868 468434865 104025401 661918269 172460450 48949407 592032977 883604743 266220878 79894450 468741375 528830194 140011291 749292025 266730688 562172211 616425622 140293244 306543961 968859440 20635447 493548759 269191483 579962155 583798019 202774574 378977077 393675487 450373530 662080599 174474495 144164051 693140719 415151377 485289438 654551852 344403162 446551331 745578070 681516035 502869490 425767690 869959508 882031133 759604413 564472805 768018416 968662488 214132844 521338326 423616627 814528259 924598257 450182240 966205708 696519735 532661316 519072601 894842308 962564532 570896878 499447538 551243196 3893229 230846721 734514883 325469262 609282939 215209281 971343046 367555166 585255277 783739283 742144348 267050205 20482808 450515286 714554480 155329807 247719516 614507657 595037684 886200320 114119210 395583330 773713471 492578477 223345968 308633970 704303308 524468350 811044192 951806309 843557382 184614209 267956805 240564440 940636654 586040780 956773489 621437594 678620053 675838567 27811085 18663203 266439029 79851766 330994937 819868429 98247140 680352209 941072743 34747610 323776182 421037825 367139918 87490835 892706409 834696380 928523825 279384234 545731419 464129489 740830234 137538793 791993803 154769 366901940 268833211 505782454 86837739 898770271 823374772 151756417 39898225 921786202 67799377 915314545 753919897 688731366 873174441 611112382 98677966 166298128 981732647 639931259 245334404 880291968 941878615 353910320 958234600 268505840 633456705 622811880 701397423 257489307 934577307 895523499 421568320 548459077 437355965 514489350 977123613 346094564 403366497 926095343 580692268 689633255 150440127 469036777 711030806 777728402 160992935 947751162 201565945 153990127 574084179 975462197 35396464 751041198 325227498 333651717 274664017 736047489 254488388 482566904 233014890 453295107 202938398 674562648 546829085 257123490 353969796 714926771 483675122 418849747 881579052 687538097 490247881 178552503 904111762 737873897 649873298 74736773 243173153 938281157 309773721 752534046 88650833 156132345 305998915 612345562 682328761 57190139 255679452 683188715 992217449 141850148 144581047 410325270 942838756 992320610 485778586 925368701 503799178 431166137 934974236 656104624 683304628 111154737 733139336 635294205 904278568 538625488 524508459 469361986 955269748 271789384 538308378 222979272 15556812 853266315 711257169 376691516 553345000 135798810 272957719 724169122 140598067 668134451 136905003 193760927 298183495 299572755 804174081 274944362 506000664 945872106 956171572 456436279 391233018 686522087 11436857 307441955 695486025 603320517 366022129 243251546 753030543 165042893 547959954 969804733 619103416 450467196 386728464 40938188 324551757 695356279 986592767 586366081 418496627 530314999 287901822 693005597 956847132 597315350 635291985 333631197 486268989 228499875 373525541 61620315 297133615 288872160 419609141 77575414 624679195 256124432 633783960 874759220 794288419 859948291 593368606 257508456 282226807 942253634 656146124 360927994 139186345 888189936 494236810 803522480 835049900 487525391 413492673 449079770 494801504 262586898 561546732 405208705 347545971 396270086 980653223 107617096 438346623 59863545 921123142 18429718 895168027 160363495 336721918 358771900 689311331 536422878 450224067 600281812 432244175 754201539 230466174 481116373 965978844 395821761 105875641 612357178 988150614 599301170 561586956 104321498 803901750 163035621 371462163 417540270 77783753 143195692 618183935 97062639 439326048 439602078 944133438 639814866 312352616 609091715 518326573 260668803 333850834 303337751 329135996 239065180 299580072 236622059 25044996 406942731 473638038 977174729 696112587 420702821 252277925 331079512 672604475 464180380 155462716 722274692 558729975 339872338 878050581 278888935 83064817 714952299 774124000 618699700 621876306 609680109 342794823 455735915 686857097 598126344 317949304 967882652 642062963 876544743 733069187 530827222 313013598 417324964 158595568 606925487 359190969 404042695 892910670 388696746 700658193 163601779 517149956 711977423 705930159 74730170 41581510 364962379 180257828 199997730 432719246 745509570 919080513 752189972 633498857 455469506 484417870 111309382 312560158 556778921 583949459 440289373 511802798 269730484 145902465 99459991 685442263 199376775 945350380 872063027 922576078 303830814 490308459 545200076 888249777 773421857 71182569 741020207 224938895 973284379 668859781 24252068 939341073 751435868 678979604 501777927 476845153 261052006 333848106 928895630 556638734 671375787 428973156 393717823 155325236 679414942 124455412 650874881 581333201 456497549 425988159 557161514 251625908 443261648 174065936 182136599 197608746 596829274 220710729 382305081 418887555 768808407 309596196 47783248 401358249 194227426 343408860 135621818 163966000 970673811 448889690 31197095 607252425 519611073 919251715 641838730 19699865 832854002 538251348 88990239 410519079 554529347 908603708 321639267 360664424 386939459 699196728 710168946 35004960 668450306 136002207 14603420 652894339 532977547 626417437 382823090 351936878 479388749 742567908 256105697 606274907 866094464 992276139 294118366 620200547 211442762 72289380 865491464 5668458 926242442 58234457 74131728 694744372 725015707 39226006 408943288 257491163 858961460 82622178 839329573 111065557 168900348 630140371 928802594 288927165 735354477 589599491 248818597 154916124 454630278 220076784 313156222 997773725 186480527 943297314 689893890 274435750 270300897 394469368 583681644 336927806 841648572 452306356 681523038 170293693 217728710 266652867 630801194 278139656 617291073 794217717 149160653 647998341 190427403 441000562 121470514 80135026 256952347 511536925 357089843 30635219 732864921 575102716 584363037 145817878 124245103 947408480 907016631 490705883 799456812 398187887 248288088 314413017 239272976 227049430 334289211 446005796 531749294 151699256 802536010 989289956 905243461 966040309 348784451 65502390 40658173 440207691 887580948 423601234 777792460 522017921 466710832 958919318 332782249 297859578 725271750 170689528 972588232 648842241 767207418 476179839 712020371 161120666 343212790 140698059 621990554 666242859 423988613 278967042 308968017 553604466 819305919 887270279 345859468 485314742 865215588 965185843 865276586 163902825 204749795 511299461 104133920 238475720 888920240 281328461 291706003 581160446 302172853 970108043 222470335 304915043 827148061 184485011 386109853 465423117 170156379 333187840 851638873 352381513 459848307 605324777 201223883 695571564 465121594 484993430 987980471 355573668 835969125 665015495 482039742 174064944 44957321 241304183 385048214 752914571 217765126 870702573 564772696 739989372 126162650 448621430 493468996 451324025 519130516 692566478 775096331 343032651 478037956 511704281 988018692 407883237 703260220 263312262 496794401 635901053 304562041 965286094 228127314 923389121 29154590 73291188 261157693 723022778 187948540 415322234 347824406 790058676 134585284 918385903 241236321 236566557 412229640 354916185 824134178 151608865 167510159 213392996 901099923 874229210 686340964 217089083 906316244 750048607 607329075 388003535 802558918 444876875 109231518 175097636 787600962 327105685 545771501 858250773 609360280 358485422