1946 940691610 830407070
962551384 923746712 52283382 266773409 204626187 899260708 762970849 841482876 713964651 1031853459 432932339 737250079 733611129 850839488 718672492 687058442 435263567 901805515 1056716631 184161124 451005795 137916678 279989718 473466266 1036274138 735706662 488392659 406875956 89300898 457623199 751363382 39284749 535389703 852413072 840615032 929188373 965772856 7955223 227937440 187983582 119261598 955285678 894093528 27273638 680434129 21560874 1009433203 888672732 744703565 13334993 291003910 968662041 161338290 1071380605 554915968 272126790 58392858 781100928 208864157 89479907 741857614 28117146 223695460 878587 995326007 19332402 178127893 66701054 725473080 20778938 907854864 679203514 822502025 689532712 845594400 182457761 998576890 111499827 821953900 984843856 56476534 519321217 924207385 21664050 833390119 131320750 945916067 955192921 744446408 275536158 41749306 149915558 722522801 44024278 1049288445 691103995 25497002 512651594 753267099 880805708 258897548 2065589 911059452 94073889 793654035 506819850 771566332 216535042 207491209 711468869 829191783 680421422 434973674 246885960 398881546 284707782 866305512 117001623 754730887 253633168 934697657 57638981 555699432 420730424 924733633 75043394 712754170 225393452 730757594 922535632 981794432 200665627 16745621 797235713 1025577239 752811253 842301135 14768095 781608857 837848059 114380111 945197289 14875394 885028043 371098458 992135595 908381312 454308821 1050255935 980740911 759904820 464065522 436484918 274746742 978124575 112282479 129515254 121357662 55482090 978178619 502764730 457429865 794535214 656246796 41644545 257559056 97456754 758233849 933644073 218195636 885412169 658866236 91659482 1068327022 798912490 1017579527 694911032 1070441766 749879304 403599930 447152056 858676049 147282950 506528405 740025983 827009824 121884622 441893126 50447726 861035589 932074673 796038394 882298752 152579901 1038978353 257199125 722495974 751046154 1011254433 252978543 780253395 165385280 118578703 858468320 504206692 1040726111 138155332 729496232 94180218 665155452 979969937 147793907 853956969 225150460 3898817 135770114 22874106 4162261 51316210 1041868805 801284781 216902891 1013496518 846511392 483261745 979876108 854772872 46227455 77842702 210930863 107301491 716969133 373458002 403953449 914934072 471896741 105467047 497155435 667779500 797113340 824212331 1034746108 82223290 14125453 867698268 126337926 941387324 115829789 747148580 931548169 681219801 956049540 12647690 984924190 937057197 2328201 784226756 754522120 986543948 11503237 452032580 198689285 100336154 90899962 63140905 467225344 498590888 201064222 1040384264 133943774 922272280 174456958 827221361 148178273 783086685 517445087 791432715 53304027 383156522 62245446 5993953 957112622 169125278 949233553 426192727 185330353 681794062 223666913 120549381 931024673 802968894 1035189171 569853496 966673447 811176356 155021344 1001737480 1063512256 821430012 87493538 831551323 1008824158 431915269 75352886 894308812 683540045 512697829 88018514 260270188 539451288 983631091 508529535 1049017808 467506416 891734944 53460406 100599506 57265950 377915274 846829924 564874064 226656971 794769877 810964057 195018994 420324848 375556498 1024789644 1047162962 814088924 190812306 509378604 43481677 811994908 541810064 18678906 48585971 426472080 62927206 1064719995 111110709 97717034 404968361 450332488 1043041675 790856114 835749659 434150925 420869371 375291610 658343372 57001446 465797032 899445975 894645712 112544131 1044535276 6783645 128436294 783827386 72993342 279205422 406706903 98899306 736065423 684908210 488659030 826571871 203402367 275271654 758206828 107826587 432162075 536694516 663845732 908882087 87278318 883425660 293363710 381057514 284444814 849348876 61983502 10975453 838369571 109400659 13598373 385255786 61719510 916902264 432340390 897321748 203233792 833650491 89852122 1007696562 480443039 486189503 67459027 833910863 80201478 258386331 967845485 378437434 490359122 103797262 1042664636 562514520 442100722 722599053 860490132 1040230328 12026477 976691517 769522433 878446164 122908985 483709314 127368013 775306330 4687997 967443711 682277802 16484225 1033310620 672673481 20514498 133415790 479876975 377651154 426671098 204984948 888144748 150502176 272912110 182484782 847433128 152996157 952609513 85133994 372933026 245780578 214743597 126076750 132087157 994890759 146708429 491571891 102843551 121097254 530005693 251158898 656506692 916668016 673152268 12227346 910844317 41430902 780291946 51757190 780644515 507759271 889590748 270289086 407791973 817234812 157511586 263140627 978757711 700916763 925923515 879910245 845073584 823689987 193543030 10419986 421370393 809370860 974526207 426186194 692247369 1039681247 469196490 938626021 403997094 913417972 754690699 169312376 159404843 102061603 218092557 268018129 27091211 742002325 731827453 837391492 1023186353 1024870490 205383539 1054879154 716996150 799577153 901406861 506540685 670924364 828671039 220090714 143455897 885785204 65286750 718885386 865754477 144916703 93672355 219659096 116739651 846617721 866156011 70217989 28377426 52919901 46382798 965467700 967100700 1032481900 375817546 930641571 59096486 821166532 267539342 192197026 936792793 235493349 148897601 123979150 1071603048 114642019 721791197 371358226 563304832 18419330 428650388 185960723 1041765742 745672616 780335343 519822239 926105488 969763000 51100862 532899637 377386778 246588600 195988045 499475711 848479944 102583179 466378820 845857048 93522858 187880357 17103930 717024697 30476946 514937864 17126611 658079124 372668650 77296417 48200821 471495120 32206833 1022783704 91453785 1003244381 72683850 1054603626 737289243 806244913 259141895 670664212 197953486 437926880 493968009 9143441 1018352522 844660675 894850393 1067276066 1014558225 812255316 60886066 817782625 220717789 815033967 961182402 873383440 1029839774 960689077 126602686 855032640 564613784 153719159 919130736 742738124 964640120 989215464 851053748 950310366 33096514 64342278 723970668 790189434 819753111 508776341 248444241 129727553 265065845 908117960 406411156 507357497 692022954 1033022837 268262796 107563143 380009674 793983181 141114457 790776052 213600324 946465194 60781365 48742342 709099142 531325412 565400000 654407300 177156927 80044307 444246339 131874798 72577593 518090356 690977246 92211666 130795838 843234856 101568534 886574620 84919798 67964762 442180145 46045898 501761746 86734641 125815574 755361257 96539762 245742023 404761212 1029746145 286284310 1070235645 505439978 50764026 756384843 926566157 741591853 156464854 804352212 848852099 850313552 923564999 750413153 670402524 1803681 719973821 119525078 396522770 524893636 282348238 468733009 430668726 555963808 704284745 440700676 92475786 903980052 405301907 929716157 1068792590 916487403 1015086507 375028194 497182754 829369432 65099487 94489646 137722716 891949268 930271624 445549185 848215824 716399066 963162524 82403079 229222741 535930398 665419956 758804936 1065836780 1033987851 692475402 476626088 887231204 72177083 675625765 837179497 1044508790 870057812 693916215 380274050 29449983 666205276 819594356 462875683 813432228 763534683 118998118 693594893 676291512 1041051801 794427038 15693509 180786790 850574600 791794009 694103010 496445271 932339077 851211703 835488263 569333384 63814806 277630174 385775642 1051956459 1000281151 176957561 449119719 442721078 844470380 877550705 858131356 819931192 103300118 41245635 156864224 514219530 1047740873 790425840 662796676 184374274 46598082 139406829 281564966 478985150 911241627 998397340 839942619 276845878 508103046 9407077 804921496 470090623 433437236 48088182 25757538 460248571 93258482 463948485 190278457 998460881 445457797 127259382 108231257 563040456 733200401 52546862 972658917 149258895 165676930 218623887 737457818 477815927 839539037 187956865 184306767 847168752 822112907 192579918 855557616 792070168 512041222 5596643 752734745 1011138480 931284533 932736387 55279441 465315865 86941354 118189585 878972100 865966684 996218852 29847293 11766681 25232626 77685535 63555166 116479279 246775395 818806988 901620252 723788719 105659918 919912672 966427409 243082839 868514527 505872128 70324306 699896648 533151780 1059767950 145910054 955373109 43867659 959458419 128696702 939152333 758310381 996704742 260257481 730499417 910740920 173986795 39071358 815423085 1048730642 939813023 493152225 65914710 862848908 1046553358 841898577 668304412 855292984 533815654 88278538 3634413 876349332 774285963 909954640 942438216 69667970 906126261 1041039713 536787277 187424511 934913252 559634096 211195378 832671892 908699652 77505930 476743125 711032161 229659449 424947047 207080481 134446697 468794869 742788890 897004232 942303345 31991958 560417560 9666937 694998711 927093237 828931411 570381480 19304506 890131249 179522243 104681579 248216208 118400874 88540354 956256949 283924510 977232446 791925610 382896242 507254374 968988243 933907965 382632634 498511465 1049010255 819071236 55663567 497970532 915458984 967050734 187279825 887884340 129487854 852151256 147765410 934434213 1056729586 422601254 806458292 474921831 728054398 118737710 450413078 802051478 823429359 865338724 1054462980 894464155 672919863 688230467 262591898 870685772 66174606 939415713 32573650 433871760 718818139 762563717 269767246 820142229 884657336 782727320 216720942 851597429 246133207 432588564 1052601724 113470249 489685815 922012704 868007760 853198072 923945989 409366198 453296740 509866350 7047537 1013010628 471958601 495327638 54906406 828409131 95881378 53674730 66437574 924470253 52018878 443998357 848695228 55166814 138640132 678221734 715298158 270817070 785670266 415797974 423246523 732414856 770004721 91996382 64948370 487394870 829580901 839751292 113681786 968674321 133155382 438929864 260023846 843842420 441215899 1071206908 120938499 569593152 181030038 525970197 1069900819 929451753 557795368 880310179 939631316 433334113 985517167 695301028 669874540 470600987 226726959 536738161 668042980 928665133 45841217 883165252 681549715 804267131 95618026 1020700875 148766000 748494584 120760418 908484777 954836216 43369862 764170757 817393507 240502544 868114017 277106286 856316509 50560361 72365382 557275576 525256838 808976308 957758919 268024910 138277419 1003306177 257151565 59885902 209934016 96433493 684347888 98240986 1047209201 1011318542 96221230 30215130 284184918 59624726 761169367 256343722 792897703 1021906238 761238331 565135112 967948604 682305279 147049871 123717206 32310298 917554152 1043941490 48405442 766704815 928464264 886313188 853413292 949945884 197902720 445363972 873045316 1026084287 131715302 940923292 894962972 739627388 566973584 262089772 52807270 1071298649 454502107 880123948 972291494 885524796 382369218 156592623 536391997 1068627151 1025956824 975212812 84375101 1006272267 474312790 907595096 694949587 58022083 70005838 913600399 90638338 159294282 6521801 58178470 652047500 816448468 897209933 879805544 544168840 962506113 1063799247 4425129 1005112359 875743240 960983192 506214739 436224629 694558403 881066884 659126644 8880317 449626511 1539277 685013544 8136878 779353320 808604453 201553283 514498883 182921083 846201964 691376616 557535088 277366694 1063429071 1031566365 90378058 661225780 515744563 976743162 79864706 97976546 680906756 763734049 66964534 1059405004 853570219 817571584 70633798 245692899 145921733 208276754 221873471 853750256 570118128 514646001 520945014 858288531 878708108 877136444 98580774 240794962 562254176 58836078 255783400 1028183018 943878590 1042615182 834819957 63245610 1007977570 249714364 955588201 24023594 838108431 883954668 672234084 100940318 160047095 915194608 1055587454 830506251 74386098 756530486 465769779 57841634 258001965 460814635 806747836 896667332 749254969 16221357 562776336 449378250 95097210 816712460 751922426 82015561 411774935 749860970 980060301 529286851 788111709 722067723 918846943 30736970 761622606 813323597 109661031 682689645 218900413 973844540 841792304 868664032 865648216 792513337 892286168 683770011 1060482529 890243884 1037277058 708429569 872832393 508153268 12408555 966982830 447539385 1275897 807012340 932554732 835224563 99208734 268457526 32836746 972289799 850053272 1009509247 886049708 673918201 171169177 160399664 493539554 510022884 147037575 884872684 43687378 678601838 280253710 284971262 928043920 938887929 913203089 727091286 802529501 816974404 757770527 823951959 870473621 647327900 884215076 44238538 125657643 261488096 927356617 136424479 236775774 159082753 852933376 1009886861 370573482 495142425 439333172 189328228 496693253 984138651 568022960 144653216 928283055 876876804 811730404 5778358 1041331986 262469876 213983216 852673096 678099712 658606596 667514996 491313360 378697970 903661712 881595124 109922939 258413808 892603428 45728638 121620374 813534876 934169809 282085014 111322178 1060294 166405647 514505416 103108531 912574464 68274254 31809523 565663416 104941951 65500445 432538342 107041119 537091680 1027794669 486382789 847954008 160867686 663585324 210192193 888408228 960264858 969461858 814614860 90117010 456982296 683132554 960697562 21038450 703868489 855929759 877950639 968383896 420870814 125268525 896823951 1067410945 485708699 882669527 6257397 215368192 781286767 36711558 826311499 844258117 1043287649 94834562 786972451 54116990 522593469 797652767 795774907 824861821 887387583 792926200 106025990 724156568 435251632 227111238 96849190 1042271667 27592170 1024197123 257608994 87121391 215901845 535723249 257283170 23137458 655720348 410685917 95357490 759661572 1039947614 223722477 1005791719 111760199 1009406970 414721413 887016880 54641902 1014916906 215218530 1038718060 851390712 567493888 425753746 874776900 123120026 106780747 528869880 677550983 567233608 273176614 854509776 713580372 822290736 288644110 87758234 748111692 148621442 836894348 262593333 882849976 443536175 1057105865 427993781 1034503070 86181834 982182789 443508856 256921599 74937133 1067663148 802774932 937454507 881855532 660701892 555435824 928924929 98390475 942051198 937272796 899047065 811203756 775014680 23789346 509430122 711668299 729760747 401240322 752708028 913099440 986811347 105203347 99552690 224292544 380536698 969485042 941350307 969774939 259784854 272648630 426045609 655983828 148571248 114119739 787695453 97193146 21844667 514020512 415434772 860647303 274486334 55818926 220277748 61455006 23397994 159590682 935094967 904164031 519961186 434163205 116041330 910214664 64604990 987808108 868326228 875191165 877446000 411821730 520366762 528916675 873232583 919653160 898942304 833128467 500676775 270027398 1015020663 110185359 454982911 828147479 259471809 912314184 684426926 532764762 970996286 123298103 836010031 693805650 888934420 972150016 683492485 1070903369 8352533 475375745 125478802 842715064 883052629 64078030 96030935 809895772 498798484 871023640 973441232 27488521 26017882 519820796 555175544 836270403 725948013 819333948 1049448976 50945511 170686889 876086620 919027560 832436892 148981177 141779120 560681936 1070084054 814353684 373718026 3237103 1054464683 687713067 921359208 431313006 36527579 700189066 378177090 840875312 146156396 809635364 19486151 926828769 732464854 892490789 649687700 714034639 232262041 847019255 856108776 558322392 505428043 143038843 835031692 849032128 879236604 672666700 978020160 842974576 881331644 723280552 256264684 872417356 446723601 976405262 85918738 849237825 505717936 926305593 872726848 892105639 222019118 179453279 85658970 845334120 1023247189 67646294 876613580 663324916 1028479125 124243142 85398626 656767100 29950690 903766657 996910080 960704035 57526358 501358438 965180094 182381229 272387198 403904333 92997946 38886095 910476480 670138020 660966396 176520853 462192350 407539830 815212808 160438215 720413862 93861686 3418814 8616937 186000911 196245202 766234652 36924953 430825260 74535599 725323418 253063628 873990556 223258387 885209520 255678066 751415287 791710433 434819482 18155978 48956666 217411058 826049591 535571662 232062371 84582834 208226756 236406865 67308170 275007150 870874067 1004602763 1053832333 60381431 992072309 29632158 821693492 123456798 733476436 495233813 279725214 1043125203 1005597345 683082616 533984707 797234274 157964290 203441531 282612486 101152573 249587615 56034274 665944868 991494624 560154912 901301912 109140287 889927584 877764404 91839511 840355456 169743994 1014179363 889375400 15957977 104421207 558058976 117262251 777594147 834665620 113859367 384727802 703915836 936266481 60567662 100748991 824472703 984020690 189276323 199099757 661486188 1043889972 490278532 567758584 842450624 721032514 483068411 461706460 766773349 236823121 37029898 69817543 74724926 234880053 1017904189 879495988 681562011 906523571 705811557 443481363 508481735 383416034 440587942 882513140 10050039 405119948 843498464 1012458307 975727271 84761851 134233318 476806406 1000308400 103512113 407926848 98793033 683408440 1035869806 784098987 824650280 931811293 917293616 849791648 807275820 270553590 906339852 14386017 715541150 936529349 999827173 163097463 245390582 497210247 189645456 697608771 281825374 1002018808 39389698 917817504 814876036 112020571 739138327 197316081 65605154 830768671 726708394 964460535 440014835 841138920 186169490 966852319 1000467251 1033234352 875086456 247096717 970735937 687627982 781397328 887568040 923587680 267771747 179069004 452298951 89637862 831030579 152496180 27855522 921387104 177720761 190830640 34168039 975231406 229023311 370310130 419746596 717433223 743375529 133679270 221806224 373197722 504466981 559894632 668564820 116218907 832865023 930823040 102322039 89094181 370838114 889746099 54378422 793408660 79656021 561993640 921205459 938363409 863006075 672428814 756317336 887771709 463885204 418098141 720600896 146264572 231592468 376077826 978640737 508351220 831290951 465824807 188769184 384992178 708629239 114902711 779823924 411404759 105871653 212637212 874254036 92737602 24204207 138162109 491065099 9868570 428040016 883690164 705198261 191436641 847693664 82560254 478292834 252461143 91342734 279465830 16944898 896453072 844151848 874517004 855771812 434476871 825788899 198833996 474866803 965824374 924998101 1003708882 678098277 181886674 753411785 925816216 160356267 259129599 478499260 771379234 842110836 59359966 131056246 808816812 783180024 99816298 239774847 660437900 914673728 840092104 844810232 802414191 473185194 462398776 13862841 62740971 735308071 500103668 839123076 157604925 149835496 499990934 150265770 264400098 863395193 1012804202 128961206 108019718 11239857 136339398 724789765 838630007 1020220071 906021512 100076578 67859217 1029653733 61195622 72027578 431261488 837583079 936003613 1020895185 770947616 143578270 912836088 946286243 53123570 680667764 56736942 793641739 832460353 807536228 108254718 663061436 534280454 474894578 794781556 826832243 863185680 34351758 248668656 249314994 860826904 802536278 873727076 173918261 34565349 1000890188 34670098 792120362 870367304 380796978 788195430 14586122 218168809 277894934 143457336 127156734 1042994684 385516066 665684460 404299613 875404860 920177112 954389036 875592123 432209875 207215174
