936 12
323782846 788358718 688155521 388237616 350762770 494966862 985263186 155350231 82521190 224780007 896648388 579518162 72909201 171995027 172253854 264814220 275105182 410868123 326666442 103447016 216821066 339089225 95802696 367385034 661319146 200512196 505990903 47784161 335610446 345684662 42015153 774896391 39800904 49950896 528793150 69565982 125195172 331659964 677396799 112537554 769899830 358984546 753332735 58469276 816058747 474876303 760268340 628368747 252076924 718903065 450657025 24821578 215032167 117128163 360566442 133886162 443472056 545006431 941014364 844270101 837854436 749334645 898861304 535124915 577691957 937103303 870956002 507567449 516927876 275886447 700968830 156587697 25701715 923072459 158989703 45807244 280464855 244913974 45167478 983639148 125395033 351868311 119548177 420014465 341237171 708591917 918905268 964370414 829261143 184698061 341728247 784649171 648401298 528879706 710219190 440408811 85687613 276024556 179873287 573028304 923925328 441567254 116330596 203083475 350927341 480882369 760952775 388631788 809159644 759166654 96139412 717375067 42115060 715291710 695591941 817784768 633848386 904884538 610874787 106697948 407544918 956525157 114795070 112787249 817669279 986266606 647810179 683141680 762355782 170362752 456345341 107034242 300541090 249647939 807751406 667769625 894596450 512376858 732717537 482545004 335054507 597385312 540089408 722244020 529356784 613388594 73201943 521773141 622472112 581140890 333355558 183526573 844406641 689492413 324987800 139575334 829256311 397541871 991328910 746667001 783752385 557301119 72313352 221713449 963286864 716431640 369048186 221313307 388572297 513404298 592425425 365848856 192109342 195216605 412329857 814085777 871769854 378318208 130530203 305782346 96205735 355417959 810470512 520409711 974813052 874822756 889570194 497409872 760264964 486661018 275670328 77024079 190516263 381586610 426398008 721574703 253874296 482697781 12059980 755331058 187872892 72526800 865681286 806678500 406395969 537015680 898844399 397848180 395171316 319628922 60633554 681553273 180456168 839761592 853379573 419273369 566114655 222583033 848107855 805887629 719524153 996904396 183343491 408425067 381557970 976748158 839819295 186524782 985448568 579343574 976915796 248845561 335936388 815526845 295926465 139944066 291891588 417730703 379807876 207098128 81630317 295967835 963937817 756331119 819218779 113982748 207900172 161285134 680307175 489611881 373152965 568174489 602631021 348787897 440632300 98018083 32170197 561896576 828417293 820466455 92383011 399605466 825624859 926009131 965660328 804365446 996188124 530253573 841881516 3350133 131756122 398352426 163213016 326824192 725530104 166207783 585383086 981838165 252541113 796052343 410038397 972783443 734192130 161749625 407262896 361684523 133528174 488873763 429331351 340799109 142179055 642921388 136236176 622334264 694499398 930903090 682315613 481392492 883201329 315325172 765551919 695318505 472795248 636284115 897533067 602375255 95026961 625497121 124823872 840048250 678613822 547242371 595984210 620686875 81138395 702225455 832966918 946129095 178130340 155882176 104749149 439313608 359183876 972714362 623637534 170675270 207918632 195790218 773271894 583792819 217863504 447878525 391843079 389097269 852365465 619972590 512880261 880340665 431276833 185179693 334895688 209284486 392069130 978670163 217503123 904021976 346694469 74073463 916262037 395208042 796131150 838279577 438972482 624229068 105605748 129460695 578347839 575908201 449404616 429984949 347018079 819957983 895468087 861773109 122678890 334696368 21776441 751235518 865593272 272869690 650974494 413072576 181288364 102231041 403523867 569654381 619268894 301465882 489944782 581277771 977256850 782012035 768122389 659561906 360774121 743082825 558229609 362334622 441256236 675648570 151907833 687740333 249429112 606617145 466131009 842880608 628383750 109450563 796363090 601661542 578624644 95628650 855034889 680343915 702185586 507250118 261682969 760307784 259583192 611656574 76890681 138553153 595258902 933529914 525742769 433520534 529388679 346233908 19468188 507177142 752116789 866439607 33997186 162056470 662342524 207254214 389465428 260086903 513557453 973862451 386859130 903766976 293389000 438034483 627447910 424680529 722946144 242280136 180272928 116339137 867309061 702068146 597747076 273800179 809429519 761666477 955126309 866972240 628577321 273615934 295397926 195886545 605719556 956291315 160730065 501686257 790197987 456770506 432579882 716445350 906377445 236623673 7726127 651931837 701596908 610159615 649479020 273662708 684436124 142344360 326878352 19444419 200508957 443513127 813953261 746412552 873425185 883419462 594049108 448793123 924948671 162502949 406720932 668640894 172248048 827688241 260241569 30794909 570313915 889872665 58131699 977132570 385899648 572465488 250487525 562382790 39852368 656882294 216913332 685178544 55291801 8932011 108716770 918000511 685386328 766248440 963102441 80918505 818859302 317245561 531313501 353317317 516605394 769056643 237695336 878302708 855170088 140794540 84369354 507953497 105178841 755606480 644006018 256578298 66785736 59387376 136868435 155966237 653975754 753496255 218473164 591971411 440439545 566565664 361483428 944792662 838430389 876137606 885328211 668281617 730663389 530535897 138953981 885698882 128484489 133457574 982931984 150265560 425135254 128874066 382899661 170369344 443678522 420267846 266666388 670627336 25312246 130685737 412342081 825576687 922666802 671457622 467449481 563890386 345033422 357219973 500505508 671535245 663983526 982750297 340390399 392211460 661471826 574502508 20301598 408866976 846438766 327346118 675831569 248001215 134065248 79917396 624386464 51087600 627560977 426843047 354506496 251563760 479654486 416727525 886700755 981629489 612030203 245671567 568688476 403799202 449042082 420301690 826000016 913348117 438121141 328776407 25351588 184661677 874978118 769510700 972693154 533820571 85638693 299735361 57557576 37953342 890713415 584258998 627235431 470932126 468421950 807581625 529364860 432594710 988887699 686493775 847292720 749913356 792766126 861365555 317911573 660955811 251831861 511912458 664121147 182185892 244015392 855318660 161900350 713726152 468654518 349717312 86737458 611400820 183723591 996755046 683708411 953482036 596414638 456070159 39384813 153629998 825643812 647951105 706471643 103990937 111589206 353086030 837363932 541189458 484760267 273617473 626496349 809497595 638766267 459180515 118654866 911833399 596411368 245517282 670235035 569126763 854044108 512250943 46982062 282351959 941817296 404303847 498541051 700404240 170019378 196062373 28765872 911400848 637504487 347899776 285193645 466630014 768256793 156131521 696954879 303441005 664207615 566610663 854545127 900803232 123008672 280242012 1163889 865697577 92215414 981529040 721361945 359969916 415641511 936980635 39103187 853499921 417375700 732377817 918739327 613458133 696472588 257717125 715017089 945774489 380607524 547578074 593949590 635170621 452746284 328127601 788120463 716409804 169284038 534334956 211687285 872330244 285425900 934196152 37976139 304688484 203534117 719170707 150311276 333694723 655753806 429342988 254406009 111584584 671993183 976769437 497931956 712452619 805047333 319126216 15025361 578245603 260381036 696009084 914510708 746762687 42085956 686879158 368424081 798567701 969818396 575113607 301894123 143498454 336924587 542334096 465287368 634785165 284923855 248360274 529639963 666417453 472046702 387950671 640754501 630274866 312555297 529345298 917561302 496949803 496529400 122166283 156118836 888546577 250441272 349251090 536140399 724396352 618642691 535205822 375146902 192536221 7902481 102421011 930169690 280403096 583600170 989179251 851073500 903147570 870673566 401034821 841067633 681413421 918306983 971263241 842055366 763614667 851062822 787494325 173325027 400921284 905418107 363651835 445901602 325986919 271175715 823885713 467615906 191260525 309821726 922445797 938729035 244881924 460777634 109844435 841844939 419898383 787352314 804600422 468931031 861158097 911225202 468322039 964468701 603251707 74197460 41386358 809461665 859838883 933430500 300201044 357289752 343422752 383041754 150484460 256596830 849199842 119961002 730821271 945693682 475885454 890674375 142620402 92391490 453682639 499599766 149815964 198054763 594470786 146744731 76150853 339007602 636908446 391356164 580506440 611724650 952928683 451722811 792877552 696520939 230469566 853462399 318761916 868043591 504905148 78772999 619466812 775474957 329420533 516622297 454488999 777766817 399167181 250641998 384560271 420115748 942233164 46067472 134531621 271874220 149407630 103670994 177954102 177132483 39714106 475138277 777987872 4618445 907389634 193661531 741712093 376340422 856359228 651664747 83786987 988397078 350263542 911001777 850377490 314065305 412222973 116047582 836422605 810774814 831200839 647461467 221411811 771115144 562920711 254106003 901672447 732980819 614149005 230382182 465312237 852846350 657218049 317491838 238447576 732091584 89107201 573432580 550829609 614165012 651973440 213007254 908467542 669052096 23658274 376435506 588135192 642383112 433572402