125
546902276 523141610 96430549 642554037 594959382 137134320 480136484 50738690 633723936 287067873 118578403 803935280 213746064 169480893 915664924 206216964 889494364 63874134 583615880 103093234 776769077 751943284 174220736 177129443 618973565 403030782 233489247 67103321 547503226 214268398 414177616 127258304 742935577 645990145 189160523 177154946 118462308 588582945 367469382 559242118 564006036 297504365 78388983 449722079 668399908 940399300 185866161 899900909 488303495 437871470 389154720 297186493 585441523 536822243 468356382 501796376 585594070 388305659 561601846 959035970 324758747 363097891 391285704 334262014 266519644 782596816 513912518 560875657 855662553 308782091 868156955 742309398 262498499 457566809 843920010 637742959 726215400 333277797 177306794 971481324 339806264 389693784 767682245 122626388 635088803 741925041 908552639 353785027 489771423 799298246 749531721 703912835 27012687 478333647 245740014 954036296 968404717 326753 967491949 777778883 345350415 888656645 415763587 943565267 764042063 883080770 715311988 771154065 322184351 531875038 339177962 867594036 235350200 25018249 952672282 842300937 714738608 983567153 393034445 301842785 904349666 190574462 630523976 612168692 529035645
601
350171674 956704962 372114276 600004716 552173485 708478660 913505797 696535058 606612615 145764143 334468203 93807415 848576009 392819973 36821872 547833366 545336395 761051422 950359058 507257904 27954853 892815093 800158576 474893609 949903488 489044493 963159793 833534784 395723594 280983038 190807684 495268713 303982467 595765536 395042561 325517577 986487028 55806930 641436846 203459917 873374208 647941224 956883422 492088872 947740179 535588271 105378741 434540775 204220215 403949597 259432198 404965490 431044805 220304794 534850397 505088801 18483512 589481445 322222104 277420600 339169565 297264560 38601985 193724711 162386957 611904789 97510276 218906975 7830314 319343416 318157030 449977208 519346892 159448226 476439388 157499918 375101249 121105866 31116339 716937092 83380292 1806076 623222570 894145025 201957403 334693503 935927088 156901890 832364705 894966557 39571387 895288150 449706740 560105564 748022715 151133637 64732978 668491695 141878334 493436420 339405680 864973298 517117711 539857754 434586791 820357589 733349400 441394427 85206995 628931779 93095560 386451182 75238434 818864535 317160607 848593167 527047897 891871342 441104409 22481457 112480964 559807284 753297243 486305624 503913383 27910752 405305651 51316583 872751274 96660099 645660537 182251902 183956083 621446630 789363370 676605918 41650197 943258047 499300293 613467670 346163818 5048923 503127081 572217401 460809704 269156253 380229057 488123356 999845994 278758912 904788678 348714758 771025315 377795647 544490380 982152751 16781701 155567989 736153363 53364076 234423289 871239077 69917187 753862454 53954261 716772420 856026360 870910595 677393318 266749101 635033139 468578074 952723349 736060826 876814927 56886568 78787277 875089095 188122369 966817521 520071590 68058694 440043043 758105617 620713918 31643279 251788124 641539805 853058226 922014638 882579566 845544936 430245498 145583514 401395228 424977759 59678630 5387190 533755930 105641369 524726033 331537218 419538660 247102601 584134217 7546133 778960271 32784362 984814395 648398187 683529353 504935004 941145984 718118026 280054761 743212060 582883681 382777970 609003327 850912509 296974763 357768847 747797064 615605476 132513426 418308432 9961856 778195950 18880365 241464577 312419607 204120234 33743086 674817097 751155399 636336028 627635811 384921150 837423482 590044029 780784971 622792208 269388529 197532884 222586366 605006497 908376372 310233096 13347467 583357580 738630054 139079289 393856780 554520335 386708138 42732156 16229653 810619796 802670433 454036724 937753050 831850386 413081225 304195584 680102597 293403043 209444488 833994804 668766654 605963972 605861207 480703831 201328840 341054251 501420665 931156680 275654229 617750161 526132284 113623244 967255787 777113426 169671822 37399224 761034907 510820570 692500612 830082081 600580043 805295294 832664638 229778355 623017007 490144012 658314215 440271714 303753584 846614763 818659050 730015428 764620444 858397467 281380666 836147219 328169935 88842582 32030215 638598498 150203517 532116945 526779420 845661417 360958047 761521378 183603160 281152129 616086264 238373051 221251271 537280043 143314371 144425300 329620426 126180603 906407527 139088717 95854577 591359238 774963605 253399511 786157734 755317469 432245863 84527839 530474478 491221272 906509940 552495047 231440586 462029053 633107978 819510508 177958474 241804207 269311199 912090601 660523215 761607145 859667704 324949111 236383926 181977097 501081502 543722263 763411534 344367158 287110244 610291853 530364262 963302319 410779535 981893872 950412933 379708516 909577552 720992849 375405025 666412427 432314883 63665489 28950955 95385962 260286481 793955850 797398915 323311025 206961375 541141148 729521994 990759968 722774069 745074828 279304321 868969086 742840129 142912691 15782654 27461701 995549692 375245381 231003675 80831334 639748660 570095861 231213278 966539265 855862716 91618879 890955895 114396097 187996498 569041126 656543443 232845123 964556185 383911353 332430465 881874064 737606629 45308147 150666256 929914425 173562377 559834992 480983050 980502577 241504518 233295622 290921367 754611727 236977102 447502452 872728757 202734179 256908159 543126146 328115578 946902103 262409203 889875661 55921253 459918996 290534754 965264328 569614800 796319445 389949989 443978323 139426822 26933397 991447798 577124193 530395416 752047378 423098 77640772 603946596 797326879 576007588 197184486 280226745 238058155 731712719 328617719 777432836 201748075 95606309 495828557 191100315 129543266 234256313 831120953 57600550 80857986 916597956 336926452 464185642 581287788 650932795 585885751 878439252 378077449 250649577 849562014 745654016 569176558 839932403 948295936 943709167 427834099 27153712 582505015 579140246 110274185 82545024 205619467 567765957 533457982 36864252 777150335 188349481 945054491 547566659 518015674 480344042 623468444 183692275 227617421 266436213 50701644 922991412 72866209 622947412 820985710 646607934 510299448 291029153 588172570 265693626 121866265 661367241 358921142 674609276 465319284 113580983 335085778 384214700 142827443 495496737 849735240 260047225 86561195 890590085 560668041 207496454 426614079 509233699 305542673 497867809 917787388 950376834 91325625 550173221 177457075 598760301 347304734 14504552 544811967 529100868 824748609 813166839 602787774 820061053 115431209 455408749 373139314 423731739 127708760 687844643 572690678 721371387 433363277 745317772 969266957 311391676 766896163 934330414 794336915 47963212 353037655 882665277 191006485 965852428 571211175 977079254 327303804 523405215 208286229 605006037 996495844 55098964 576684554 483230035 631985035 912835629 503763864 548434623 245008356 797367180 312919512 209999512 909864907 73640825 25449842 163121604 813297108 791927186 710844731 563261840 178269372 385168 880057593 301332037 989272321 972140401 517486657 28876643 290596237 24131400 858298753 817973117