import sys import numpy as np read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines MOD = 1_000_000_007 def to(H, A): """ empty col """ if A == 'begin': yield 'begin' elif A == 'end': yield 'end' elif len(set(x for x in A if x >= 0)) == 1: yield 'end' if A == 'end': return _A = A for s in range(1, 1 << H): if _A == 'begin' or _A == 'end': A = [-1] * H else: A = list(_A) for i in range(H): if A[i] >= 0: A[i] += H for i in range(H): if s & 1 << i: A.append(i) else: A.append(-1) """ 横にマージ """ for i in range(H): j = i + H if A[i] >= 0 and A[j] >= 0 and A[i] != A[j]: before = max(A[i], A[j]) after = min(A[i], A[j]) for k in range(H + H): if A[k] == before: A[k] = after """ 縦にマージ """ for i in range(H, H + H - 1): j = i + 1 if A[i] >= 0 and A[j] >= 0 and A[i] != A[j]: before = max(A[i], A[j]) after = min(A[i], A[j]) for k in range(H + H): if A[k] == before: A[k] = after if any(x >= H for x in A[:H]): # 孤立した連結成分が残ってしまった場合 continue yield tuple(A[H:]) def generate_graph(H): V = ['begin', 'end'] ID = {'begin': 0, 'end': 1} G = [] for i, v in enumerate(V): for w in to(H, v): if w not in ID: ID[w] = len(V) V.append(w) j = ID[w] G.append((i, j)) return len(V), G def flip(A): H = len(A) A = list(A[::-1]) for i in range(H): if A[i] != -1: A[i] = H - 1 - A[i] for i in range(H): if A[i] > i: before = A[i] after = i for j in range(H): if A[j] == before: A[j] = after return tuple(A) def generate_graph_compress(H): # mirror reflection を同一視して、状態を圧縮する V = ['begin', 'end'] ID = {'begin': 0, 'end': 1} G = [] for i, v in enumerate(V): for w in to(H, v): if w == 'begin' or w == 'end': pass else: w = min(w, flip(w)) if w not in ID: ID[w] = len(V) V.append(w) j = ID[w] G.append((i, j)) return len(V), G """ from numba import njit @njit def mpow(a, n): p = 1 while n: if n & 1: p = p * a % MOD a = a * a % MOD n >>= 1 return p @njit def conv(A, B): C = np.zeros(len(A) + len(B) - 1, np.int64) for i in range(len(A)): C[i:i + len(B)] += A[i] * B % MOD return C % MOD @njit def find_generating_function(A): N = len(A) B = np.ones(1, np.int64) C = np.ones(1, np.int64) l, m, p = 0, 1, 1 for i in range(N): d = A[i] for j in range(1, l + 1): d += C[j] * A[i - j] d %= MOD if d == 0: m += 1 continue T = C.copy() q = mpow(p, MOD - 2) * d % MOD if len(C) < len(B) + m: C = np.concatenate((C, np.zeros(len(B) + m - len(C), np.int64))) for j in range(len(B)): C[j + m] -= q * B[j] C[j + m] %= MOD if l + l <= i: B = T l, m, p = i + 1 - l, 1, d else: m += 1 Q = C P = conv(A[:len(Q)], Q)[:len(Q) - 1] return P, Q def calc(N, FRM, TO): MAX = N + N + 10 ans = np.zeros(MAX, np.int64) dp = np.zeros(N, np.int64) dp[0] = 1 for i in range(MAX): newdp = np.zeros_like(dp) for j in range(len(FRM)): a, b = FRM[j], TO[j] newdp[b] += dp[a] dp = newdp % MOD ans[i] = dp[1] return ans def solve_small(H): N, G = generate_graph_compress(H) FRM, TO = map(list, zip(*G)) FRM = np.array(FRM) TO = np.array(TO) return calc(N, FRM, TO) def precalc(H): ans = solve_small(H) P, Q = find_generating_function(ans) return P, Q FILE = open('memo.txt', 'w') for H in range(1, 10): print(H) P, Q = precalc(H) print(H, file=FILE) print(*P, file=FILE) print(*Q, file=FILE)""" txt = """1 0 1 0 1 1000000004 3 1000000006 2 0 3 1 0 1 1000000003 4 0 1000000006 3 0 6 999999993 14 1000000001 999999999 2 0 1 999999998 26 999999972 22 3 999999991 9 1000000006 4 0 10 999999945 190 999999791 999999791 450 999999881 999999815 999999983 999999897 38 2 0 1 999999990 90 999999777 272 75 999999384 632 999999942 999999752 198 999999845 96 999999996 1000000006 5 0 15 999999667 3841 999975377 89727 999843888 999933616 853474 998688719 999764725 1921386 169082 909226 990472660 4399320 16536564 989535207 923739 995900973 996974943 13301314 997485893 995412107 1954996 62879 999763340 89685 999984969 335 106 1000000004 0 1 999999966 626 999994795 26632 999916042 135637 57937 999199739 1620135 999093191 998485993 2551590 997377220 7154119 991457770 993019186 21987911 983996162 6152683 999036138 990231089 13699534 997404693 994521618 3355642 999776210 999597590 189183 999956725 4214 198 999999956 1 6 0 21 999998819 33693 999436429 5860073 962266040 133514102 929136360 431241967 654250836 839086547 445006449 590028056 825532221 685389183 704462583 427249983 541666783 926820421 764709524 582516343 909412365 900017668 785675119 180011121 496192818 209757910 674600534 76330199 452857958 668200755 169118335 388777677 904740474 887916382 671938205 879345481 832206907 566669394 702582218 457203893 148622722 829977850 269842066 287478868 575104063 840890499 102988330 691692129 537130174 803473826 274435539 754464000 914140557 505651188 329169310 35974660 877155902 299783640 139456757 527551741 76782422 936102085 7612545 2363009 164652 495 999999575 1000000004 0 1 999999918 3110 999939541 742664 993958208 31995434 906653130 979867988 450143629 57940041 51719115 329658325 705040706 38479371 724108123 810715054 484591080 77586872 13495283 20514139 279183132 513975810 178497912 771592522 295194475 776332021 223981658 58083192 17050708 16230911 494464705 476519393 189155785 937991413 54201070 63313885 20151946 118575609 776692687 610711296 884756831 128167752 845202278 735369307 206268113 525852836 826291169 922972595 693304349 776356265 548131137 141958987 152522485 798387263 987311741 558683120 404633960 238042460 920984885 675315088 341916115 676073373 221240708 211895609 29348012 576165 999444951 999942165 999998535 107 1 7 0 28 999995343 390302 979261277 765350670 389595025 297013369 530956970 440079916 457973561 899537123 825800282 703121040 654230148 502085672 892816515 640622006 583228763 804764150 703759762 938543462 185882577 402604156 171488342 7462404 141973244 310361697 495237514 866198903 712829335 496235025 522429112 354484819 804734437 192361128 910590072 172180831 424019738 97206678 64016054 414857175 382112898 166193241 622316133 94457460 393387894 266775036 907085865 882256066 34569154 869338941 35588897 568298331 466901464 150047457 870209299 851010037 256319672 77561341 856394015 812308257 830391254 358822957 479553206 577938473 920986090 578861286 89108042 180785680 548053826 926404015 751651737 655635405 649170381 366650300 470321403 772262409 949270786 179741227 789412451 612706225 918409853 186491917 687548020 572614072 334437580 393522144 542232669 33148162 440785714 656234828 695927320 534932291 919813629 656249689 108682588 845019557 31016981 739003736 73533070 746696925 327018783 178996830 58430801 731966165 782774329 789594531 66720678 995946423 296830922 101355418 355936134 253159216 687163430 557588716 788640596 743319856 742577239 646682538 107391328 608990040 5023871 258031351 246406033 562878343 247651901 689494357 474923474 950620096 857913174 475379552 883453689 633959790 384522779 8988799 369679392 560783897 861847106 812496660 659132944 16146166 994884039 925025591 670144907 293137433 44723512 964136526 184163424 156783034 97712113 348673282 267569258 948080352 358711970 636896269 539259823 560117745 766536909 369883765 965992377 680852959 84142292 493962194 964718724 50594957 629001208 480589591 838932136 568266480 40972662 772421316 893912167 326105433 540978462 993134663 999976667 1154 1000000003 0 1 999999781 22133 998708004 51265818 517360108 546845912 149828812 946233573 211651202 232405750 811285267 401128294 116600453 290384294 677300925 13623411 155729746 111188901 452410975 117842397 332838981 970845792 94569547 820027654 200913625 890068520 67908380 76368293 461783299 774230873 809781530 66759279 19585253 349823801 504256321 826122746 84252359 578059214 341123611 323641562 621647519 633413775 635711110 932952837 35095443 981566491 537648957 564758649 706798990 100000385 128921008 717726991 383849221 750895077 470510190 554514183 475290790 79252471 926030996 307209159 522079494 32775585 101415276 271705401 266458448 606062420 260120971 123407489 837735148 245028769 821505999 329034147 44511599 943629170 138511469 145790140 346792223 395988572 925480272 909141629 573883305 305237182 934272686 724968146 362587964 615079501 821387966 307899471 611914183 219979031 157062462 192214867 530161994 276049689 109370078 332843953 437308315 752536534 225262744 767746693 118820492 659915009 148956346 342326029 932826231 121257500 190435414 682932862 93801129 679311932 391327856 174721612 371261815 658110054 823002334 293616027 350408100 31341195 162686635 380434359 514468457 464117410 565005604 56215077 112578061 257377860 902941141 918227775 565229996 757086971 827775747 329062828 480907436 157361700 70022425 878622562 520826406 187978351 283088291 593161595 117585205 327508906 663456512 92016231 699721310 209521382 807714963 131675232 261081137 577438817 42318841 923821258 380930212 199917502 581730944 726241975 812221768 292515948 848519168 545507143 238738168 216060021 879877364 711496839 917027319 282174451 185267082 643028099 857050431 163144958 546075680 193151642 893859690 268322266 377828077 871297985 1077829 18317 999999639 1 8 0 36 999985327 3019112 597822563 186642870 370836457 670855183 122074887 834105310 160387753 624576679 503452864 181006113 23412787 587229898 89408622 57554267 671498086 384876386 683044289 745751734 400213235 202305814 732681805 729017292 851925366 725161022 49280101 196410500 288460709 562677227 617920014 165464079 913307512 353537630 142984468 350516448 525868392 930444685 636260122 363682682 174259463 797092860 934542827 907339773 443249574 261304515 139870434 702803811 756190456 790705234 44633988 182763636 318162316 530828477 543142737 564178085 781690467 880903860 156123065 462608527 331873943 895495296 593119596 8607887 602127688 901873005 663134217 358491959 585649591 262166323 454482774 333981707 962053752 496046996 643159739 29744351 405676926 109944118 828246237 355124372 845223518 225659698 308395011 180131589 241514521 962990744 195879716 666006140 617317456 633268143 989402509 69979257 586926761 150523639 857367260 723580184 401184227 873809768 198741621 114603094 546762471 961556424 98132256 451012436 814509913 328606913 238995752 571942562 27331717 146434911 384029139 181830050 540772710 973337193 44277340 349573637 703485948 174809332 236503422 832993472 321894472 788413021 229986514 954585720 281091454 428830909 78048473 512851571 639302590 146461291 816457140 354515017 153748653 262225533 47259993 132133552 621204934 585730606 399402828 239852680 245091000 836361166 876442997 738812393 867701700 799824340 250796343 678381006 584015081 73798975 54230031 505727905 985894064 778525897 881297691 611045144 626048351 906453788 896564341 590965593 684276913 346884013 804291808 722293273 741859051 597857591 268973892 369599157 467170669 517801398 666343629 385122665 518496167 862071595 176137330 465708789 674124053 647657685 105124490 279759849 876352078 852590618 152651842 905223524 17560606 178698282 957646212 106714187 154149933 362973314 800767349 251223752 369929024 64528446 24658765 425651539 833986977 239719351 857996503 623658574 990374822 392297408 457069880 730631483 480611396 612264597 225576642 54977849 667477418 851505643 216995723 515141242 387081483 332588962 855836121 746725559 808314323 354895712 676482253 583403977 621524609 420580003 427893585 211613467 588725722 174617018 229897644 236407451 382005598 902545173 414335157 367581778 989304253 414283685 355092066 939716976 216787303 690016408 927181463 501468935 28392513 806313981 414869401 727165057 73965114 238087273 633885624 586103017 871285538 867338734 885979453 574496812 553371296 51502126 471130479 518793425 131667170 830935447 969302137 959975133 272256930 352114620 27169699 178038326 192300426 577509535 516872930 488661868 864023570 357352798 411013417 310391367 272822673 394000569 312756867 553782931 805544865 448083394 811053951 85414277 580961437 649503866 496296854 949260200 382127126 980410064 274062103 433880664 749376817 269558635 863270269 392703006 507444549 341235042 179957819 175616345 887355771 754547778 6046773 35491390 651186185 951482399 673728551 858605803 370093520 238193481 39974574 454597472 406962812 882844627 965143879 184283439 179907122 393727606 354613939 23224130 414708319 776245792 84576130 196618530 618891432 363049153 672028682 871626104 804230586 963060235 640023702 915815418 590799280 546175292 436656799 381276245 290578128 318605244 579868087 268039778 533991413 64250946 294455984 606889661 685116497 867076232 67822206 985249818 342670934 78200978 851952695 25142160 833604476 897336623 311877935 415072607 277482359 189647611 240971465 414038744 644193362 30897680 97463063 731469545 994021441 905523609 128429207 612631685 68756021 738175680 542282020 695075060 10642957 228902358 471505375 964045744 274465755 390312142 717991618 752361876 463421871 351479678 718344578 701076920 894897784 836091984 485653840 866330329 429921925 977729334 841381548 251060088 396245001 582645135 812625177 363911800 615558109 456672835 969656038 223766883 634549138 458780506 479236862 430793826 280675210 532639366 188569065 943104545 211544802 595858789 204102674 934731032 855265433 646181647 305993505 689138617 530633605 208039749 723691211 115896542 37733797 48094676 492774605 235189807 352675893 854199481 155991107 549691504 505839639 481490492 151073549 949969439 114428523 63416758 999570253 999995747 1000000003 0 1 999999487 121621 982609880 728058965 987778989 174829068 53727628 7205002 429985264 238803947 725474573 741291920 842076511 80566125 630047723 243273237 704919909 467750756 898645900 284015712 120666140 525076163 502048647 41285713 236154320 944501774 488500488 710436225 929390983 946198532 360474668 349764997 546341165 947196857 642988951 368966218 168715782 469670802 231397888 68229010 683271338 664890364 139880593 745193967 857773494 996357368 296985699 387800445 999535757 347864702 663192692 941229752 652195017 974804757 617212988 303782980 637798607 506484052 240297013 25400671 836103437 265982407 689584959 996104694 900416203 918296796 522286080 187612087 362933090 864532307 302981624 112204968 54400905 784706585 26473224 668712640 375257376 41403686 733299902 290472213 417704505 968163964 206305019 642117922 452197323 528501014 758704660 723789950 861488883 186442869 911469844 189585922 385531334 883639965 340445857 803030761 906058405 283729103 556838458 207205455 236582603 332247614 512751191 978031986 933348343 439583198 259555183 667111524 134423267 627265370 1218547 652309453 774086416 819442729 303725740 362324759 808079315 666491770 170076746 67455926 981783870 962127145 308555979 63650406 671285897 392101680 496994999 356899672 113429770 530326097 799630760 988646538 838587591 155025630 192022364 334997493 224438207 150157191 926202557 508901327 384387352 201600983 922499010 934485700 211414346 320838066 944419484 970282204 759269994 379210257 366839751 849660169 369564163 397878810 842191624 914513850 81262954 512817858 699572773 73984848 652395150 274641274 19567651 313454866 517733797 732834732 683830859 851387499 41462608 755742719 327386893 146422653 280719585 245862381 75849368 400405900 623426624 323900502 995684701 649837950 712790652 689384867 712068630 251496879 603708479 652192881 830106386 434833194 562491712 7093190 794371622 230556813 346620116 863101446 583807218 349090587 349434449 580680839 164857387 858407370 420826464 111043596 706255236 828752073 486821786 945421669 334275891 7749670 469804619 531998487 577456543 437330438 192802364 339161210 79451038 697562910 762676651 378714174 136277270 612489667 226816771 18447731 814031151 302415632 895311508 826637650 480121030 72644533 104253907 526628766 785779519 212194261 162176985 229171858 660299181 405518105 475658895 271893670 153602347 227044504 493230361 220368386 2456839 278002827 509864003 579236359 144720094 69430502 353996002 902690656 738366048 18491633 902501522 549399509 522545766 557160850 294333309 944294748 733035016 521453600 654630136 355163957 83445555 446062789 602883516 58164724 907889336 968279122 486960845 6092978 488051217 239187866 500350824 446413026 364867970 293570497 437561632 546514652 353147020 184699732 342059370 90908034 203706709 419444183 495246668 590236228 529826205 783503620 543077435 389342496 300468224 737345482 593103076 962272241 268050333 700208604 630238783 377190644 663585254 531081907 562207598 560055481 462273498 340097385 577843235 438543318 542695407 240460506 85696197 852960749 708243855 357474416 35233189 886404820 783773695 580663937 979996091 54888582 153040947 805904119 560313486 116387497 794826272 896287073 767874291 430061171 754591084 641547207 599926992 982019810 84811201 545913874 673760737 565719119 887158365 542060632 884307697 809680891 644419759 749572988 894828730 645628517 789681045 397480957 690692127 925108787 631439798 221405719 420992738 823536228 850184166 686938582 561412994 694931701 590472721 857763370 547795108 908024031 163676569 93224809 952424240 603702399 777896391 615989257 387932407 947630136 596984018 844375184 408007263 527596252 126707118 904693720 637968858 181854776 988697472 216218687 884035973 801361388 871033102 799464827 419251246 860180888 670516234 13638879 174702108 43525788 380590669 150639864 155316288 473919774 213510789 852837503 258472507 369947189 718610519 657211677 950407319 309727757 488494822 113764870 952317721 323855947 982056241 119995213 903306923 573858592 335915859 665953195 729432528 421470818 444041677 440431099 828648704 521790123 730000703 609341909 439574410 852276450 76946971 58248143 435433334 803096862 777840536 960372939 89722122 328721511 305873657 57219747 566132089 355343950 589824792 224852426 977308292 38843 850 1 9 0 45 999948001 30259309 372213360 289056086 775433580 58119018 538774197 837992957 472771686 536590018 252106864 623054442 829822817 246891915 290331115 851512626 998830160 216863680 100952917 944480631 354459430 21405671 399306270 367837900 449901442 702936843 682361744 228916148 169103518 218271388 346444528 151074213 4245939 324583604 481376117 412436806 331974041 209190102 317007795 46072809 833136994 869091638 594948136 5204650 227131699 99990168 131984264 770682503 320543350 910544010 777190186 456993169 842547257 431159999 480001598 252167964 710265293 542650458 586081485 720506200 300500479 953839294 480280812 21561643 30706706 146892853 230359747 87507155 32582952 355582967 807444188 265750249 170378882 114598491 468340730 211747361 335252948 905204063 117720160 232018389 934036717 381702929 881137160 583915971 969532484 662150008 252714377 177072465 34947620 392890688 304345883 372772782 340523795 97117067 812062418 656142761 212683518 481483411 236811734 789212512 912631201 20714908 970352009 851234322 853846811 551481116 301433940 421397422 519009646 38216905 74178165 423957050 913256683 208861132 621430710 386206721 419570596 198099642 431835967 891870805 986938191 354206003 478338045 14005542 869267475 169683493 321971392 672582573 501330652 804759405 257029926 664407676 38820750 502549666 684867953 95479072 519781898 213180467 161582508 497178343 833474582 970994432 420619997 170951961 200855750 228863356 774376500 30672534 878728350 991509074 378673844 175893219 73808920 386078794 749934203 429953003 892529177 745838804 7252492 139805137 290346282 396953402 370257390 248518548 489089264 686658871 362133910 599291259 425872440 978445292 938792804 75575498 481099504 218378762 88238874 514118437 971841093 863123334 240942413 988039859 764525486 647424477 569419192 288016050 619836973 855309962 832394064 942365057 758832882 912473065 660862782 982185794 851116341 66429934 184623712 683355123 144419936 430334214 790141252 73646049 125816878 83139872 725253033 347963601 919510924 338833821 817698340 488048212 16527581 77221805 239749855 113561041 849587453 864624173 571346248 59994782 122067425 117264415 173670492 394947049 707399863 49161712 578311545 829877148 120332060 765444005 263111501 394877252 904463334 862827571 360411469 889305222 968106937 267996483 661482097 352989799 650153782 137495950 720369838 928424411 805364368 365611940 851269050 820352134 498324858 805586733 148435560 944508071 644906343 516936617 549440445 269058288 403109421 470272390 347284458 272036337 689042408 483460622 320641865 9118185 595723362 741264212 485704771 534201317 305292484 144577781 816426873 295663815 152893470 449974148 734049369 666253875 272916650 912152978 675406498 449347603 229333927 709463609 131379346 970874472 217961599 331729021 860804340 182165953 802250855 571262301 993085488 800961276 892858182 517182805 962353339 47219598 425230429 642991567 494968406 9588165 135308118 249016484 708504481 427133360 541531853 673336163 656996979 211656855 460919858 998681952 827818106 600594695 314859321 9546699 431041154 563216792 652624990 374731252 417005332 564936213 844492719 690530839 685953465 173137848 406811675 647970813 207671572 214126554 294773877 605401196 529071808 993498765 784544264 728599053 817023761 268920261 383356776 980965331 855467642 983222542 674814970 742023613 854581332 19009854 513459263 805052451 920698461 203779385 582677751 732020093 863827531 78281292 731509237 233269605 676936101 412593277 392888437 175521058 802481980 986106347 338475269 177306019 62454223 350268772 261928899 985963368 481284652 668196003 280748109 68298393 509088326 864287405 689661238 523656897 785519759 760059197 541672511 703115534 499086944 375036355 140904309 759524017 410674231 17382929 205934224 66891099 828412569 635954731 331997085 302174893 467411892 443824207 944514964 562882459 361453491 110620 849912883 846453605 551761139 468114823 518452291 797323092 303514262 742977512 900492531 840488525 753907715 892643447 543509682 724965376 532801010 506203460 286664962 213044892 152846142 561220354 843802160 840420568 297576382 453985476 421793455 256851793 75190822 791960021 368194903 539326486 707666527 533254571 91250513 686147537 142474017 57346331 949667748 113070577 461257938 459210535 971524008 504917239 325092306 491226850 342743578 556581410 823937316 177260237 46781294 670965839 298660136 89860952 381539742 897420916 340096647 843786965 977509000 961133091 11545266 498144035 280825534 834305377 164820440 748413626 484469806 279444834 593011972 972510878 576245378 511484781 852737233 80234449 152198681 409652153 945283772 524575285 247687676 590231845 515791559 861763952 283063493 821886421 331347099 165744126 623986038 992077353 972907135 432405354 14973890 508410101 4953393 972231728 772722898 352440942 593350663 470215781 707530959 533292488 50333825 985909122 424217322 824047024 9762557 722529462 12582915 302013651 903372881 513323997 887590331 413936607 63126304 118225049 796415971 45750532 643997346 734883463 192827865 289978627 877256516 65191916 770161761 599392846 492759563 375147067 658767670 694578276 285208840 164020757 574233235 105793332 645935691 180325083 274519461 978465017 64433429 192343857 439774551 1999126 183540150 534027164 370492460 100666930 737397692 360091700 739864958 191445431 176096707 761267649 381938776 517304646 54559265 19093190 796264059 722438078 782531033 113268465 240995302 625763236 803138939 715946747 423093659 158322159 1744852 251817251 334804737 885784379 737307593 95580394 736803778 546736504 765306567 312320524 639589377 182148566 525350790 174530634 161110821 39741352 417630367 534171453 155643257 331653139 16577880 924495997 642135604 546923664 465455396 385234860 314481821 925556105 876578574 595717623 852867583 393298480 306031567 818534927 977869298 709528206 520390650 122327417 138172366 508674454 31552446 111084526 318686228 982720193 471598170 765404974 52222906 277870583 386378918 731077211 386917905 868913683 506015444 182903461 472864229 597525740 406614728 498433240 664101158 72447384 104969349 585057717 93667490 707288195 919796639 339218324 851448755 212390225 205863296 836755635 347508991 110258472 298685521 853947460 438126475 426543237 498459800 788903387 98854274 195956801 301373949 625942691 700520505 348812268 525777443 382091477 344623762 437260671 726069892 782520139 357845010 596421262 691080743 935237658 321860766 583567895 693276029 284630741 510490807 464766853 863197591 220958457 230969773 339139248 613233990 748599568 359609105 285524609 859488292 292647438 324904434 299803935 462387267 604308869 70610315 801112150 992238453 922336522 346807928 294544166 278543751 656284409 319019146 179730448 516021704 893400709 976681428 570560786 143677203 307262826 754424137 33563500 614772518 311052735 451794337 751496014 376959000 839381931 368539947 991115762 452673846 919136641 585591228 443902153 605935307 381214991 996707957 513194555 76779360 494144779 82682969 734327013 964589740 187493834 677445831 820040318 185265736 978878904 290561137 707658719 980022885 71695262 551788438 361781268 964426374 96741793 563482986 52913765 868407078 82604620 376071115 571605774 679380870 707272695 320186197 110552723 81195632 206152254 717453895 565640076 956328000 673815200 401035000 954190452 332289479 796258013 490306403 327459689 393377922 760867895 889793985 752883746 762267356 211514441 355211843 825266735 450607430 490638301 978973543 829934698 593192995 890808420 469561713 76823921 170635171 378721177 399674959 437691549 55726954 766028114 568047573 944367662 715623714 507190498 820231450 369217481 840683211 904852874 438037615 991422575 17058758 761721682 643402088 391372137 458158860 430499848 818137295 344990749 437367018 274464175 337151289 157260234 135504376 833262416 417719257 444766929 969492962 814027405 572844106 856817756 516295894 557488103 288118054 897092821 873555449 150514541 100528584 509270422 245743414 286813485 66256846 934426565 188230972 883828781 917912873 609395948 164232474 484464253 558378853 378840893 275674737 890704823 497002809 467639352 864604145 900489729 642139008 411364602 413034046 392940163 341465333 650809818 35980437 828210619 154606419 368921550 66150643 253477094 257341859 4514772 12331121 789199854 445391021 515093071 660038119 584012183 915416755 311365556 198739051 757542218 451635836 307795838 866686179 621407493 545434400 5406186 822515645 336183157 826342870 621403967 364452576 716791383 669782694 814417499 725373622 333616609 103170162 504753133 660074406 242529250 33600948 441376949 933658794 338453883 261647873 222821500 105211772 279152229 518936398 48087115 45382113 735236805 144793073 68999166 421775996 86988172 681899890 947825493 649330511 698730771 380568098 431058612 217026043 610986734 97410366 250801209 280226747 2092227 212922202 444061281 393118642 863073063 112850613 299417297 641614180 936927490 529062445 201506674 763935215 347446587 831713077 118465612 391603901 976350473 431436512 505742503 830205428 85587231 815615968 248151093 504738224 351976838 256415900 765290431 699715109 672539106 426302044 524130185 501276119 425192036 647786951 926263142 894477379 946431741 214461428 797948146 107574742 340997255 287325257 440685189 118505034 449354988 132732524 410014727 104728025 6957908 785808405 394290114 905063305 26570665 472414093 113775117 979456785 771372986 532393509 737269542 316555825 153920962 279975776 844813686 971387275 996482032 628123109 461007354 643507565 767458391 216498807 3731384 71540307 945729394 26104906 745405288 808837699 177780351 500930886 325724525 187801816 367177541 535754215 233245600 795678227 700853551 847898306 957406636 243631118 546645801 21847864 286443630 872446452 241689343 750723424 235746843 885258650 511563840 419220332 644657033 647749971 786705972 445600451 230854329 440273965 512551048 787898622 509630044 93350978 523381416 727813281 365518715 261195107 282472129 23846364 864319977 662716260 889330212 538445939 897627359 593509139 607774915 843718250 735865244 71857467 290361324 483412063 222426615 326961765 204959019 604669435 181177680 495481446 329648161 671081197 849652439 400436028 423959682 416996343 831674518 572068670 708183467 11581358 62568819 345173672 158223248 906380543 421289517 385695477 471112395 94273838 853342514 399508354 136684247 383244471 28057347 958902225 484548529 352610387 521139626 768355865 314843669 629295637 654864772 737768980 867898905 310602711 479252429 653423795 971469841 633741482 314679397 952066736 389101714 48388724 227637431 953731647 267052530 326573627 337285362 173402887 824046758 844816294 261654256 528092426 707611560 1875322 73981529 492193097 994230049 455272740 730235196 978688249 44492400 886273907 941897809 108501116 446139352 77805446 848224416 627048399 48342072 303150301 36709964 102104826 644527417 854629286 255111915 740982032 66840926 691034780 440125929 689714236 633651037 816905337 48737461 614865239 117350683 441161168 934247377 62505086 131321775 209177173 351263855 244462431 836915205 959789062 576721160 908898166 203719643 990479980 494156971 886293071 234604201 984058016 480934099 150469367 695560788 347743607 51535321 109682888 326764770 817285657 288632989 363090768 738494968 593730057 5529983 999988292 5 0 1 999998634 887468 636765977 512955430 525538310 263188713 723603795 663342771 426029874 465917941 373172336 471704457 374416355 90720607 963591976 383389817 992867728 387967057 390941572 175887743 527637438 907504359 995034273 975557621 770794884 318998174 418277007 924200673 80796745 446606388 39013644 87909285 153438989 75423150 33138204 836049554 83516262 270722166 296760831 606272291 578760298 749044898 932574756 532785966 638095905 648265703 799294492 204769497 955271760 752030222 308839561 881538231 161756750 148346572 9071147 17237043 184452281 564082255 330692428 739212293 707636504 953269920 217921818 314118749 520150234 62649533 827359956 831719578 318980353 226472927 807716175 105271580 313191103 593471752 996256970 793592044 156539568 114712417 393656163 428156850 899213550 805684845 814163441 964433169 787384611 817127197 472959112 701518041 360685647 621707852 491366042 956499001 734377890 993818110 602143401 924419979 872051934 141663455 78603207 531565266 910627798 853688947 19294036 920243768 30273821 281553994 607934591 42457358 582559393 14657389 534910961 155813558 25410440 135626065 307764773 766499510 120141812 499621443 310846754 142009620 150026338 628053072 133383727 323867994 912776511 624993249 977582982 973570163 612638585 779736102 721939712 180767932 137222963 411616687 125962869 13378164 393885569 66561015 663116966 464841646 486136046 189563926 869882201 302054688 635074760 48614053 521405223 489300064 746293387 963233328 530252777 425045195 311452627 860340857 180599476 157565365 453868374 397105781 809919285 588463039 15314268 660910612 804562453 835216831 768323323 370185013 691315867 380585151 78674131 239678521 155686467 94677753 59598160 220840085 684279558 217290022 109891184 537533994 788550460 493818683 398326064 100654646 91818874 748945885 13967106 999584994 117149360 155794470 571414884 842747259 27619428 708243130 555454982 132710029 359258633 649254832 96073570 164623856 695815112 433785701 144702297 287008859 208486309 582462971 818808524 624194385 829364850 767325231 374192297 383851216 738357704 779132099 498306982 328195479 477313943 558409401 371209236 956319182 308596107 117333624 293875220 770314431 17785829 214273614 204584119 1885352 780917052 611432218 636571429 88982515 220961381 136741667 188431674 363996303 565021830 748623169 967051752 505227200 976504403 483333177 308335078 252003793 742575387 117566958 316162961 326062761 936108821 791872863 750773942 111991111 116963784 220708288 696125856 933859774 646508845 236485719 20856496 979894319 960044698 138632529 543500774 884058526 237429450 58221448 45757574 769671472 447171964 331552052 922834877 252964523 664226175 183022332 606265167 339303689 259823103 386888293 456424734 264719437 542405816 61014214 579557574 570833325 673723287 923365863 463740456 464324063 244701079 508482473 755158690 308038108 868776133 885173340 214289642 911248450 221722543 827133960 500985325 225421199 247305708 521460412 392123474 88393916 921924998 670279037 509375238 565038799 920284560 975304356 198634940 519729553 168077726 679142010 359629911 354565784 462518581 638310372 120298036 713512692 745047820 447806631 229105402 693687635 967738727 988166857 478650666 934929168 256021584 499561074 138903129 836960011 716814465 634488588 995045809 3579592 374835562 744275649 90380511 257773156 640608445 676879587 430016053 912191060 404304927 310193629 118932777 966949225 543282539 889279307 681655812 95752265 732338572 798957510 388113918 868845304 63433967 121049105 385117354 849911462 69911011 121222552 435855305 677326463 896682737 672775134 135713567 187997959 758080922 854610996 246856578 611090572 304445917 123388453 73222325 878310198 408659279 515745945 286533478 316598487 46958408 853604087 432874269 11032266 590981153 794365040 548753964 630858088 589633475 36775454 24490596 695412533 424127744 853134294 791581147 272666228 571765352 549437872 53758664 653995891 527094987 892515125 508079938 222515632 550508162 386906276 720884286 600488256 361858313 174743385 391972274 518509829 310454767 185986944 178791476 584814673 642140859 812783458 693804635 923561626 425371988 830134796 487122015 881828835 870140021 813168849 288326091 242817999 625727136 227470782 794766334 314375597 913073972 624410345 890817174 240809544 56407029 731823406 501915110 27476215 548245010 716349128 524168039 417769653 8586882 31166870 632949179 888561310 129554943 619396566 39625246 234860680 291386311 740663132 335836890 786742556 105157797 964597128 689192126 95735934 474554916 540166926 120056440 573796043 526302779 379352121 335250356 91932472 24456515 655357702 177825658 273631310 703150156 679386464 860947276 968783942 511284994 639490913 578488155 677841260 166000409 602307025 985019676 923729003 729476310 136109704 284749271 522837466 397516033 73056708 1079340 625377850 722682687 768821892 581572980 950764922 746870966 444334755 665874851 661377657 940995412 963081675 77278279 577231116 242536390 674919117 515911260 859428450 958553647 571412759 713007028 228071352 327275188 443218927 913554812 607741011 792151329 513850403 532876855 139626039 252889099 675166660 563041269 370848153 597267281 921068146 553300880 721080291 899433543 781433901 335967887 210694213 505038856 664282057 992763583 338025707 193497833 876462511 476965025 167571210 814924575 321173468 300677987 462714259 708123227 221868248 448701061 163647083 916355960 781511521 99293964 273311414 163417638 145634981 908779048 809636616 837765599 420832395 239095347 801318026 853894182 600645274 907627540 762184454 793293168 885649457 155422657 644743445 10206734 143901315 305920251 175684819 838672 866944322 483316669 944104244 242003185 246439089 339108439 282673140 443726190 463542957 635720729 431791768 450009688 555642602 238091229 461217484 770328990 991872604 522750228 822281455 387740481 887611461 111535658 511178348 659448949 597246427 706958673 514833 109243689 834213503 137085595 98851645 101688111 108699309 887141640 329470574 308693780 328461500 425599814 526225648 448264531 888110697 479488490 863216709 317067808 759435334 592217643 260280758 41519528 160082770 860326027 496449401 495668709 234331302 449573203 176904473 93212799 958101457 545015436 820967634 563296471 336685110 423580019 987089736 784111517 878745857 535420954 416396185 485432719 97194216 830274486 524906813 61946450 436734522 177556551 914916605 132168363 888689493 326600816 834309630 788615493 716233754 890966556 689147663 963745520 294781020 244487576 648302165 698437501 956060464 62649118 122452833 231683728 179184395 870475103 92066698 752021384 862716816 135452402 309842828 496762430 281075790 58075351 523812771 601130188 594865117 521525761 923644861 268771803 187784311 103817575 418826495 344648958 829681127 348094629 563389769 137664581 19205041 809660555 886436947 949644232 865608001 970073278 819566210 80484367 356281683 573846132 392309173 178355283 521963079 300840049 824031155 123946819 528665456 362683831 399155039 453436298 659723037 757885199 107881930 993520154 742233487 697527461 67363836 102854731 550265866 529219228 612183298 663070607 605998407 734647597 427811238 178315801 876664013 253547527 960588710 649393471 164822117 73236452 626390971 331956502 647978083 493004813 898717942 514840676 962877678 722435496 660064255 741146076 13919165 407860414 744072262 801735376 887799652 190384062 986617306 93899888 682403108 968293247 148423221 328578142 49840930 548948047 644869612 661483156 299894639 828058724 83604729 15611259 334996708 256867466 794072866 389474596 365001136 918386893 444905336 21185636 687563048 761714354 738432134 761006149 752747760 864657245 338657790 158159430 720902059 741719695 812168470 796592514 722266704 927239385 437940916 493929496 490480930 705685913 148767413 485983444 89126870 932366328 394311274 874277287 476167235 506084552 562446339 76763965 90907667 851639756 967312702 723319887 751696047 952848342 100816774 578421205 861935900 38089218 321958510 17382277 11524455 592391551 505963973 462253958 108703025 607374561 639133718 886081515 722994210 61834394 407482391 456692341 461760111 130958636 511084926 54062691 70775864 289964743 364800199 988972988 23871665 85145094 818209109 917636208 502864659 35350184 815451060 989631917 142980133 798249471 237624348 606243935 864831660 118627048 99036299 42238937 346340655 545273792 567015313 720329351 823479844 882929487 384395578 797882659 295950529 349779954 34154355 427805571 729598924 49278931 793890934 929891152 746233170 547461158 522817670 981418181 15193421 41781169 636135321 577580146 5964243 64517365 56768936 380825421 15716078 783408725 462483489 632327355 848851954 61427551 805667525 176033345 418470057 855472087 688623396 455908563 29616323 433159860 225339137 740392284 888935806 665103011 606244755 502013715 388760860 776788528 277268937 237934207 100199628 274957208 455214611 739393510 332721000 730827374 149104414 508150451 617153235 695104685 928841024 514012598 324076019 354840271 907284628 681632451 277893038 879024123 851791236 837589465 352174973 519651011 782562875 202656727 355512281 990209292 490680151 508964529 393133746 583016190 718651208 500279812 302852404 345279890 301100327 500286045 908139904 796970687 752283086 205901880 642711922 816250085 305217687 189407116 50517712 418454600 124088743 788490148 245791183 34486677 397532777 110633380 983168687 268420035 263123869 800106675 722941531 725647782 487579756 768338253 602993 193033876 629428967 166273016 349612330 171107996 762235392 267470783 427641079 13383714 402101930 398940074 877982217 638853579 715086356 120222650 863722183 191842250 955079918 198407224 905774037 137081145 344671879 374292999 676610027 576374590 633610541 896352642 24976184 843710568 577551952 297154735 50457832 272989769 62953344 710692718 787400483 863480460 100461791 634958064 253923471 937569180 819813666 516941111 976478434 916708104 480681648 323316751 994195648 319955565 720027672 639589801 231486854 403729696 302235622 272403274 445320248 610401104 969148013 388341900 590475476 637356187 567858155 816345764 569661057 340816142 394291560 476248978 578865195 889166585 47113815 520428784 336542468 274779009 824207398 323985852 629330435 399379037 82661867 469235669 250259693 667622574 389583309 323272209 685828869 583024151 562432957 595445633 156373582 408232309 360900093 515794409 545342710 184147235 918810876 932442780 820313351 179682138 965540209 129727143 911369151 352579754 38546435 95687532 971080160 652561608 156062732 610479020 902044767 9337295 301989687 243625359 261208471 378979899 242626014 751359956 968580027 393168509 924321812 647751516 556290208 872977075 800826621 199310310 437094045 659426486 577909113 660048988 837915820 393907243 942521929 255804362 950067297 434407016 999800271 840079405 117308643 882966929 302161847 809504464 842726551 973612005 422899737 291205927 639919449 302558127 75365727 335870847 839348444 180838947 75591691 829487121 307727773 238841009 330790782 502618921 477143691 983895071 705513480 769936442 576528085 466863065 860143685 974756020 267619825 825191367 641726662 344240382 900675477 210552637 685077842 228148626 125247389 369452687 104296235 711361075 249868562 734763102 294504257 692399212 861495097 706749917 674459620 444166015 78442197 998202226 2830 1000000006""" def fft_convolve(f, g): """ 数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで， 30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える． """ Lf, Lg = f.shape[-1], g.shape[-1] L = Lf + Lg - 1 fft_len = 1 << L.bit_length() fh, fl = f >> 15, f & (1 << 15) - 1 gh, gl = g >> 15, g & (1 << 15) - 1 Ffh = np.fft.rfft(fh, fft_len) Ffl = np.fft.rfft(fl, fft_len) Fgh = np.fft.rfft(gh, fft_len) Fgl = np.fft.rfft(gl, fft_len) a = np.rint(np.fft.irfft(Ffl * Fgl)[..., :L]).astype(np.int64) % MOD b = np.rint(np.fft.irfft(Ffh * Fgl + Ffl * Fgh)[..., :L]).astype( np.int64) % MOD c = np.rint(np.fft.irfft(Ffh * Fgh)[..., :L]).astype(np.int64) % MOD return (a + (b << 15) + (c << 30)) % MOD def coef_of_generating_function(P, Q, N): """compute the coefficient [x^N] P/Q of rational power series. Parameters ---------- P : np.ndarray Numerator. Q : np.ndarray Denominator Q[0] == 1 and len(Q) == len(P) + 1 is assumed. N : int The coefficient to compute. """ assert Q[0] == 1 and len(Q) == len(P) + 1 def convolve(f, g): return fft_convolve(f, g) while N: Q1 = np.empty_like(Q) Q1[::2] = Q[::2] Q1[1::2] = MOD - Q[1::2] P = convolve(P, Q1)[N & 1::2] Q = convolve(Q, Q1)[::2] N >>= 1 return P[0] def parse_txt(txt): data = {} txt = txt.split('\n') for i in range(0, len(txt), 3): H = int(txt[i]) P = np.array(txt[i + 1].split(), np.int64) Q = np.array(txt[i + 2].split(), np.int64) data[H] = (P, Q) return data def main(H, W): data = parse_txt(txt) P, Q = data[H] return coef_of_generating_function(P, Q, W) # main(2, 2), main(5, 6), main(6, 5), main(7, 77) # worst = (1<<59)-1 # %timeit main(9, worst) print(main(*map(int, read().split())))