642 512 432
14627228 892141502 822486547 351520994 558148738 251212833 409112148 605867895 590594845 822961439 604344850 516848677 487351483 806446138 495643878 780252871 73298910 724116291 197155549 365916873 541121726 408481508 739649782 829447597 689079236 775233304 730482087 469803913 311421456 700967341 809635161 374946183 117164021 976053449 747284199 676538981 748520823 65231714 501664803 222552307 431104212 514376132 161852497 940046999 845694200 202401295 8926890 712369100 32846855 274406583 735311579 353943710 364527575 527893250 119797635 102824752 830340211 466494350 604074680 824448054 771761817 18090696 595851395 529463675 138604093 30258037 392196447 310746717 995506948 904021293 970716862 538119244 966461642 384144603 51636100 311986510 290749980 279371583 832936074 603036798 560505023 121585004 83388188 332522632 74163239 882976586 947318652 461744175 324983809 186743317 17145693 559269064 486678697 763997916 104991336 285248700 28971444 811221251 581913274 851555338 769780840 444530369 96418148 364108482 237772351 715208099 932741354 737728395 718058856 782268679 57329605 553127966 73701702 834856098 704029921 665634248 74937583 325181691 721035295 661694444 103382446 415896045 888809172 989097599 457715073 971497769 15077960 462152842 146042267 403267249 896848953 61670060 504363235 665809246 842102101 432439190 121767540 75849564 659955651 234933388 406722587 774387369 999639963 95783402 471749340 559866265 295470441 770145693 989852526 688789333 147358894 939021734 152874170 846190167 504851551 211976859 930309216 795618031 661993828 757266470 842361137 528412097 365703962 605797252 522890678 338302533 16755154 421536262 515353768 332501830 303655760 428459411 609090422 223168868 434706764 256363813 507861698 334696850 121477620 422117191 201554148 610569112 283311208 224322718 665407589 907353234 986942781 270312029 735961733 777153903 180176123 35819215 116409271 499740018 343302303 354072529 697905184 430563509 466993178 128299860 774459419 280841889 507686607 707745248 428767927 977066616 395349529 866697996 626701367 875287499 615177667 277622791 958211217 144848644 424361614 140704274 976078832 83281886 907690670 573848324 944432947 164343271 431191117 72816069 912184939 242295045 584599047 663513299 681621856 454829038 903893357 209808576 538226701 519400110 294075778 765639857 528413472 686947109 857055041 989910241 321333883 581398919 903932437 74502940 746628534 12819162 723791454 220188996 105778842 122660731 60844531 579958736 80267687 622631833 142922907 338356296 442265743 470628281 296361619 772444106 90888377 427517232 395963147 554740104 399560639 31833772 610438313 925111112 688678896 657313452 774871556 300945890 191314639 85814787 398100522 253220294 960946578 976864345 471014682 168322419 164022691 776251050 301407819 552259585 315219235 700066245 207543076 839304600 686840162 353851085 67459457 965344759 52501864 225346492 430068277 624665838 181562992 498334171 205487490 649455332 300872807 978320460 156454306 364668242 643431025 346782848 890786114 494249797 746691429 510475457 393380354 386089952 307687500 736643242 479760630 511764696 644991205 561160105 322649384 484000502 992155172 955010948 324585491 828076697 227881135 406634193 669861929 371104305 19652960 683855228 760349007 888587973 150072262 611094341 164349788 517446766 870842531 246924863 601854621 892717786 65364079 858030931 307788372 942569418 882013140 360482491 933465396 699027347 676734000 679470727 368182247 374665121 823844886 180567835 171548552 893592816 104086477 270942127 562345513 937173137 763643343 456059598 410358607 723933227 349483851 430875863 874492017 665279607 239273636 829395583 668164988 31499715 801825265 698686285 630093650 803386992 816519035 208699933 984210502 249909109 684663361 595565982 806823073 677692121 760380535 188137684 627468065 245470780 422532098 806017430 359632757 564098383 448219390 940957457 199963330 169969239 592366648 661534275 158834721 239809710 670194101 983271041 741368606 795501890 919882025 956375537 67392058 408367381 374634113 723549201 661318507 99419579 489441370 778926126 917192855 414991839 672414855 243465198 379588124 724937662 476031118 113201607 252180299 817410986 691115052 817125253 900992744 778447496 160821197 784030408 292598188 861767250 521430292 874639747 253970627 544794263 738997593 909917823 248547919 124160758 839442982 929124821 128780771 82613670 382746554 806520184 413902600 173994993 140473222 686469545 746086843 178564789 116898482 518290305 329680621 934266594 538393241 421636458 606759170 261575166 649536328 745872294 962543699 72814756 56823811 330998471 707098540 755048192 566220737 616166965 718978766 858044245 614635435 337975980 112292078 41514103 830685601 205125819 355039540 15601233 419164853 913859397 929953085 85901921 893708717 957159428 194267034 129476151 172652421 673997825 689527887 514718714 118296043 209734685 854638421 937231074 51457474 543209868 41117464 399158207 201585567 561231957 713394425 248720241 53970511 516057555 827347917 206800237 775290191 738978615 122574940 67578431 574969682 770307075 916405731 317272578 185041087 772075664 846978706 222729962 917706801 441783433 626319887 988920762 245373685 697524590 271846386 189847118 135671695 63933714 554003527 12808211 554977845 623853086 135518735 661563530 128059730 841107084 186627006 660569033 297258501 327407148 186132414 297831161 370615455 114972962 536357099 815635161 266328361 761685094 880356118 198925369 257710556 419381826 190478210 846777472 41353638 553690328 587113322 618077735 530451628 745805978 816704633 286707516 247938242 65891536 914738000 830155232 427675125 806654485 871806467 117545161 156067074 343026394 411501724 784212929 538431964 94568930 233671063 39829029 257707562 898376900 540875365 751925094 141943238 54944877 967440361 1711500 821150015 710854043 790361342 173706158 547211864 54419299 986516206 211991163 663807623 80502187 825535484 149509812 686814582 799093681 72133084 32003503 269830534 133483138 184764470 375709142 978390087 827993476 310001958 366531366 841674497 901929197 904355263 333897137 481783087 132661321 321246339 599561756 719264511 6833912 302718444 31328801 17672147 406023341 776668903 208163598 676059842 394265072 290356564 738218565 181012247 368553629 16011911 615200698 69519057 535669859 407145930 933629560 362574626 650775366
5714649 728435484 320894705 27669022 750990948 603556952 328343896 185086230 605686928 939745650 890495014 990059565 487361911 203595970 962967133 670918584 181276067 976544311 927136949 378179294 654297751 557832659 984056344 525995547 113617734 371945002 592853540 566795197 932802714 192242408 467903404 409225322 320482286 55990600 119837495 150218648 439768468 511658653 593619328 316154900 500206929 59277517 180961780 452614780 329067740 395686608 524584759 201126341 438896226 805068086 92489631 570847669 216661765 529233566 777871287 542260073 114569560 992385600 985253566 748184529 279251429 950258788 919799077 844078639 728442791 811026153 459634965 510985372 217664656 233730495 26543335 312519811 312050692 790736237 433370025 379370788 801336156 370770828 42922400 874009106 332352101 966476105 384470720 585500598 80518110 166635495 727789878 686862282 760642558 749383483 702805471 97342942 474602731 36020782 111830222 445961686 979214659 688194879 832602570 52573289 395054231 745465598 575902413 362010532 251294187 695477906 203225222 127315814 253986360 648716340 608904920 909326306 277935339 991483826 480738137 256253983 540983907 153729261 118591444 131592827 522833014 230013531 622726855 996501284 208800492 339585926 512204262 858616478 888368643 828641674 358029974 411532352 84557034 475553179 420622963 440356022 307862086 726601085 809798602 719363712 970695343 591646730 991291423 93342834 644807476 859370416 144752809 80840754 718763987 599251696 329809105 328955582 863586818 568129248 812168375 943938787 880306985 257889706 615040941 988664262 182745381 310832395 216918713 776427359 766928583 981104341 838265111 873876217 142720595 262194541 990583989 572947892 582818818 378033229 408832694 560620803 419076224 239514243 221965296 112571695 827308398 922272561 419934574 686191569 474927073 529577995 33680622 578297436 582535905 545454556 586134371 119888017 387330539 545598209 752588660 626289928 938910064 910513644 909597692 446300078 58285396 188912034 509059208 244565569 186119535 632998462 663673308 673452758 648838671 897115500 90988654 772462164 538498677 906187502 179165929 733102327 650642771 446785819 973789356 55103181 755535188 877044059 413677641 662638652 53524372 581069996 219964934 210254458 804761124 963308064 277131871 112706580 186088072 839703901 893495938 293051752 269207608 67658011 121998033 788590378 837391138 61261226 331679076 641157859 358878246 46791017 852811396 652355949 13428633 53307216 28366641 600143736 602067395 901454695 885143453 496807433 767140193 632402764 961499567 613228790 164850211 564066482 35590530 519420779 206518575 36721628 383990243 974415463 370495388 884365862 237917398 776320320 253592312 153347709 393835537 465993755 314406851 35029473 398007167 385551989 598131698 832375274 520661950 541314461 390098285 938850112 248109218 798672695 862054544 837445666 516815792 741999034 25227950 841850592 959253155 489264883 796194953 880812641 292839403 779401344 662849756 935194270 924597545 707358806 711037649 191296805 885960117 838440764 593038475 258717079 973025048 639870285 43183518 677607466 492698514 282605690 482912658 536502823 920790165 542034182 797600867 921146477 638342472 546668552 632947972 703645676 188455173 696335340 972904407 297881131 830449115 9327858 228214070 578802116 607209228 7051182 501495790 413424354 344880016 430741894 249057727 217505225 453693585 389138232 359297501 760694094 233334765 530880849 532530034 655140699 838315191 95482550 477217305 816541549 5956022 474686751 865100901 89176854 365935589 565219223 173577816 718422651 954722545 543226110 114084332 32959702 949896126 797591175 696233870 52051701 924029155 777912890 800468637 18573241 218292009 644258163 465576432 822708889 738542095 528679777 738510413 138210332 489859657 934147976 901225715 58293858 967229501 224364095 343969297 679473564 119366277 502567219 618812748 955003536 429557359 693582306 63385661 570686230 479076480 256190497 287942897 267404445 57628908 370660503 572973671 251371174 478964256 75397952 997992725 872472392 690201913 107152874 367969636 595724715 977485450 91126459 800028719 319329933 937525274 602941097 956222792 666305216 837342243 994873856 875341300 495830954 902924693 752937184 103643498 179173315 343550096 933197245 711715159 350871322 588542190 346385885 943649372 548700625 624915127 886972381 382090895 626099356 662086314 703731245 969196022 572534087 24654011 669777295 386923791 794721069 305050255 679624604 482692427 590906817 380600834 214851903 966256014 362650377 404051361 215392056 744165041 90672669 934787376 945459354 428667392 220217773 809380902 357044557 568320957 866385017 900624940 335279757 733971355 181261270 596705186 634712937 224290627 161307184 930512410 844413765 292292818 73070466 836973787 825032280 329067353 479178207 585639263 381041199 722863452 329000429 444093397 184009256 225054036 285651301 46557600 173319672 945855533 386623381 378858453 595787302 811132360 259483614 859005889 33130637 874247034 87338549 778078050 833028830 590924940 736635814 221680617 933915419