438 2
693023610 162530658 182795760 689261946 527902309 988692013 339453519 752629314 541028115 154698988 546230043 503831770 687730336 387832966 311588347 654130350 676115300 116013288 739550487 557980945 825253275 790409339 410690359 982057710 389169782 442941200 18079542 88245979 938352693 293102843 982254795 637560390 77367861 171057749 907645992 531856458 645502993 843017973 519264198 385135066 905058295 506229312 176203123 251351786 154528687 689765489 584368195 811131877 907673198 471434490 242730241 673977847 357189951 257575694 511158753 540259714 667389387 535636872 964168576 422014471 365361123 915736477 493893777 459499273 881787998 315334631 303364970 364449952 868094260 530152742 903097364 454754086 748684399 114097367 77123775 939583177 360079522 345600396 64478351 804145876 415165701 952001169 801304028 325145923 68747303 643010658 95485070 241988039 63185373 701519399 334766759 79396916 160039148 518069373 727997687 127606498 37139978 886148897 642087606 849340894 240045863 11394338 281787663 289330677 943731236 221533072 219157876 246714031 154437773 473362066 167170534 816616577 95912393 684221712 107806778 275415654 989928682 447420912 687657543 440599558 63227629 626725766 730136020 674781981 511759915 958968131 474104870 622156766 654810887 342592422 819223210 594661845 278161063 899282763 657365110 605452912 942167802 465595937 128521861 2994048 697365686 678697815 388340590 54385216 477743629 238184208 755750528 458426681 911439993 307848900 1286581 667814293 398527249 983984473 944871149 609054539 832294428 689897092 392492418 627602140 171483019 71516254 738225851 66786814 396984303 831939483 856960013 201297232 328238093 510586808 770722705 980144147 391461870 720547745 98825391 867398950 790012027 803579338 104912883 133229467 174975941 198135822 531743152 578863191 204162911 370501353 135755154 985727917 228664965 414507188 187078589 59037584 95657693 875995995 14613836 250250595 383754486 373641634 8109328 941112938 473515235 996768872 749312645 10121095 301457717 795184023 596206923 354927174 262932967 783629310 656272356 673550187 17681402 551930705 219501785 543439513 531180748 96675903 91182198 764728174 963797738 78652501 968181210 125467086 691399127 517291082 818667316 715816639 413347616 106887070 813896263 954341618 981267757 357505266 285245247 463606204 527843534 685564225 943898856 571468535 573836060 780031262 170728258 826459525 765017503 47851551 989184448 302642098 504166117 303336689 942405229 251100819 240761257 342536555 897209511 914621529 155214937 288412426 898925540 921333648 50900754 779264214 193033248 245068009 813409880 573758559 643560113 572512370 461955112 814760413 353140683 420634628 253262536 770965365 232693472 252725274 290766032 500343892 34831435 851503993 228783915 535407212 642037229 933832284 852941205 183210742 98297197 571293307 489753254 415195290 164703725 450168637 623271881 189813904 284590922 50224691 459854048 657630336 664900423 885089400 298594772 149174939 930941076 288222124 117344229 873700755 585437195 390781680 439821567 455943591 87441798 785732535 259150281 854720353 88796879 757664042 476121681 433438709 847368639 912731961 789023166 2485350 465898246 633478806 113398689 2969518 522912412 661345674 27225341 833181056 646362286 502296850 797073525 311691072 900901821 692682630 478156304 193192495 117863588 815206611 421131425 26508227 842785402 534280046 908114386 241177422 677908082 433128162 302956498 29725134 757206660 123032241 32120562 505016273 297763729 860654788 337919819 770633731 776795184 222536072 222189641 183397067 68965201 158402335 63968198 237360198 284835494 338689817 634410253 523789914 616380203 656674827 150033992 72308303 427300971 938958765 389310166 327912120 691781751 274702942 986196961 975904439 173459391 958310817 847108660 568986776 950368131 941126122 973310244 791735589 276477283 267031882 213017192 584880700 387367411 61800179 146210419 941060538 579399691 142897556 65327933 876254170 916392090 356710791 543033473 368595315 87107921 834156603 642358711 67174585 190012174 900896994 633998822 684028702 806744715 666037417 891703470 241209396 839327037 950066975 130922754 768189529 517931893 876679472 806493163 659456832 321900273 270968528 91137353 859225706 375424079 325713877 452323574 135558633 551971317 74184047 519873295 26355032
849810555 872391315 440829835 299617715 930858916 215148175 176855748 554547107 482438639 936656734 424442370 130615401 68938699 455742673 863682140 952624139 716914397 70139983 648341014 266207627 614430720 793632577 634884487 978798794 724708886 139863999 182671000 915834300 587101677 451389549 35384370 505988960 812135921 398976321 179658317 258177499 777727390 506929854 379718572 979629883 599279121 156080673 293751473 653850606 198235041 712258211 327772285 252076687 980602874 954230404 66494948 55223317 742237251 310468309 281146897 341530916 504912716 590874309 565794355 61862918 768124021 776214620 890482759 108030113 163730104 291831458 67525584 251698752 463183767 136813487 163707848 334693378 584529947 251926602 183736953 218326832 977475206 94359351 152179774 940710721 401708388 761684721 287211838 241491059 721530182 401725862 781001327 989568037 220593262 509380088 994364237 319053460 400278716 995830176 547438200 375080951 615641764 520520018 238480606 748962511 427679991 714155548 465598538 186193398 367233141 997972725 744698738 565938878 911148521 908367691 317076185 424218878 295296188 112015869 630731280 583223216 708843086 103438404 290615869 921975878 239584463 605373472 14465570 679480771 793394183 742609898 415368582 556752962 957608953 268186561 591419741 141573558 125363097 612535700 355903686 778217860 800163633 590602134 697865019 867604441 981102403 567224515 37077330 670016535 907245832 55591884 809508834 202072962 93322201 385224236 390639231 269620011 894026155 356350038 580470964 754468700 123548563 67834055 940928613 477877294 471912857 41143996 96893978 367100352 998297000 280703939 957921183 512605200 823274425 298555763 975806917 2755162 691434028 412252690 115840611 165523557 831114827 805362487 753698279 659714024 746721276 913150128 938445670 700981902 488618690 505928663 616216324 640166997 352272136 846476903 946237320 262504736 443758458 822843139 923277891 714074300 148222242 856764205 654252607 355225737 345558156 923420867 925564841 809478370 151210552 185617357 21902495 279775076 507243405 681765091 641274603 126201185 365657039 93800889 288471002 830658244 463006633 371314240 198406770 843633882 707743371 846243224 181107793 28535100 526016611 112693172 826549921 175542047 554614192 287258981 777883218 442437129 610732737 977048173 693137098 342712729 196379390 936934732 661025800 338218834 510532786 496788709 665723978 344156905 533558017 437274830 939051997 950715607 44826063 645301360 52016871 778244875 673785288 468892668 688164328 411549691 978145362 261346260 426208067 312161557 171419977 604277119 80507419 158369256 877545216 298834208 899333667 716974807 331612072 437712024 777315502 814240294 598697256 627702680 399260169 36295943 631034840 738209661 337610832 688465099 780657581 711736492 249250066 566980819 819378321 976159481 369564183 284737328 306613220 483827177 799017304 836453767 558300293 19417210 531813366 973655578 232367999 556856274 305909336 456397241 845109688 678299282 127430061 447902077 365902829 817117815 844390955 657721970 951574549 216987150 416408053 73414947 552681563 355613614 931844158 285494699 92038859 961365247 951938249 166211813 904551135 475800511 577113746 433380296 219157915 901101876 945717877 567944624 482747687 176806630 458355067 813421740 477018775 640415829 98330380 869000827 569398222 606155359 168560945 517664182 681396934 372924259 956659874 949351934 535567606 493326341 167474048 856046775 529711835 737240754 755171047 829305 781450620 919534972 134587756 616580368 927800608 815661401 647560949 346806319 681300592 478048245 340093199 417127495 514408426 171295733 69705804 846513954 674366653 63721825 702771 509763055 401532555 280816272 323717181 803277490 713712398 725547725 646828238 973895680 456271916 925941452 740367762 890185771 27304757 291104925 585595653 68391317 331369328 702642588 301020036 56200656 216908783 284512467 888776236 848504997 101727737 177213819 681310639 303375489 210908849 528066021 877506167 54914544 299016141 885848477 255413929 71482847 647829055 522604516 412192205 569123302 944505492 770602296 245910493 543478562 185982477 836456748 787955601 975089276 183589969 530814473 348053572 776001749 635554147 559445304 46420014 801976436 75923367 98922073 246922156 873780769 399761328 577745579 361315866 361872425 31490010 774479886