1158
30152845 101886483 804953962 638726004 521785470 138123496 935753202 597172857 645786036 725799245 912268060 877069172 218700153 452011284 114031360 187445398 535459533 845070425 716966371 853608408 132075402 694905346 113797543 277316959 606815504 672265934 565908201 200918635 753821354 671453681 505289675 766799313 267362782 219324472 618168447 207013639 238760701 602064832 579698007 777757010 532024707 935295918 776815980 667077500 443479203 142227186 725661942 133925760 601212881 200514144 595770578 891924704 119421682 742247738 865783657 552071430 392146180 507638717 454170122 895898412 829988381 782740766 769457759 841588880 879674854 694083456 153698287 538251859 227527965 707372443 552617781 498398681 432759445 469877928 217722861 295191679 743708957 993836426 608830827 913863297 681009296 917684929 245842245 243675506 991690892 313129003 57549286 870446834 331145459 995328927 914283651 249649537 292315605 359062322 534643610 796319149 576318593 6044793 814650001 138727359 147229279 517268502 724601625 125887045 914731744 217086174 984449603 302392214 914181599 314999408 722526194 743151091 409093546 783046001 95091052 385167900 674614115 486460474 228175448 841259018 45862488 152311251 838396732 780713951 835344868 458258945 568180666 781423089 332945080 234149220 600374932 527825971 451491598 250444409 192148944 971602175 709957311 810217102 228948941 113485424 330974695 338016603 295330117 944662423 620719397 660485018 700393324 528817900 681764830 196461636 704973443 799608 39780423 493921957 805103158 583745129 717683561 487919980 111389905 734596650 517759134 454062951 551820568 825686797 287347207 233642436 175431468 211283861 896063289 107843805 598214080 500589087 554205924 489673507 640726686 232179238 964852527 495200924 839892279 254505685 626479474 564767909 218312730 323259588 569201645 906220187 744100143 908802920 935966018 147219566 919779051 505062064 390304443 897932381 721649734 878986600 36181420 877324680 275735038 359287606 381925584 579253905 374248963 544376929 92502878 177195346 480295982 116037323 365791021 910457950 809262945 85568902 737371959 456428454 136574219 581796099 396415274 386794722 607161994 379174222 201890519 995965856 105634659 685176449 672653833 732996274 732514851 637037191 880142557 422763144 873172501 859157473 947748835 530516805 493520016 62081984 818565787 126680668 512402107 669635437 357337759 428232153 144745659 959381528 20556082 424178379 41682222 584149142 195517476 84795053 119410495 256695997 781284528 246315987 989490834 844084810 379938378 607478069 640276171 985400075 658946189 924084985 547042133 670166746 218779997 160034420 289718625 565249882 994330847 291457299 237038998 635561755 548818348 806475629 686721171 912200879 296140168 738473492 751682087 57895500 469170575 626212347 144750800 386105981 838394734 201323395 87953507 954821488 795120707 71415272 205307014 158382154 387334022 193946643 756701047 601270138 102481649 579325001 197405395 46735859 251626309 755483625 998213922 198753598 862525129 857302610 165000116 405197182 210692140 817609402 482245978 606742920 802119453 920316268 743942136 135358534 567890863 676151844 132496071 380998383 33366654 780801899 169910303 552158541 74111310 810738705 80609925 18881524 829971744 609206735 829291937 217242675 32991932 569316477 352926248 190845694 874864834 731960443 99972326 83430402 623596181 858862393 355714144 283809623 86819504 311407801 296136972 729738808 414586783 846466124 409144418 542106925 474112255 776093013 656538921 551147311 828248607 278901420 469743858 211417053 383938210 294718490 678501232 902723434 550022566 928452744 399612914 510877631 437608709 520693285 274399556 442274102 609190366 49030244 246535742 170481930 664815445 929028397 100661080 924543531 200346950 415033299 19056292 744243452 64502620 93289216 300949277 419486210 219715122 271634123 377347214 782827374 802251790 600883415 734992604 686054332 614305213 609164094 112055302 10717391 233588188 321172815 502730124 639511923 753385702 815622824 53727889 628083816 804995003 239838012 424809089 577388299 496980987 799170091 700062013 943847772 902682127 907412500 189134432 348782821 828881059 128651672 611439799 74055275 749744122 962918729 26819234 716631382 391823240 57778341 811559594 49576234 355086069 841597641 63957246 204613908 199350706 613476982 416340320 779618518 537618228 194439075 901244350 984678492 429654368 416032586 354038442 359834681 310001492 759897599 126289431 939467905 743260642 598033678 630948855 231927349 715025164 604981990 594528171 60562412 368421763 652186678 213013537 346534194 251015391 771560655 817645046 993971586 838073636 139938035 577612321 633025893 237758240 605415675 386053808 643345643 622176680 616997100 597164928 445285422 990349740 129212999 59577175 232431249 926612162 337241323 580133735 93098485 562280172 511024018 752225262 158243855 769726953 773689256 694960024 504428952 289984422 841761984 267856919 802371329 597035155 34837515 523086140 293664033 388251882 357728860 422947011 150040784 311147125 879937331 455748159 785177890 952615865 141159835 182190956 607303652 823634244 404734364 239174804 428614658 244394169 359908070 479739234 545897664 947779428 363108596 208265586 473922803 170182188 395660575 137653947 741457378 31337791 927987329 133523278 76610331 303276067 948564663 508602600 299656131 699433095 978009806 127899768 922708611 750506446 51678163 669362773 714815837 11249320 360414634 777912559 945585030 968391219 87214495 542393159 13491379 982057303 379528448 631878252 589638392 589337736 667185225 470786908 286780950 864913388 897298865 375520308 960390198 303107436 549064373 309056783 919593778 532435613 97318606 781194598 660134373 811573782 94834521 236049177 281776235 823143145 901957672 211571418 299279165 179086349 59181828 115834601 423261030 684458830 205392494 840888777 577060462 134400529 881777726 691675496 591004357 8460422 975183141 678993499 108296301 23113979 581533827 733511730 574506697 961792690 411547781 249114133 67658953 301285834 859040067 855192543 77515213 572510503 991981633 126904674 147247907 282646871 167762728 104925523 294373999 464134034 895955064 459643674 616505014 133637718 461866358 638956405 787257758 998155937 471771665 185373939 446684445 142086766 437536370 750515233 555924168 432786075 303270716 138627803 859516204 586874682 470372524 334141585 449233214 868710118 734606958 533771662 875670659 565378901 345590696 907680000 750077004 452202176 112629587 791591440 839103268 686508238 773100454 352760504 665468491 903218716 726749636 279051101 937107411 950919326 483033592 463949180 406750097 859216907 108280355 349404246 360843687 297730752 967799178 374089338 214177150 844742441 996045798 407219371 737279924 832747229 645176778 69600247 339043727 564668603 530993233 581899179 804211536 191963104 610288649 113301324 997809061 444043429 218963625 310903006 423747216 376808026 599602248 294199818 789420744 55264586 255556608 244894522 552836903 566080284 510842543 421950337 428806304 830693619 54103917 740828148 949817733 521048321 559891404 864091054 698593141 226975385 644251010 589421960 756025231 897143677 332590815 983139404 44922079 415461433 648671114 806087948 690335007 369397154 723254452 590085445 620097780 724918828 427665696 419618207 111372348 399786813 535700123 283174969 559220499 677068431 435460904 46820500 123682442 602050330 840228764 243419352 802765287 125562032 334492007 360335169 922702124 491095767 665449353 203828646 5049993 32530424 486090895 123538632 369709152 896708910 332754579 853151755 233349021 409581153 549020242 786710473 663750040 893572259 275252825 935451290 955360221 449252384 350084812 265063621 809989871 221816973 233960863 35562384 420568245 466180725 330726041 170501987 881235375 332681350 298377472 469435086 535767441 995955785 113756072 684154210 283048052 302065772 293247546 81299517 975420812 224662179 434108243 827626146 271748676 289288200 221911442 462212393 984483539 172231455 188331496 529026198 13742633 135160440 372601689 776478068 571977331 558572342 7889248 749230362 671085436 689133876 912051853 528331716 391598430 657157457 205416842 531982760 927276079 405701846 343521701 672479898 995019568 606554227 748596675 359859761 535836064 393199163 715065656 853960138 282046215 6586101 964370630 188642535 14225073 67920179 352297773 343228024 603598611 821282568 299583794 539478390 883353741 742920804 424215035 509300282 551240523 41710375 627125445 337499819 35681904 707877512 242844014 461431875 161491712 863866277 298847855 801317683 430362693 133992640 678804349 256191346 792044440 409615124 902625461 351116295 861895164 627906059 671329520 761830311 90228038 885986765 924891384 464619940 288058563 984147412 544115720 478866301 372166103 944044733 517414208 559746086 291529005 19173522 491189059 182259266 481185017 917593101 992696757 897149944 955953749 496512594 534620457 217516092 717724860 457249714 979604539 517185837 713358493 763546152 380409873 321130664 975097244 288861445 688672073 301949494 409705114 694863331 871351947 787554165 744787823 457319311 914726612 356907838 321430426 683753638 557521155 28068503 192476479 753074445 171218315 368591012 927789795 169713505 662348591 238981689 504568779 383207388 747321248 462579333 720498640 634081523 677324081 129035653 243993012 40568464 55357632 328827014 331705607 38381695 926734575 420715822 838928708 572770052 649953850 358959447 225281315 98484819 498027183 339031691 987946047 383003534 249878056 973995945 890420083 24646954 663895213 396541121 364213006 672531137 216665692 671821363 534047547 990875030 583745788 369930740 64685694 827675308 624195280 60625038 701227388 457264505 691469795 691688060 952796266 152076185 883791235 188492577 906600259 462898912 413505819 727648995 420276103 924875966 889244175 417044881 40508593 839520188 826237393 441742533 505877106 834480412 213383099 610551316 969951339 46194347 965780962 195228683 809263090 612963915 924675712 11573546 932685094 626783125 371672428 295297661 348965735 270580569 986415368 766725774 895204139 213417615 900558596 31706856 310698560 236983443 477001692 140859065 923679113 841612625 20490062 495634206 980118604 174453758 421557559 528064035 175245839 803936763 115961324 726548483 326988974 118020901 236985232 264973284 201226608 854493492 26998318 139517260 14706148 697494184 37230062 718555318 367199800 958100392 568021276 804840222 922834812 434772703 548299710 279392112 224378278 941650379 674165957 178798111 941103517 174588983 875610626 670812135 284045453 440260100 813008469 379531552 401255040 772835319 806751953 166628101 616994042 719021321 958325695 886567373 215929409 585579806 2060849 586956247 276998680 838675563 307944446 837040836 430087869 287429716 720676114 946096953 711746593 52822361 480742577 948172025 263861544 159667823 423685358 166024259 857040556 706276928 584973237 333761406 894267876 802351158 20810701 49977827 125625456 561591514 892686002 290019650 395417687 52340630 723330540 100027862 114570868 601933718 570061398 906776630 201371259 327556078 738232164 927582448 579045062 505738896 436270672 302515186 96876625 762408718 250483725 696041157 750304210 790090318 935526456 277086552 982504132 2582397 390279725 408234692 825405380 96920367 114627488 976411486 518053729 168953964 274590237 329050715 857084341 282393465 508932415 146849434 633837005 818864137 857136760 11762354 353943105 608321563 288970305 666566233 71313959 732841302 847963442