479
616994042 498027183 5049993 35681904 440260100 11762354 376808026 289984422 13742633 885986765 358959447 601270138 589731394 846270167 211417053 147219566 584973237 71313959 395660575 233349021 620097780 610288649 132075402 216792161 144745659 602050330 862525129 811559594 955360221 694960024 201890519 263861544 838396732 147247907 216665692 906220187 411547781 984483539 428806304 249323241 871351947 462579333 586874682 401255040 14225073 640276171 910457950 624195280 295330117 460163414 459665198 138123496 639511923 787554165 572510503 681764830 449233214 620783239 589337736 288861445 423685358 192148944 409705114 452011284 238981689 616997100 814650001 277086552 40568464 598214080 813008469 724918828 606815504 759934455 30152845 133992640 572770052 912051853 583745788 978850302 424178379 125625456 709957311 104925523 756025231 359062322 177195346 553943860 471771665 295297661 53727889 314999408 779618518 348965735 623596181 781194598 64685694 780355372 893572259 914181599 84795053 684154210 677324081 532024707 608321563 749230362 897143677 299279165 226975385 982057303 267856919 11249320 590085445 857084341 886567373 33366654 594965556 806475629 455748159 463949180 232431249 114627488 656538921 671453681 14706148 390279725 958100392 713848110 23113979 945585030 243993012 385167900 870446834 729738808 557521155 894267876 964370630 169713505 417044881 355086069 444043429 755338399 140859065 228948941 293664033 863866277 626212347 293247546 456428454 132366897 330726041 889244175 825405380 667185225 718555318 594528171 80609925 447727450 857136760 937458457 744787823 486460474 232179238 941650379 763546152 423747216 756701047 326988974 283048052 199350706 6044793 749744122 201323395 83430402 62081984 686054332 67658953 192476479 508602600 329050715 113485424 349404246 139517260 965780962 614305213 332590815 219715122 897149944 59181828 399786813 753074445 234149220 348307971 469743858 271748676 218176929 927582448 86819504 841597641 550022566 291457299 67920179 883791235 279392112 96876625 711746593 527825971 959381528 583745129 396541121 327556078 716631382 188642535 521785470 493921957 706276928 49977827 242844014 523086140 81299517 686508238 551240523 491095767 191963104 282046215 137653947 504428952 94834521 864091054 167762728 603598611 434108243 544584487 142086766 375520308 922708611 284103821 821282568 709641618 691675496 838394734 294373999 648671114 666566233 32991932 912200879 218963625 345590696 998213922 18881524 961792690 332681350 552617781 343521701 637037191 535459533 283174969 87953507 917684929 116206884 855192543 307944446 700062013 409093546 714815837 721649734 838675563 777757010 116037323 929028397 627125445 419618207 753385702 289984885 841761984 743708957 236983443 331145459 597172857 713358493 932685094 952615865 840228764 420276103 351116295 750515233 50116611 995052499 799608 236985232 635561755 902625461 854493492 352760504 369709152 568180666 828254535 495634206 755483625 948564663 900302343 785177890 559220499 694905346 111389905 631878252 188492577 93098485 478866301 975097244 962918729 360843687 64502620 742247738 129212999 766799313 437536370 360414634 119410495 601933718 408234692 917593101 927987329 374248963 670812135 671085436 55264586 334141585 111372348 77515213 895955064 994330847 218312730 608830827 474112255 193946643 523932556 772835319 561591514 469435086 409615124 622176680 141159835 165000116 725661942 392146180 753821354 799170091 434772703 586956247 482245978 310903006 274399556 174453758 158382154 413505819 202735650 997809061 339043727 716966371 580133735 645786036 160034420 170481930 256695997 792044440 964852527 416032586 996045798 987946047 451491598 853608408 264973284 589421960 208265586 995328927 914731744 640726686 22083583 664815445 529026198 329700418 449252384 174588983 769726953 504568779 982504132 790090318 54103917 45862488 147229279 809263090 877324680 387334022 926612162 238760701 726749636 19056292 302065772 535767441 386105981 950919326 135160440 993836426 579698007 469877928 604981990 169910303 534620457 517414208 383003534 204613908 574506697 414586783 391598430 310698560 175431468 539478390 24646954 97318606 505877106 224662179 203828646 663750040 311147125 311407801 838073636 935526456 618168447 369930740 408406818 388251882 69600247 136574219 505062064 809262945 941103517 405197182 602064832 967799178 732841302 685176449 353943105 214177150 960390198 338016603 233588188 815622824 292315605 707877512 901244350 935295918 481185017 669306070 461431875 591004357 133637718 200918635 437608709 908802920 902682127 118020901 549020242 35562384 914726612 879937331 992696757 933943659 609164094 633837005 663895213 357337759 111620720 55357632 52822361 508932415 352926248 39780423 776478068
796319149 409581153 657157457 138627803 168953964 383207388 239174804 544115720 747321248 510877631 298377472 245842245 947779428 609190366 599602248 937107411 296140168 363108596 2060849 381925584 555924168 273976721 11573546 517185837 615761411 771560655 983139404 137803283 301949494 258528133 847963442 853960138 343228024 41710375 794481856 548299710 832747229 364213006 743151091 669362773 829385204 548818348 127899768 430087869 989490834 138727359 873009424 930568996 107843805 369397154 829988381 817645046 991981633 638956405 782827374 389147011 517759134 395417687 328827014 606554227 195228683 968391219 707372443 178798111 188331496 421557559 502730124 875610626 833108548 865783657 6586101 76468662 44922079 742920804 737279924 738232164 616505014 390304443 436270672 422947011 717683561 551820568 406750097 113797543 10717391 59577175 781284528 430362693 732996274 246535742 750304210 536906683 381799038 581899179 313129003 473922803 985400075 20556082 76610331 789420744 442274102 355714144 182259266 919779051 26819234 489673507 129035653 166628101 698593141 219324472 153698287 477001692 801317683 432786075 627906059 287429716 256191346 805103158 830693619 217722861 380409873 628083816 634081523 725799245 823634244 217516092 372166103 924543531 210692140 518053729 432759445 175245839 161841187 644251010 359908070 452202176 776815980 857302610 244894522 211283861 105634659 520693285 356907838 781423089 505289675 290019650 390281570 133925760 722526194 171218315 569316477 545620518 777912559 769457759 31706856 600374932 156590905 979604539 564668603 74055275 237038998 542106925 990875030 678804349 445669712 806751953 299656131 859157473 684458830 301285834 975817828 804995003 589638392 201371259 517268502 859216907 952796266 690335007 19173522 289718625 609206735 92502878 251626309 993971586 907680000 144750800 288970305 530993233 249878056 37230062 620719397 350084812 470372524 462212393 404734364 205392494 976411486 672653833 282646871 804953962 321130664 279051101 744100143 923679113 734596650 26998318 510842543 197405395 662348591 189134432 126289431 844742441 383938210 744243452 881235375 585579806 493520016 837040836 57778341 228175448 846466124 672265934 652186678 236049177 827675308 923894610 883353741 975420812 393199163 500589087 924675712 671329520 205416842 660485018 669635437 737371959 459865579 694863331 374089338 579045062 181283963 480742577 405701846 559891404 221911442 975183141 532435613 946096953 346534194 185373939 298847855 569201645 927276079 365791021 270580569 299583794 221816973 213013537 179086349 607303652 441742533 296032326 123682442 90228038 565908201 828881059 420715822 302392214 142227186 368421763 686721171 626479474 643345643 828248607 873172501 198753598 496980987 897932381 602245683 445285422 427665696 839520188 294718490 20810701 100661080 579325001 487919980 565378901 46820500 803936763 773100454 683753638 688672073 783046001 32530424 218779997 810217102 454062951 845070425 638726004 386053808 881777726 751682087 859516204 155881878 826237393 809989871 548674104 681009296 984678492 464619940 457264505 112629587 126904674 249114133 658946189 943847772 595419328 459643674 891924704 461375972 810738705 678993499 233642436 927789795 906776630 935451290 912268060 825686797 907412500 284045453 368591012 101886483 677068431 200514144 577060462 531982760 990349740 743942136 360335169 913863297 535836064 715065656 98484819 8460422 354038442 551147311 787257758 217086174 914283651 2582397 233960863 984449603 158243855 359834681 454170122 108296301 607161994 924084985 582293264 224378278 217242675 231927349 480295982 731960443 840888777 607478069 867699741 28068503 377347214 877069172 740828148 633025893 42761105 853151755 839103268 245494757 135358534 499610686 858862393 85568902 51678163 161491712 542393159 424215035 868710118 446684445 115834601 380998383 194439075 333761406 267362782 535700123 170501987 795120707 924875966 34837515 620313939 310001492 281776235 783440938 613476982 31337791 782740766 528064035 606742920 780801899 791591440 672531137 700393324 379938378 422763144 829291937 507638717 466180725 834480412 959950451 900558596 748596675 674614115 701227388 649389108 671821363 407219371 128337338 196461636 806087948 732514851 598033678 906600259 40508593 562280172 697494184 225281315 428614658 415461433 738473492 581796099 880142557 74111310 60625038 286780950 278901420 761830311 715025164 146849434 215929409 71415272 804211536 409144418 660134373 924891384 802251790 835344868 386794722 239838012 897298865 479739234 152076185 470786908 469170575 995965856 558572342 424490071 126680668 114495379 941891700 511024018 277316959 119421682 114570868 113756072 827626146 359287606 139938035 57895500 509300282 462898912 297730752