831
805015307 4545091 725551611 668805106 939186150 952825937 198186214 926833366 565213720 458317460 928161178 42736079 904583468 425676944 354218039 667816021 830498698 482808942 272893290 56116560 437705628 136847536 669550885 1502398 8682610 952775435 653578478 687299221 922144875 213660286 68122238 862024991 523845213 915469834 586955364 937381535 262299383 154429672 490692485 553351841 318194564 562610844 38894095 418685828 95010522 537240735 807218154 683677195 448827604 318173551 738610510 286083894 947978281 779701069 216470097 684698758 162316548 18825852 766777783 238545527 980669382 622183636 676455260 929378556 907207244 41437340 738216121 696965673 597036235 786927573 532670460 323100055 992767917 413389255 602411540 389390011 286590854 772240307 32937136 333662814 971450893 332579379 81596125 460523447 798389658 199459954 257160948 49244876 439326240 474383818 604785931 197325470 345203368 196545462 952796803 477374092 117491464 413993976 30243803 519048350 881170934 786045426 991984577 661250401 812292097 716179583 891874264 133851946 969292181 118989418 912429700 720297453 539322516 1016513 358584125 148404293 923834944 947727624 622987378 375011032 985315662 469087578 433518494 218236231 383440953 498193694 162448486 571584398 384252128 328550388 518458843 271052573 429457256 853108142 47260395 501387596 23522165 44998609 784556801 935225800 550729169 433087938 261131901 251571115 691907592 237979010 986499816 955175603 158457633 701607680 916466495 80420063 244427313 291699740 285086364 850080181 214058089 342629954 116488344 383916368 50310584 111344463 794286896 634400644 125497390 810121040 983534089 329849638 320546211 289439197 909012864 919633433 565182822 522489343 442165689 645102087 447916381 48989273 601108253 682911775 9088939 368560649 607433792 386097504 636525573 682858534 833645585 858845294 76032512 714065254 156718513 627894960 391831891 657728239 166671755 55890071 983437609 351043193 95981778 806477921 244713232 860776354 577679687 732852371 721657006 720142155 172170426 466425707 206338567 253086260 194777602 613566397 348883844 193262539 589163173 852603046 436779928 600272060 77742909 569970133 815348943 474802211 385486185 688013968 773631672 130056130 145877725 771323694 851665608 843697765 568273092 251402921 824381027 78608106 591115287 732423235 471822659 972106449 607188634 843426690 670891871 465005076 468814106 927110427 634754924 35643839 623338619 281094723 865175868 19859960 150959416 951782154 960982831 418265923 554495884 989824414 370230124 203088560 579038779 271297672 909795453 599418986 820068352 99678734 15372231 988713320 698417640 555978178 502396546 783687465 351115160 931398168 800464236 449545049 728257267 861759264 306234610 796489900 25088475 792012818 585305455 11697273 896843890 595637854 336911665 69373258 682174848 287030290 693904239 641395398 16411127 777871301 307656911 124830871 302387490 232209320 668160766 971461619 498313495 980582271 827805779 228892398 985546034 237403588 257251185 878858909 17871030 374245663 667097611 986669784 598288359 207416145 76459130 416294261 884757566 269074815 649361516 776023465 420895753 255853148 660785575 999548598 735122687 246547888 783425442 125275830 448990009 928831327 925640799 741248600 513970341 512916084 326224120 424589745 554631439 634677290 16775988 262228186 421597682 936587253 133299580 938988098 908428141 159499970 438608572 171392564 985316558 347924829 178819474 489961796 281763787 850546140 419162671 68193386 455514230 417473597 954309450 160002943 239948599 576878524 88193870 55997715 175840392 495022691 562361002 71240421 785270183 263524848 559722044 381622034 383411789 361527208 439161545 550874252 59400133 714925490 828693571 740090950 887717080 814135243 443272241 465612076 325403666 808367074 257705253 315610077 718068263 124740593 405204480 222793256 361241944 922655515 406093666 56591077 201564615 813613935 847038857 445729099 946714456 992621498 988053705 774441209 928539117 786516789 152389562 407125532 303840892 833839066 411187527 478559856 541979136 273944924 315536054 483699739 790354998 947698224 515544927 251766836 769788907 650246619 50949667 21602102 654666133 293547696 421661300 861771458 93306683 791012017 108751447 699464380 852483501 608429154 645963791 47095160 218942749 89807984 116572242 841120022 313013643 315896663 969958560 672798804 570688881 885562632 159059603 15962479 438536626 103859278 71260814 288627951 251190311 1566715 32061123 895597206 125277484 713767469 764900390 645505614 697693816 770425969 537104218 634629136 161028274 448262510 558709544 570153739 131218732 721022766 962388242 975243045 42900007 643659169 375577468 360490678 96606645 922444467 216210359 673933536 704662353 264434120 875251956 402616415 792140932 967559382 563135816 318891589 586020236 679338498 25145905 776149955 280191867 460826454 375638618 213943263 734323185 120038445 946629871 909668282 764196877 974222725 204396882 871383370 65220132 146218931 139756135 711168140 337221974 728388041 50489217 881519438 928603076 319976643 290127182 831199074 686643364 487713671 787356213 78758688 279913701 849907344 690453301 617750309 526251704 482054568 742630912 1225246 917575993 710938598 485968904 330044955 506542398 645798211 895104244 815559039 214130780 471483650 728327185 633573074 345821222 525367386 435263274 50997284 257262662 786918985 669522529 163003815 673878343 19063571 207174323 55701771 25787235 412438185 469213427 414824089 828683264 436679714 661003746 236028529 647282959 589948434 664275845 275711258 453173206 927323096 383597287 39702130 982729077 451543536 746869074 492682724 380269625 636997340 864796959 746677380 251834791 696847885 529412916 593591212 495288568 151718672 851752253 363858489 452610219 451085206 775632318 108197416 893967460 721188155 548591889 840896984 453291138 25403233 170865067 831926002 171267928 290559824 210445965 656500190 597980596 480742624 844731914 294224197 910016019 547026593 395503007 684077597 284097414 59389531 841162809 591914578 589171252 691896692 694734953 613740646 157880006 716721904 348340859 330668430 576304538 949567176 67700524 311386431 969282139 137024075 208959049 632609072 454747484 729464296 85890301 365699523 665429706 716808916 608533344 474913942 245109330 230948716 320917062 269436082 276638888 192716909 12975548 700762253 36964496 164557815 766555628 8324047 606119761 662182638 624517697 478716602 664824918 629736376 789383766 374360914 952886034 119748213 605073843 789404526 71632844 881351309 846819631 837589550 148956411 797682468 254223915 806591094 754240053 431877714 593061921 330214711 308508081 369582538 771665550 289712828 793795428 436324938 112297652 133174659 364602337 565657847 698905465 94129414 341087608 22750439 437692657 668610439 528756389 229654197 945384707 96480150 670978222 858933402 862115117 228772484 939464424 423906036 97177816 184310293 350272075 284820830 153326724 905585038 642734957 455165096 83264657 561038897 355625392 756381209 763755297 261834717 150527003 119618448 257888216 684397636 978320062 715494475 921060550 834942848 142925169 78698639 730735502 863487633 20564041 593355766 136549699 682691497 456142770 475334940 746583088 984895250 706595590 833044801 366518311 918724591 287511178 402468301 514043010 73225358 750075522 421506526 563779611 132644186 567937122 860035049 912634005 329921400 705954539 537388256 46814040 299138117 283009761 376600684 978894170 673153379 98617724 491277788 869900303 16491920 287377661 202303243 759814450 679955052 834816563 344951237 311348026 42383959 706839114 314559536 710773554 815085063 265017362 165593812 361204171 609517461 888798422 578596293 934305441 172198906 571844656 995638075 276388742 639634313 109694697 334862362 739230253 487750521 35254236 464796148 593242079 413297684 315739057 325750308 342255771 699615561 250909148 280416058 792384684 145109298 867621280 338203590 287429757 975390871 973091609 609056623 476626521 525900088 870337691 106691550 128427567 793627641 651889876 901049778 309199180 223028877 607689064 302392520 863024418 281306026 322325857 688283050 283728264 869641285 697627635 791984607 2133050 690274340 871232666 294194455 126851380 973138497 971730879