Problem:


Score : 800 points

Problem Statement

Sig has built his own keyboard. Designed for ultimate simplicity, this keyboard only has 3 keys on it: the 0 key, the 1 key and the backspace key.

To begin with, he is using a plain text editor with this keyboard. This editor always displays one string (possibly empty). Just after the editor is launched, this string is empty. When each key on the keyboard is pressed, the following changes occur to the string:

The 0 key: a letter 0 will be inserted to the right of the string.

The 1 key: a letter 1 will be inserted to the right of the string.

The backspace key: if the string is empty, nothing happens. Otherwise, the rightmost letter of the string is deleted.

Sig has launched the editor, and pressed these keys N times in total. As a result, the editor displays a string s. Find the number of such ways to press the keys, modulo 10^9 + 7.

Constraints

1 ≦ N ≦ 5000

1 ≦ |s| ≦ N

s consists of the letters 0 and 1.

Partial Score

400 points will be awarded for passing the test set satisfying 1 ≦ N ≦ 300.

Input

The input is given from Standard Input in the following format:

N
s

Output

Print the number of the ways to press the keys N times in total such that the editor displays the string s in the end, modulo 10^9+7.

Sample Input 1

3
0

Sample Output 1

5

We will denote the backspace key by B. The following 5 ways to press the keys will cause the editor to display the string 0 in the end: 00B, 01B, 0B0, 1B0, BB0. In the last way, nothing will happen when the backspace key is pressed.

Sample Input 2

300
1100100

Sample Output 2

519054663

Sample Input 3

5000
01000001011101000100001101101111011001000110010101110010000

Sample Output 3

500886057



Sample input:
3
0


Sample output:
5

Submission status: Accepted

Solution code:
import numpy as np

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod


import sys
import numpy as np

def garner(A, M, mod):
    # Garner のアルゴリズム
    # 参考: https://math314.hateblo.jp/entry/2015/05/07/014908
    M.append(mod)
    coffs = [1] * len(M)
    constants = np.zeros((len(M),)+A[0].shape, dtype=np.int64)
    for i, (a, m) in enumerate(zip(A, M[:-1])):
        v = (a - constants[i]) * pow(coffs[i], m-2, m) % m
        for j, mm in enumerate(M[i+1:], i+1):
            constants[j] = (constants[j] + coffs[j] * v) % mm
            coffs[j] = coffs[j] * m % mm
    return constants[-1]

def convolve_mod(A, B, mod=10**9+7):
    # 任意 mod 畳み込み
    #mods = [1000003, 1000033, 1000037, 1000039]  # 要素数が 10**3 程度の場合（誤差 6*2+3=15<16  復元 6*4=24>21=9*2+3）
    mods = [100003, 100019, 100043, 100049, 100057]  # 要素数が10**5 程度の場合（誤差 5*2+5=15<16  復元 5*5=25>23=9*2+5）
    #mods = [63097, 63103, 63113, 63127, 63131]  # もっと切り詰める（10**4.8=63096 誤差 4.8*2+5=14.6<16  復元 4.8*5=24>23=9*2+5）
    mods_np = np.array(mods, dtype=np.int32)
    fft, ifft = np.fft.rfft, np.fft.irfft
    a, b = len(A), len(B)
    if a == b == 1:
        return np.array([A[0] * B[0]]) % mod
    n = a + b - 1  # 畳み込みの結果の長さ
    k = 1 << (n - 1).bit_length()  # n 以上の最小の 2 冪
    AB = np.zeros((2, len(mods), k), dtype=np.int64)  # ここの dtype は fft 後の dtype に関係しない
    AB[0, :, :a] = A
    AB[1, :, :b] = B
    AB[:, :, :] %= mods_np[:, None]
    C = ifft(fft(AB[0]) * fft(AB[1]))[:, :n]
    C = ((C + 0.5) % mods_np[:, None]).astype(np.int64)
    return garner(C, mods, mod)

def main():
    mod = 10**9+7
    comb = Combination(10101)
    
    # OEIS A052501
    A = []
    for i in range(5001):
        c = comb(2*i, i) * pow(i+1, mod-2, mod)
        A.append(c * pow(2, i, mod) % mod)
    A = np.array(A)
    
    # (OEIS A126087)
    # B = []
    # T = [1]
    # s = 0
    # for n in range(1, 5003):
    #     T_new = T[1:] + [0, 0]
    #     for i, t in enumerate(T[:-1]):
    #         T_new[i+1] = (T_new[i+1] + t*2) % mod
    #     T_new[0] = (T_new[0]+T[0]) % mod
    #     B.append(T_new[0])
    #     T = T_new
    B = [1, 1, 3, 5, 15, 29, 87, 181, 543, 1181, 3543, 7941, 23823, 54573, 163719, 381333, 1143999, 2699837, 8099511, 19319845, 57959535, 139480397, 418441191, 14536110, 43608330, 426790700, 280372093, 669442763, 8328275, 388935521, 166806556, 139062193, 417186579, 851069935, 553209791, 56037501, 168112503, 267344849, 802034547, 652357957, 957073864, 700539444, 101618318, 396133601, 188400796, 726068788, 178206350, 741117043, 223351115, 742918242, 228754712, 312476430, 937429290, 321447427, 964342281, 33806458, 101419374, 751551908, 254655710, 363399877, 90199624, 156603031, 469809093, 915208994, 745626968, 462850378, 388551127, 246596506, 739789518, 467733091, 403199266, 447059337, 341178004, 278644239, 835932717, 889171503, 667514495, 782338579, 347015723, 245469453, 736408359, 931113934, 793341788, 806025176, 418075514, 217760052, 653280156, 768963093, 306889265, 711216158, 133648460, 910406639, 731219903, 926508572, 779525702, 768155852, 304467542, 326462370, 979387110, 463504958, 390514867, 133036428, 399109284, 590456714, 771370135, 483338560, 450015673, 888488321, 665464949, 350083538, 50250607, 118756719, 356270157, 661690728, 985072177, 23869570, 71608710, 38222864, 114668592, 366500311, 99500926, 572394560, 717183673, 709028776, 127086314, 639656744, 918970225, 900643476, 701930414, 382964607, 148893814, 250036934, 750110802, 219858937, 659576811, 916791044, 750373118, 157680701, 473042103, 487635248, 462905737, 404083031, 212249086, 590446235, 771338698, 6013544, 18040632, 991399340, 974198006, 990849114, 972547328, 558168879, 674506630, 801159551, 403478639, 158070240, 474210720, 809129432, 427388282, 866168462, 598505372, 788433413, 365300225, 674421938, 23265800, 831193374, 493580108, 34565782, 103697346, 510567483, 531702442, 767728249, 303184733, 404642877, 213928624, 853165051, 559495139, 296074444, 888223332, 256370401, 769111203, 929943512, 789830522, 312639125, 937917375, 495300751, 485902246, 972025833, 916077485, 766239658, 298718960, 912963713, 738891125, 637708625, 913125868, 178553316, 535659948, 430788617, 292365844, 288710724, 866132172, 812694564, 438083678, 768129860, 304389566, 442776557, 328329664, 314589440, 943768320, 1868510, 5605530, 833714184, 501142538, 404937555, 214812658, 978572016, 935716034, 324168948, 972506844, 197285144, 591855432, 632087160, 896261473, 377752714, 133258135, 882603909, 647811713, 807878557, 423635657, 722338539, 167015603, 789937499, 369812483, 339651082, 18953239, 44648793, 133946379, 103702425, 311107275, 978041817, 934125437, 122643334, 367930002, 355736134, 67208395, 436516581, 309549736, 107629577, 322888731, 111327069, 333981207, 367739160, 103217473, 894366798, 683100380, 390949155, 172847458, 219945373, 659836119, 802910542, 408731612, 898291568, 694874690, 491207321, 473621956, 696998132, 90994382, 24477213, 73431639, 121003549, 363010647, 656403179, 969209530, 302011238, 906033714, 621477008, 864431017, 217130939, 651392817, 919981289, 759943853, 243207256, 729621768, 265163174, 795489522, 263176272, 789528816, 59189222, 177567666, 310716811, 932150433, 860725050, 582175136, 153427859, 460283577, 197672923, 593018769, 925701914, 777105728, 652750427, 958251274, 407430445, 222291328, 96759999, 290279997, 472290021, 416870056, 456902630, 370707883, 514234291, 542702866, 44831399, 134494197, 788216213, 364648625, 724873033, 174619085, 938751738, 816255200, 911804344, 735413018, 267341221, 802023663, 75547515, 226642545, 802404278, 407212820, 387611837, 162835504, 131495508, 394486524, 51974757, 155924271, 581030990, 743092963, 341540130, 24620383, 679956305, 39868901, 431467085, 294401248, 426377279, 279131830, 447213546, 341640631, 410299788, 230899357, 162936579, 488809737, 853235231, 559705679, 906282997, 718848977, 433049831, 299149486, 248134475, 744403425, 260998812, 782996436, 102778462, 308335386, 43466084, 130398252, 836558177, 509674517, 390595580, 171786733, 243051360, 729154080, 221249400, 663748200, 549684743, 649054222, 378848148, 136544437, 963222440, 889667306, 935582264, 806746778, 588678111, 766034326, 315651076, 946953228, 980147809, 940443413, 994332441, 982997309, 322308459, 966925377, 187412112, 562236336, 411227448, 233682337, 234787384, 704362152, 987025193, 961075565, 550680030, 652040083, 735699850, 207099536, 721841180, 165523526, 651373967, 954121894, 564548234, 693644695, 245325054, 735975162, 650015809, 950047420, 623248003, 869744002, 778245844, 334737518, 38880247, 116640741, 950632187, 851896547, 869900167, 609700487, 187475200, 562425600, 213226770, 639680310, 998418232, 995254682, 270537038, 811611114, 757588227, 272764667, 660180124, 980540365, 252273970, 756821910, 325744671, 977234013, 302411523, 907234569, 576250102, 728750299, 57669416, 173008248, 551377419, 654132250, 829342660, 488027966, 710350562, 131051672, 176820813, 530462439, 783704896, 351114674, 198458213, 595374639, 834136739, 502410203, 805847845, 417543521, 443379759, 330139270, 90917952, 272753856, 599823090, 799469263, 413222975, 239668918, 144460903, 433382709, 601204964, 803614885, 448059198, 344177587, 454947208, 364841617, 864306956, 592920854, 747741645, 243224921, 983058532, 949175582, 936669048, 810007130, 130475154, 391425462, 39612605, 118837815, 695662137, 86986397, 822843470, 468530396, 946427128, 839281370, 255503173, 766509519, 229624121, 688872363, 161353001, 484059003, 269517079, 808551237, 873505478, 620516420, 137322910, 411968730, 784746535, 354239591, 49559330, 148677990, 200201278, 600603834, 784173380, 352520126, 212998867, 638996601, 850942476, 552827414, 839727494, 519182468, 399144292, 197432869, 677184264, 31552778, 594283177, 782849524, 3359066, 10077198, 375315202, 125945599, 926652803, 779958395, 840982921, 522948749, 274287637, 822862911, 364115072, 92345209, 178248998, 534746994, 62782906, 188348718, 10125159, 30375477, 43887369, 131662107, 304864555, 914593665, 282228246, 846684738, 104136462, 312409386, 686230526, 58691564, 897378751, 692136239, 211389162, 634167486, 417400716, 252202141, 253725498, 761176494, 844235022, 532705052, 698197612, 94592822, 712703222, 138109652, 151547059, 454641177, 651680234, 955040695, 840416712, 521250122, 806164857, 418494557, 101365696, 304097088, 761871457, 285614357, 928674409, 786023213, 125634495, 376903485, 184891139, 554673417, 433130722, 299392159, 754361926, 263085764, 336116396, 8349181, 310182871, 930548613, 20803768, 62411304, 903887117, 711661337, 762524523, 287573555, 577943215, 733829638, 313360112, 940080336, 15401226, 46203678, 949589565, 848768681, 199490340, 598471020, 349286863, 47860582, 827361518, 482084540, 912565509, 737696513, 250091996, 750275988, 807546653, 422639945, 274312568, 822937704, 313920570, 941761710, 438256149, 314768440, 715946919, 147840743, 708184656, 124553954, 709450316, 128350934, 602912754, 808738255, 353276312, 59828929, 372316580, 116949733, 829807418, 489422240, 169471503, 508414509, 566612519, 699837550, 385444665, 156333988, 352646463, 57939382, 247283608, 741850824, 401332811, 203998426, 619129613, 857388832, 170263752, 510791256, 526977653, 580932952, 462744735, 388234198, 407180751, 221542246, 656084248, 968252737, 728293306, 184879904, 752883294, 258649868, 450584106, 351752311, 544584862, 633754579, 84125473, 252376419, 447933212, 343799629, 95435131, 286305393, 731771271, 195313799, 20328427, 60985281, 361240842, 83722519, 671191928, 13575770, 552408286, 657224851, 721691592, 165074762, 86664420, 259993260, 456306417, 368919244, 793693842, 381081512, 787459772, 362379302, 860542956, 581628854, 654181651, 962544946, 216378666, 649135998, 532060672, 596182009, 460056948, 380170837, 862718225, 588154661, 252908380, 758725140, 279625799, 838877397, 535715980, 607147933, 269563916, 808691748, 945918035, 837754091, 154676574, 464029722, 768010428, 304031270, 271643342, 814930026, 110953311, 332859933, 965265027, 895795067, 882236267, 646708787, 492546420, 477639253, 204787729, 614363187, 340705793, 22117372, 79879902, 239639706, 302378339, 907135017, 305516802, 916550406, 500477224, 501431665, 953235840, 859707506, 81378462, 244135386, 574381658, 723144967, 931558832, 794676482, 756497113, 269491325, 950994207, 852982607, 990111656, 970334954, 462489386, 387468151, 478171028, 434513077, 102475005, 307425015, 450609266, 351827791, 640646720, 921940153, 660057217, 980171644, 97697070, 293091210, 410926792, 232780369, 533061691, 599185066, 94814348, 284443044, 591486759, 774460270, 589619088, 768857257, 918123849, 754371533, 121590764, 364772292, 869989984, 609969938, 239578028, 718734084, 875679310, 627037916, 993016613, 979049825, 919450736, 758352194, 720465230, 161395676, 14094036, 42282108, 302863303, 908589909, 889845328, 669535970, 842381777, 527145317, 157554451, 472663353, 883942031, 651826079, 822031415, 466094231, 651596042, 954788119, 942244314, 826732928, 937139369, 811418093, 939819798, 819459380, 809309210, 427927616, 265476219, 796428657, 134406054, 403218162, 192495846, 577487538, 299304152, 897912456, 981349311, 944047919, 477280763, 431842282, 471595163, 414785482, 413970278, 241910827, 992082790, 976248356, 225352248, 676056744, 572688272, 718064809, 558721284, 676163845, 130616084, 391848252, 832010676, 496032014, 115697611, 347092833, 93633934, 280901802, 129239903, 387719709, 307560046, 922680138, 95962188, 287886564, 879296072, 637888202, 149432400, 448297200, 527040480, 581121433, 601048956, 803146861, 950705902, 852117692, 871578487, 614735447, 82754093, 248262279, 660332026, 980996071, 893804061, 681412169, 88468414, 265405242, 33221238, 99663714, 939731968, 819195890, 739972718, 219918140, 749040710, 247122116, 801563550, 404690636, 236630755, 709892265, 624978250, 874934743, 440020363, 320061082, 364356548, 93069637, 155150738, 465452214, 371715422, 115146259, 202060610, 606181830, 827636133, 482908385, 538831212, 616493629, 378941971, 136825906, 263812232, 791436696, 618404108, 855212317, 153915113, 461745339, 298303841, 894911523, 113284130, 339852390, 803392857, 410178557, 260082583, 780247749, 358210240, 74630713, 940762673, 822288005, 589779962, 769339879, 811787240, 435361706, 860754478, 582263420, 246845940, 740537820, 618646034, 855938095, 644576249, 933728740, 438804011, 316412026, 17018757, 51056271, 501321648, 503964937, 123746504, 371239512, 386759057, 160277164, 296927787, 890783361, 111407321, 334221963, 746779401, 240338189, 703297704, 109893098, 963387317, 890161937, 670286128, 10858370, 250899743, 752699229, 906102813, 718308425, 876619115, 629857331, 581348907, 744046714, 724583247, 173749727, 939419740, 818259206, 158711627, 476134881, 288001154, 864003462, 121200565, 363601695, 625038908, 875116717, 691068703, 73206095, 605836137, 817508404, 561226264, 683678785, 233161202, 699483606, 752656343, 257969015, 23948767, 71846301, 884546419, 653639243, 236769210, 710307630, 171114385, 513343155, 986347363, 959042075, 333414811, 244426, 166995463, 500986389, 376717054, 130151155, 64704553, 194113659, 51268642, 153805926, 965053861, 895161569, 568818145, 706454428, 562062327, 686186974, 789736896, 369210674, 243196216, 729588648, 121664744, 364994232, 50970893, 152912679, 555142002, 665425999, 910894466, 732683384, 447200174, 341600515, 300419995, 901259985, 883037580, 649112726, 989971351, 969914039, 19054461, 57163383, 122166129, 366498387, 85347227, 256041681, 710715576, 132146714, 396494397, 189483184, 54596634, 163789902, 274398547, 823195641, 913331227, 739993667, 532577683, 597733042, 290662344, 871987032, 3271512, 9814536, 407309900, 221929693, 650120906, 950362711, 15026066, 45078198, 690245233, 70735685, 937039566, 811118684, 342654163, 27962482, 628455737, 885367204, 606449346, 819348031, 792914801, 378744389, 607757349, 823272040, 830441590, 491324756, 148041753, 444125259, 489024731, 467074186, 805370506, 416111504, 903812117, 711436337, 924163321, 772489949, 112578142, 337734426, 298264465, 894793395, 597983123, 793949362, 568920357, 706761064, 594638461, 783915376, 853667588, 561002750, 414432342, 243297019, 493238575, 479715718, 448341412, 345024229, 683967935, 51903791, 598602746, 795808231, 297375178, 892125534, 507108659, 521325970, 920604510, 761813516, 136172586, 408517758, 283707228, 851121684, 615936248, 847808737, 574579465, 723738388, 770222112, 310666322, 198987338, 596962014, 884105468, 652316390, 214819699, 644459097, 145560507, 436681521, 897780215, 693340631, 687243676, 61731014, 666592105, 999776308, 191225066, 573675198, 314900881, 944702643, 644020717, 932062144, 237782324, 713346972, 516310522, 548931559, 877513487, 632540447, 992476131, 977428379, 778816152, 336448442, 177190166, 531570498, 68030150, 204090450, 483417897, 450253684, 576005761, 728017276, 119850663, 359551989, 262607190, 787821570, 565555933, 696667792, 600568123, 801704362, 900281768, 700845290, 708051461, 124154369, 782973386, 348920144, 829278242, 487834712, 168182515, 504547545, 732793403, 198380195, 251489948, 754469844, 561392040, 684176113, 782157685, 346473041, 52448015, 157344045, 165317837, 495953511, 760280447, 280841327, 6460634, 19381902, 874676790, 624030356, 313463443, 940390329, 495698951, 487096846, 877193160, 631579466, 956297962, 868893872, 386244302, 158732899, 269682623, 809047869, 197803505, 593410515, 68055237, 204165711, 253132778, 759398334, 488757902, 466273699, 170556436, 511669308, 100974043, 302922129, 698622908, 95868710, 837824745, 513474221, 540870697, 622612084, 182091480, 546274440, 371328779, 113986330, 652341339, 957024010, 319147553, 957442659, 425779704, 277339105, 101298324, 303894972, 906908394, 720725168, 520855026, 562565071, 694025796, 82077374, 899626500, 698879486, 158441947, 475325841, 737986394, 213959168, 684386437, 53159297, 151672796, 455018388, 904028422, 712085252, 11284044, 33852132, 473233390, 419700163, 649114646, 947343931, 520824045, 562472128, 175610866, 526832598, 436119034, 308357095, 364301899, 92905690, 90576438, 271729314, 881447745, 644343221, 686168639, 58505903, 10835390, 32506170, 944619271, 833857799, 574247317, 722741944, 506781240, 520343713, 1989686, 5969058, 259631962, 778895886, 358466370, 75399103, 424640433, 273921292, 184452758, 553358274, 665340099, 996020290, 402215002, 206644999, 154926834, 464780502, 98062628, 294187884, 36045113, 108135339, 695573162, 86719472, 943091296, 829273874, 594387502, 783162499, 418258886, 254776651, 301149798, 903449394, 913605085, 740815241, 333509959, 529870, 201349432, 604048296, 26167624, 78502872, 664555062, 993665179, 575063380, 725190133, 121034200, 363102600, 595700583, 787101742, 254124050, 762372150, 38141323, 114423969, 516631288, 549893857, 225144545, 675433635, 946168633, 838505885, 75884096, 227652288, 712154213, 136462625, 481444704, 444334105, 182517876, 547553628, 132166594, 396499782, 661612653, 984837952, 9444756, 28334268, 10287161, 30861483, 175527813, 526583439, 31315751, 93947253, 803243007, 409729007, 96815605, 290446815, 757912785, 273738341, 32051203, 96153609, 470752585, 412257748, 152806564, 458419692, 75461433, 226384299, 574987969, 724963900, 949436601, 848309789, 47780645, 143341935, 931923632, 795770882, 66255600, 198766800, 547001528, 641004577, 609699520, 829098553, 964701591, 894104759, 401949129, 205847380, 756025338, 268076000, 602034033, 806102092, 845457709, 536373113, 854277168, 562831490, 58350191, 175050573, 285076516, 855229548, 796262272, 388786802, 515516073, 546548212, 438263952, 314791849, 869128125, 607384361, 158152559, 474457677, 251773427, 755320281, 278941335, 836824005, 25862591, 77587773, 566818576, 700455721, 36366919, 109100757, 5041022, 15123066, 96620638, 289861914, 666780822, 342452, 381968092, 145904269, 724390841, 173172509, 259700595, 779101785, 221588437, 664765311, 252799097, 758397291, 336179975, 8539918, 760450500, 281351486, 72331784, 216995352, 753661675, 260985011, 475097827, 425293474, 618083453, 854250352, 297493743, 892481229, 641700989, 925102960, 191180369, 573541107, 566681939, 700045810, 442548327, 327644974, 645987228, 937961677, 301537364, 904612092, 574605434, 723816295, 938076915, 814230731, 28149544, 84448632, 101612816, 304838448, 622242081, 866726236, 923509808, 770529410, 22054348, 66163044, 366076469, 98229400, 485238030, 455714083, 767997905, 303993701, 668545276, 5635814, 620717546, 862152631, 359277714, 77833135, 901712113, 705136325, 301511450, 904534350, 976349593, 929048765, 526846892, 580540669, 783893913, 351681725, 646517745, 939553228, 616361426, 849084271, 430750207, 292250614, 302304272, 906912816, 502649182, 507947539, 723434877, 170304617, 372225325, 116675968, 39555432, 118666296, 678142783, 34428335, 930284876, 790854614, 270646302, 811938906, 700297899, 100893683, 367523076, 102569221, 23091332, 69273996, 537924340, 613773013, 119023391, 357070173, 682311164, 46933478, 268501855, 805505565, 234597786, 703793358, 245942494, 737827482, 370375262, 111125779, 783008113, 349024325, 858263669, 574790993, 685356444, 56069318, 410522142, 231566419, 489924948, 469774837, 260205863, 780617589, 273794340, 821383020, 38070392, 114211176, 648797881, 946393636, 1378682, 4136046, 588330552, 764991649, 441807172, 325421509, 859715856, 579147554, 558722386, 676167151, 840388662, 521165972, 667506448, 2519330, 587106625, 761319868, 309574603, 928723809, 673723741, 21171209, 718391272, 155173802, 368459051, 105377146, 826806477, 480419417, 844395576, 533186714, 958611711, 875835119, 869070718, 607212140, 546056175, 638168518, 826061619, 478184843, 564144058, 692432167, 796553053, 389659145, 755993842, 267981512, 558261443, 674784322, 720952827, 162858467, 316801804, 950405412, 575868544, 727605625, 181396947, 544190841, 537490345, 612471028, 222070576, 666211728, 534598038, 603794107, 481377797, 444133384, 64864092, 194592276, 56965077, 170895231, 726457903, 179373695, 615129930, 845389783, 53552153, 160656459, 27598822, 82796466, 926627478, 779882420, 792114601, 376343789, 397520652, 192561949, 627149415, 881448238, 886792271, 660376799, 805947496, 417842474, 724168376, 172505114, 444708514, 334125535, 290854127, 872562381, 553110557, 659331664, 943083036, 829249094, 111715713, 335147139, 585333334, 755999995, 945508146, 836524424, 374459076, 123377221, 180044223, 540132669, 30821457, 92464371, 110333743, 331001229, 87486721, 262460163, 69839579, 209518737, 440022902, 320068699, 959961462, 879884372, 869926990, 609780956, 222109940, 666329820, 667469846, 2409524, 552212512, 656637529, 661694672, 985084009, 136974738, 410924214, 286341925, 859025775, 699353331, 98059979, 17144764, 51434292, 73220126, 219660378, 765556836, 296670494, 562173922, 686521759, 918096175, 754288511, 767866130, 303598376, 545135641, 635406916, 345773632, 37320889, 352485090, 57455263, 152426380, 457279140, 915615966, 746847884, 269189943, 807569829, 304259823, 912779469, 798164779, 394494323, 217847030, 653541090, 861357755, 584073251, 235965714, 707897142, 691236920, 73710746, 877805992, 633417962, 75710361, 227131083, 243181068, 729543204, 173491792, 520475376, 586984605, 760953808, 822978768, 468936290, 186102252, 558306756, 702481159, 107443463, 228090087, 684270261, 955465024, 866395058, 876292048, 628876130, 585520606, 756561811, 742470948, 227412830, 955266269, 865798793, 655740377, 967221124, 25251458, 75754374, 645445336, 936336001, 136406838, 409220514, 950536169, 851608493, 979358500, 938075486, 114879014, 344637042, 236429328, 709287984, 843939852, 531819542, 378273156, 134819461, 683312753, 49938245, 108754425, 326263275, 16928684, 50786052, 961975591, 885926759, 331027703, 993083109, 981381277, 944143817, 542792054, 628376155, 82414817, 247244451, 151102496, 453307488, 662658106, 987974311, 598603636, 795810901, 162540136, 487620408, 388553819, 165661450, 12659333, 37977999, 443972547, 331917634, 958437012, 875311022, 382843065, 148529188, 167077427, 501232281, 976648787, 929946347, 360228512, 80685529, 942103925, 826311761, 876690365, 630071081, 752632735, 257898191, 334611056, 3833161, 850976260, 552928766, 663965290, 991895863, 282269401, 846808203, 881592836, 644778494, 509566393, 528699172, 397150974, 191452915, 714590977, 143772917, 50816827, 152450481, 55416008, 166248024, 388787286, 166361851, 681197955, 43593851, 687588891, 62766659, 783961140, 351883406, 916376723, 749130155, 413965678, 241897027, 924317645, 772952921, 258638360, 775915080, 815738960, 447216866, 393190260, 179570773, 24008879, 72026637, 271348413, 814045239, 720638114, 161914328, 684674993, 54024965, 713799627, 141398867, 939246344, 817739018, 280740514, 842221542, 784638134, 353914388, 674636421, 23909249, 373018944, 119056825, 704548089, 113644253, 318088112, 954264336, 76531215, 229593645, 972829003, 918486995, 611012084, 833036245, 870548504, 611645498, 32627571, 97882713, 369545522, 108636559, 259883743, 779651229, 564713059, 694139170, 484407817, 453223444, 401455205, 204365608, 816508899, 449526683, 535833981, 607501936, 964400938, 893202800, 584309243, 752927722, 777951377, 333854117, 148445441, 445336323, 863651353, 590954045, 167570882, 502712646, 890485864, 671457578, 386598133, 159794392, 362793574, 88380715, 919434696, 758304074, 168519818, 505559454, 629815691, 889447066, 83863656, 251590968, 533792270, 601376803, 737466642, 212399912, 629299460, 887898373, 980323814, 940971428, 499298171, 497894506, 732010503, 196031495, 136690074, 410070222, 119910006, 359730018, 528071602, 584214799, 166294381, 498883143, 191048771, 573146313, 180894862, 542684586, 253233195, 759699585, 707583807, 122751407, 467043814, 401131435, 529418344, 588255025, 405369245, 216107728, 36842539, 110527617, 217295958, 651887874, 332779795, 998339385, 458099127, 374297374, 824970217, 474910637, 840126827, 520380467, 476091387, 428274154, 447128417, 341385244, 966299443, 898898315, 310538895, 931616685, 178762482, 536287446, 807300668, 421901990, 369283177, 107849524, 876027909, 628083713, 160175591, 480526773, 963776134, 891328388, 850294151, 550882439, 382448961, 147346876, 994271873, 982815605, 201319720, 603959160, 959455848, 878367530, 138090295, 414270885, 763223955, 289671851, 641531880, 924595633, 121138991, 363416973, 144492772, 433478316, 96561653, 289684959, 627505203, 882515602, 950574927, 851724767, 681716667, 45149987, 288319349, 864958047, 103705508, 311116524, 555216699, 665650090, 175537289, 526611867, 253270339, 759811017, 337397159, 12191470, 641771740, 925315213, 707735935, 123207791, 696461424, 89384258, 428563906, 285691711, 624433108, 873299317, 796350612, 389051822, 416998117, 250994344, 959656477, 878969417, 85001017, 255003051, 105178916, 315536748, 387272106, 161816311, 219522334, 658567002, 593419229, 780257680, 786929834, 360789488, 444750774, 334252315, 596298579, 788895730, 665238394, 995715175, 73273034, 219819102, 725478948, 176436830, 714469991, 143409959, 425143015, 275429038, 571910005, 715730008, 91250869, 273752607, 82955424, 248866272, 102653158, 307959474, 224525497, 673576491, 388291889, 164875660, 81795515, 245386545, 11663362, 34990086, 55869390, 167608170, 776610958, 329832860, 346817141, 40451416, 862539394, 587618168, 170737297, 512211891, 609411018, 828233047, 314667188, 944001564, 288344076, 865032228, 327131363, 981394089, 623197447, 869592334, 704924654, 114773948, 832196917, 496590737, 836729223, 510187655, 481931453, 445794352, 294670804, 884012412, 882246406, 646739204, 809164841, 427494509, 32358369, 97075107, 410337258, 231011767, 265066282, 795198846, 513085687, 539257054, 522057831, 566173486, 193619575, 580858725, 638548808, 915646417, 471431776, 414295321, 472041909, 416125720, 751911393, 255734165, 670783486, 12350444, 871932692, 615798062, 655460148, 966380437, 100596502, 301789506, 791695149, 375085433, 639917218, 919751647, 697317392, 91952162, 900304150, 700912436, 864135834, 592407488, 13889866, 41669598, 601294124, 803882365, 483615779, 450847330, 519283688, 557851057, 658945827, 976837474, 799228268, 397684790, 603232446, 809697331, 406674821, 220024456, 91889743, 275669229, 184189217, 552567651, 796202248, 388606730, 360249777, 80749324, 208614826, 625844478, 630552963, 891658882, 671071239, 13213703, 306543283, 919629849, 443562841, 330688516, 524261693, 572785072, 359360110, 78080323, 611882307, 835646914, 581550102, 744650299, 622474290, 867422863, 433380152, 300140449, 207633843, 622901529, 333853911, 1561726, 186415406, 559246218, 671669224, 15007658, 873208287, 619624847, 607626433, 822879292, 147337256, 442011768, 464949191, 394847566, 394102308, 182306917, 712263588, 136790750, 435351280, 306053833, 572434456, 717303361, 600067771, 800203306, 555571946, 666715831, 244396913, 733190739, 340354394, 21063175, 241003734, 723011202, 225704701, 677114103, 687994440, 63983306, 824461732, 473385182, 670919496, 12758474, 270611390, 811834170, 260075862, 780227586, 476905113, 430715332, 557838308, 673514917, 585391780, 756175333, 446567711, 339703126, 938945364, 816836078, 447833005, 343499008, 809822665, 429467981, 54579461, 163738383, 670188206, 10564604, 944604963, 833814875, 742926336, 228778994, 524284953, 572854852, 20361038, 61083114, 100122111, 300366333, 143197059, 429591177, 542205770, 626617303, 159440538, 478321614, 580457459, 741372370, 995544321, 986632949, 556332035, 668996098, 689371714, 68115128, 511395045, 534185128, 879914205, 639742601, 850993920, 552981746, 34605037, 103815111, 2443575, 7330725, 37699796, 113099388, 671664291, 14992859, 973214276, 919642814, 933623885, 800871641, 377150862, 131452579, 316655258, 949965774, 900869301, 702607889, 890824481, 672473429, 665901252, 997703749, 713966894, 141900668, 980749809, 942249413, 435930143, 307790422, 270202322, 810606966, 523239146, 569717431, 616137579, 848412730, 178657568, 535972704, 638323234, 914969695, 105538021, 316614063, 942887744, 828663218, 511574244, 534722725, 173450557, 520351671, 544992295, 634976878, 122291289, 366873867, 530654091, 591962266, 70388834, 211166502, 100925453, 302776359, 822855076, 468565214, 483470121, 450410356, 663919150, 991757443, 471955332, 415865989, 437175864, 311527585, 67712301, 203136903, 582810374, 748431115, 584135771, 752407306, 271745955, 815237865, 98874886, 296624658, 268632816, 805898448, 850309729, 550929173, 127686559, 383059677, 851364960, 554094866, 348255, 1044765, 269422265, 808266795, 607180854, 821542555, 65188846, 195566538, 272640573, 817921719, 13888949, 41666847, 193824497, 581473491, 984668687, 954006047, 326179638, 978538914, 733352424, 200057258, 560662931, 681988786, 480903100, 442709293, 184908703, 554726109, 781135437, 343406297, 890831907, 672495707, 225338450, 676015350, 236353314, 709059942, 174883162, 524649486, 964926773, 894780305, 541773554, 625320655, 766232673, 298698005, 623416271, 870248806, 841455083, 524365235, 291814419, 875443257, 880456884, 641370638, 677186250, 31558736, 721680001, 165039989, 628514984, 885544945, 699768375, 99305111, 70787814, 212363442, 16768343, 50305029, 981411218, 944233640, 721034022, 163102052, 888889446, 666668324, 34478203, 103434609, 91809171, 275427513, 132052666, 396157998, 564796816, 694390441, 597364331, 792092986, 620820425, 862461268, 87980494, 263941482, 13459819, 40379457, 118411106, 355233318, 994188752, 982566242, 549373628, 648120877, 855263896, 565791674, 587040543, 761121622, 878965676, 636897014, 909405573, 728216705, 521545518, 564636547, 983935198, 951805580, 442967588, 328902757, 124176800, 372530400, 719607081, 158821229, 919598558, 758795660, 958624279, 875872823, 259971801, 779915403, 364006576, 92019721, 81638940, 244916820, 881948500, 645845486, 164356219, 493068657, 892403018, 677209040, 15751410, 47254230, 732350267, 197050787, 124143910, 372431730, 120868343, 362605029, 470697309, 412091920, 418456628, 255369877, 721837933, 165513785, 131787457, 395362371, 615290676, 845872021, 296616785, 889850355, 433478574, 300435715, 121445324, 364335972, 307445422, 922336266, 765876155, 297628451, 255709935, 767129805, 519088440, 557265313, 564236602, 692709799, 960671678, 882015020, 735518476, 206555414, 599209567, 797628694, 557572857, 672718564, 415699524, 247098565, 830986095, 492958271, 166082805, 498248415, 548807313, 646421932, 698912853, 96738545, 1203486, 3610458, 483319001, 449956996, 916734995, 750204971, 995718206, 987154604, 220946658, 662839974, 891588854, 674766548, 713537726, 140613164, 964019162, 892057472, 177835762, 533507286, 632260765, 896782288, 874841213, 624523625, 715439857, 146319557, 877819776, 633459314, 303782966, 911348898, 574731937, 724195804, 520037160, 560111473, 961332034, 883996088, 46361894, 139085682, 603748154, 811244455, 242032994, 726098982, 838520619, 515561843, 633560523, 900681562, 925931663, 777794975, 853236234, 559708688, 766327026, 298981064, 420635665, 261906988, 559263573, 677790712, 380710347, 142131034, 156486715, 469460145, 353019488, 59058457, 427679937, 283039804, 163808941, 491426823, 569004985, 707014948, 740624640, 221873906, 761449487, 284348447, 153088784, 459266352, 817604074, 452812208, 649429345, 948288028, 619804438, 859413307, 390610883, 171832642, 70210147, 210630441, 35338139, 106014417, 949784712, 849354122, 173843517, 521530551, 595160318, 785480947, 691218962, 73656872, 577791553, 733374652, 224010424, 672031272, 81598614, 244795842, 926743650, 780230936, 818209235, 454627691, 298139513, 894418539, 666822750, 468236, 444066196, 332198581, 547314114, 641942335, 208627720, 625883160, 425371600, 276114793, 873892610, 621677816, 744569968, 233709890, 115990032, 347970096, 764436466, 293309384, 897170619, 691511843, 679087581, 37262729, 331042598, 993127794, 996965065, 990895181, 194981707, 584945121, 302963617, 908890851, 539529748, 618589237, 833806058, 501418160, 60569782, 181709346, 761674190, 285022556, 328743872, 986231616, 626635201, 879905596, 258686404, 776059212, 536576240, 609728713, 823002143, 469006415, 243566483, 730699449, 763191743, 289575215, 82105646, 246316938, 89637426, 268912278, 440066324, 320198965, 896424420, 689273246, 956747117, 870241337, 269294268, 807882804, 76002121, 228006363, 757730342, 273191012, 604557296, 813671881, 166560632, 499681896, 557966199, 673898590, 376689844, 130069525, 983952921, 951858749, 235954006, 707862018, 695102097, 85306277, 70026898, 210080694, 928265868, 784797590, 898225219, 694675643, 340647693, 21943072, 382237149, 146711440, 442047482, 326142439, 887317833, 661953485, 154321726, 462965178, 567869693, 703609072, 901194636, 703583894, 637644928, 912934777, 768905440, 306716306, 660341425, 981024268, 823924512, 471773522, 520340046, 561020131, 730887538, 192662600, 679681441, 39044309, 390581963, 171745882, 513035629, 539106880, 27073741, 81221223, 432779644, 298338925, 389260783, 167782342, 715343947, 146031827, 669195865, 7587581, 521833226, 565499671, 931623946, 794871824, 404650047, 213950134, 810455432, 431366282, 318218, 954654, 267559159, 802677477, 157271473, 471814419, 648768942, 946306819, 999950873, 999852605, 90387710, 271163130, 21390188, 64170564, 375087974, 125263915, 598406978, 795220927, 185803054, 557409162, 484733001, 454198996, 768715562, 306146672, 968179222, 904537652, 442103815, 326311438, 790924458, 372773360, 725064852, 175194542, 762130393, 286391165, 988723450, 966170336, 13488818, 40466454, 126850681, 380552043, 717670435, 153011291, 505842786, 517528351, 761508121, 284524349, 214019555, 642058665, 128241222, 384723666, 546475398, 639426187, 39543766, 118631298, 633338431, 900015286, 217083499, 651250497, 417234126, 251702371, 116078606, 348235818, 455795456, 367386361, 442120528, 326361577, 115042202, 345126606, 296065552, 888196656, 76644766, 229934298, 931069128, 793207370, 269134578, 807403734, 818342652, 455027942, 671357565, 14072681, 77628032, 232884096, 981639958, 944919860, 972615652, 917846942, 860747822, 582243452, 199934474, 599803422, 816374943, 449124815, 880484938, 641454800, 75277586, 225832758, 696706016, 90118034, 671464403, 14393195, 689646853, 68940545, 996211656, 988634954, 125070918, 375212754, 916081470, 748244396, 336864182, 10592539, 828018071, 484054199, 482702321, 448106956, 204715933, 614147799, 989829168, 969487490, 678738460, 36215366, 755414017, 266242037, 587685426, 763056271, 900865361, 702596069, 923216786, 769650344, 783100679, 349302023, 687050692, 61152062, 409074493, 227223472, 925328064, 775984178, 653362314, 960086935, 667139044, 1417118, 344831985, 34495948, 286295295, 858885885, 92185458, 276556374, 858207746, 574623224, 38700195, 116100585, 340213529, 20640580, 878409396, 635228174, 629667694, 889003075, 612001554, 836004655, 71076081, 213228243, 926662207, 779986607, 745924377, 237773117, 502927810, 508783423, 981269218, 943807640, 729652933, 188958785, 37910992, 113732976, 660741956, 982225861, 532465428, 597396277, 975474096, 926422274, 955136576, 865409714, 157471732, 472415196, 91538223, 274614669, 308489801, 925469403, 307083371, 921250113, 982364699, 947094083, 317900545, 953701635, 477418250, 432254743, 232969287, 698907861, 430682784, 292048345, 584850804, 754552405, 59870143, 179610429, 484786779, 454360330, 265806462, 797419386, 786335925, 359007761, 220595448, 661786344, 330429889, 991289667, 157648010, 472944030, 650771322, 952313959, 931533165, 794599481, 117917081, 353751243, 330913773, 992741319, 353853465, 61560388, 982827181, 948481529, 633248474, 899745415, 219445020, 658335060, 148296903, 444890709, 716375858, 149127560, 784293320, 352879946, 82440329, 247320987, 31397222, 94191666, 687760015, 63280031, 974434801, 923304389, 293305860, 879917580, 619680403, 859041202, 62114861, 186344583, 632839161, 898517476, 121677531, 365032593, 152726337, 458179011, 601502246, 804506731, 764440643, 293321915, 508320332, 524960989, 317043344, 951130032, 448986483, 346959442, 565580241, 696740716, 11627769, 34883307, 747822098, 243466280, 930832344, 792497018, 472310544, 416931625, 971866803, 915600395, 630935332, 892805989, 293812, 881436, 922656044, 767968118, 27316412, 81949236, 819339069, 458017193, 292822571, 878467713, 655002924, 965008765, 6773224, 20319672, 107921172, 323763516, 354954768, 64864297, 234070597, 702211791, 151520516, 454561548, 967945804, 903837398, 497517689, 492553060, 399526969, 198580900, 303765853, 911297559, 372251193, 116753572, 348996215, 46988638, 623853205, 871559608, 834368680, 503106026, 555236333, 665708992, 223626891, 670880673, 214274209, 642822627, 136179720, 408539160, 380654582, 141963739, 34697624, 104092872, 702815019, 108445043, 468190970, 404572903, 821303230, 463909676, 103581038, 310743114, 367537131, 102611386, 286049064, 858147192, 718507669, 155522993, 448921932, 346765789, 962306215, 886918631, 400365351, 201096046, 612811716, 838435141, 240257855, 720773565, 552695343, 658086022, 624794931, 874384786, 101440264, 304320792, 665967007, 997901014, 280578193, 841734579, 819300695, 457902071, 295699281, 887097843, 255106672, 765320016, 526361586, 579084751, 250407347, 751222041, 685042299, 55126883, 46635919, 139907757, 890130570, 670391696, 231298764, 693896292, 447016599, 341049790, 557993091, 673979266, 571909173, 715727512, 489953197, 469859584, 499932405, 499797208, 615580592, 846741769, 164523253, 493569759, 278636374, 835909122, 522921413, 568764232, 491092336, 473277001, 606891385, 820674148, 913152764, 739458278, 690404126, 71212364, 388965917, 166897744, 379155746, 137467231, 425561015, 276683038, 942633621, 827900849, 370590171, 111770506, 462075606, 386226811, 957438126, 872314364, 163664056, 490992168, 848860871, 546582599, 323015494, 969046482, 566766505, 700299508, 699834328, 99502970, 115049299, 345147897, 927399644, 782198918, 449930777, 349792324, 426760037, 280280104, 772012278, 316036820, 674613446, 23840324, 219497148, 658491444, 713210548, 139631630, 402120770, 206362303, 41793390, 125380170, 486851282, 460553839, 139708331, 419124993, 329003325, 987009975, 324032646, 972097938, 745844605, 237533801, 14485579, 43456737, 116493743, 349481229, 616755463, 850266382, 770748289, 312244853, 833075745, 499227221, 722531167, 167593487, 921759452, 765278342, 198225518, 594676554, 551078231, 653234686, 241159465, 723478395, 198754784, 596264352, 424812284, 274436845, 428594728, 285784177, 25357286, 76071858, 444379080, 333137233, 822997032, 468991082, 242714331, 728142993, 586776200, 760328593, 356064365, 68193088, 623066786, 869200351, 668829407, 6488207, 600742172, 802226509, 843829465, 531488381, 817971988, 453915950, 169777416, 509332248, 91876016, 275628048, 529076152, 587228449, 79744274, 239232822, 788595391, 365786159, 769823313, 309469925, 600798982, 802396939, 198800792, 596402376, 116419188, 349257564, 516437333, 549311992, 47060050, 141180150, 800696631, 402089879, 99396512, 298189536, 609650579, 828951730, 103717269, 311151807, 585879014, 757637035, 511403726, 534211171, 336769282, 10307839, 407681374, 223044115, 207486170, 622458510, 250947705, 752843115, 322605421, 967816263, 107910200, 323730600, 155994098, 467982294, 618643304, 855929905, 910537522, 731612552, 61901079, 185703237, 988363671, 965090999, 776215577, 328646717, 832790684, 498372038, 790437339, 371312003, 888192807, 664578407, 464677206, 394031611, 357243195, 71729578, 485881095, 457643278, 442022248, 326066737, 114960045, 344880135, 415733128, 247199377, 278866844, 836600532, 605580355, 816741058, 747396347, 242189027, 365177790, 95533363, 798021850, 394065536, 585004292, 755012869, 258041166, 774123498, 101816614, 305449842, 796403234, 389209688, 400151648, 200454937, 977402014, 932206028, 149987045, 449961135, 351316941, 53950816, 237883211, 713649633, 625408727, 876226174, 55308103, 165924309, 102958639, 308875917, 217177754, 651533262, 938230353, 814691045, 666275068, 998825197, 395953000, 187858993, 157894524, 473683572, 949241668, 847724990, 317957489, 953872467, 464908071, 394724206, 671827116, 15481334, 463931834, 391795495, 21919315, 65757945, 565754308, 697262917, 401925433, 205776292, 340518254, 21554755, 558481972, 675445909, 895218926, 685656764, 332674004, 998022012, 46070265, 138210795, 850411330, 551233976, 454956792, 364870369, 869185335, 607555991, 782280787, 346842347, 884469522, 653408552, 681910229, 45730673, 900559799, 701679383, 501934332, 505802989, 154692431, 464077293, 484986860, 454960573, 649404160, 948212473, 406539419, 219618250, 48684217, 146052651, 484571401, 453714196, 468884943, 406654822, 447909667, 343728994, 439987478, 319962427, 951050323, 853150955, 732706048, 198118130, 599653230, 798959683, 503969593, 511908772, 11471713, 34415139, 404552444, 213657325, 382711798, 148135387, 945519733, 836559185, 689586451, 68759339, 612069433, 836208292, 933197405, 799592201, 586710856, 760132561, 111411222, 334233666, 853535482, 560606432, 117044819, 351134457, 14495449, 43486347, 75377738, 226133214, 718121602, 154364792, 483304365, 449913088, 629459395, 888378178, 268836752, 806510256, 427201231, 281603686, 912864736, 738594194, 158405899, 475217697, 993962141, 981886409, 216293321, 648879963, 941730943, 825192815, 859869335, 579607991, 428710250, 286130743, 612916968, 838750897, 433292718, 299878147, 624996426, 874989271, 334732774, 4198315, 950615840, 851847506, 756553223, 269659655, 81084707, 243254121, 433216326, 299648971, 98477543, 295432629, 6822271, 20466813, 477211427, 431634274, 299371935, 898115805, 365979386, 97938151, 369059472, 107178409, 966303297, 898909877, 962678129, 888034373, 420536785, 261610348, 24173439, 72520317, 331262975, 993788925, 39729106, 119187318, 265689129, 797067387, 760811631, 282434879, 342358863, 27076582, 777607979, 332823923, 115407837, 346223511, 205172789, 615518367, 529374054, 588122155, 130890683, 392672049, 213571799, 640715397, 397986457, 193959364, 505435702, 516307099, 218414795, 655244385, 754867614, 264602828, 941241580, 823724726, 107657484, 322972452, 992925649, 978776933, 675139803, 25419395, 659501341, 978504016, 732416745, 197250221, 340721736, 22165201, 912129750, 736389236, 415079112, 245237329, 471318825, 413956468, 531736532, 595209589, 919159814, 757479428, 230641731, 691925193, 807143336, 421429994, 882529591, 647588759, 735321377, 205964117, 580604100, 741812293, 316595998, 949787994, 536692569, 610077700, 236285545, 708856635, 787558768, 362676290, 97323945, 291971835, 520248177, 560744524, 848434847, 545304527, 565309929, 695929780, 734801499, 204404483, 223891430, 671674290, 974984829, 924954473, 415858081, 247574236, 494967892, 484903669, 471036301, 413108896, 552967500, 658902493, 568035035, 704105098, 666413452, 999240349, 579023539, 737070610, 58949606, 176848818, 705674617, 117023837, 744503088, 233509250, 977839776, 933519314, 238350650, 715051950, 367253821, 101761456, 739959063, 219877175, 247009672, 741029016, 14947155, 44841465, 824822589, 474467753, 989068352, 967205042, 625870508, 877611517, 743058190, 229174556, 729204383, 187613135, 497943673, 493831012, 362743619, 88230850, 21498447, 64495341, 114876764, 344630292, 586513501, 759540496, 646970980, 940912933, 458377373, 375132112, 658464725, 975394168, 270965734, 812897202, 859291237, 577873697, 28142965, 84428895, 58645674, 175937022, 148958208, 446874624, 6159274, 18477822, 434954983, 304864942, 776375083, 329125235, 745627654, 236882948, 784565286, 353695844, 760057113, 280171325, 487150068, 461450197, 901664003, 704991995, 405754322, 217262959, 866175723, 598527155, 524115619, 572346850, 81107603, 243322809, 148118030, 444354090, 451336801, 354010396, 602415618, 807246847, 326004915, 978014745, 718817299, 156451883, 826309494, 478928468, 879635379, 638906123, 972240866, 916722584, 269707243, 809121729, 918292660, 754877966, 565010094, 695030275, 501956375, 505869118, 230809700, 692429100, 260326983, 780980949, 950763298, 852289880, 888111237, 664333697, 397920913, 193762732, 296911099, 890733297, 618633182, 855899539, 683149783, 49449335, 563396619, 690189850, 802979013, 408937025, 570017475, 710052418, 142830659, 428491977, 674583778, 23751320, 166571542, 499714626, 673588788, 20766350, 936206462, 808619372, 951723550, 855170636, 333896505, 1689508, 161906021, 485718063, 919707633, 759122885, 130677509, 392032527, 578987986, 736963951, 555988826, 667966471, 628780431, 886341286, 106000262, 318000786, 613519729, 840559180, 172602117, 517806351, 739185637, 217556897, 977361219, 932083643, 5715019, 17145057, 599816662, 799449979, 756707668, 270122990, 399470178, 198410527, 491605365, 474816088, 876491896, 629475674, 398426524, 195279565, 119943960, 359831880, 878632554, 635897648, 227954077, 683862231, 139720499, 419161497, 600243836, 800731501, 459568150, 378704443, 323701949, 971105847, 628879756, 886639261, 752319850, 256959536, 405477706, 216433111, 338994190, 16982563, 6665119, 19995357, 505383342, 516150019, 605569489, 816708460, 790166034, 370498088, 262028838, 786086514, 324637079, 973911237, 15900333, 47700999, 114226952, 342680856, 401494436, 204483301, 271563645, 814690935, 394210782, 182632339, 882503162, 647509472, 983746368, 951239090, 521968240, 565904713, 696483074, 89449208, 441433497, 324300484, 578473629, 735420880, 282684295, 848052885, 891748602, 675245792, 345924031, 37772086, 161458229, 484374687, 309091782, 927275346, 540822734, 622468195, 985376268, 956128790, 163492358, 490477074, 262238181, 786714543, 279075512, 837226536, 990898827, 972696467, 476350727, 429052174, 236244668, 708734004, 652649509, 957948520, 314096281, 942288843, 614221035, 842663098, 93971343, 281914029, 389304810, 167914423, 838903656, 516710954, 840253579, 520760723, 727729623, 183188855, 808864292, 426592862, 852598350, 557795036, 78886616, 236659848, 719856282, 159568832, 649390315, 948170938, 357253777, 71761324, 712227897, 136683677, 157392528, 472177584, 484825467, 454476394, 385361191, 156083566, 364714728, 94144177, 917302839, 751908503, 144164486, 432493458, 399672308, 199016917, 606493354, 819480055, 525948417, 577845244, 998160845, 994482521, 537114078, 611342227, 207289241, 621867723, 279326042, 837978126, 377190994, 131572975, 611726706, 835180111, 612887159, 838661470, 934198953, 802596845, 893448111, 680344319, 935307585, 805922741, 827924001, 483771989, 921401786, 764205344, 40107437, 120322311, 284972607, 854917821, 681149134, 43447388, 959926660, 879779966, 363531862, 90595579, 778420256, 335260754, 563996258, 691988767, 74403567, 223210701, 353242207, 59726614, 697270103, 91810295, 853264292, 559792862, 688777822, 66333452, 752720748, 258162230, 988381369, 965144093, 543349773, 630049312, 618338055, 855014158, 970053274, 910159808, 78198444, 234595332, 959189446, 877568324, 249502295, 748506885, 868275249, 604825733, 992850760, 978552266, 937294763, 811884275, 883614797, 650844377, 793509679, 380529023, 21018043, 63054129, 108447321, 325341963, 553652665, 660957988, 408025204, 224075605, 160789449, 482368347, 686566238, 59698700, 27042530, 81127590, 853294858, 559884560, 40763718, 122291154, 582430274, 747290815, 727482380, 182447126, 754932711, 264798119, 763251908, 289755710, 794349080, 383047226, 410292426, 230877271, 972642207, 917926607, 576697833, 730093492, 266649903, 799949709, 341107045, 23321128, 17721901, 53165703, 131403861, 394211583, 353693661, 61080976, 585570659, 756711970, 165667284, 497001852, 224528235, 673584705, 494154422, 482463259, 553587093, 660761272, 231053899, 693161697, 259324778, 777974334, 909081460, 727244366, 704456038, 113368100, 682238423, 46715255, 921483856, 764451554, 609357333, 828071992, 807332695, 421998071, 382973555, 148920658, 537691110, 613073323, 556998478, 670995427, 779895808, 339687410, 384677966, 154033891, 152676640, 458029920, 640038717, 920116144, 8174344, 24523032, 3481811, 10445433, 718167265, 154501781, 851287563, 553862675, 225734085, 677202255, 901652528, 704957570, 573116233, 719348692, 800822372, 402467102, 377446837, 132340504, 724430894, 173292668, 270866345, 812599035, 976456407, 929369207, 902690060, 708070166, 963988264, 891964778, 617889211, 853667626, 780777352, 342332042, 796306529, 388919573, 13000519, 39001557, 528500497, 585501484, 744937562, 234812672, 572082820, 716248453, 9974150, 29922450, 447180938, 341542807, 268816681, 806450043, 851088345, 553265021, 358522822, 75568459, 329602933, 988808799, 298251037, 894753111, 575383600, 726150793, 849908330, 549724976, 15124361, 45373083, 289793505, 869380515, 210602569, 631807707, 789094671, 367283999, 785788580, 357365726, 217230948, 651692844, 561133836, 683401501, 289003730, 867011190, 747366459, 242099363, 565782012, 697346029, 780593475, 341780411, 465019637, 395058904, 164410293, 493230879, 351254710, 53764123, 542963317, 628889944, 529629102, 588887299, 887955493, 663866465, 733417719, 200253143, 332446755, 997340265, 184732397, 554197191, 208819864, 626459592, 948056494, 844169468, 840197666, 520592984, 879911992, 639735962, 589591115, 768773338, 13596741, 40790223, 583344971, 750034906, 188234282, 564702846, 516655626, 549966871, 643857532, 931572589, 875950290, 627850856, 810555474, 431666408, 225396810, 676190430, 641521795, 924565378, 885041910, 655125716, 845759377, 537278117, 436228396, 308685181, 989906191, 969718559, 812362789, 437088353, 883632749, 650898233, 79470918, 238412754, 824709448, 474128330, 760937760, 282813266, 374341087, 123023254, 506691761, 520075276, 394357073, 183071212, 264812422, 794437266, 259471858, 778415574, 75343423, 226030269, 378596105, 135788308, 503371285, 510113848, 775018136, 325054394, 180299147, 540897441, 103585687, 310757061, 499339504, 498018505, 430047139, 290141410, 585230254, 755690755, 863763596, 591290774, 41809524, 125428572, 624512053, 873536152, 378947286, 136841851, 49078270, 147234810, 744955099, 234865283, 642010542, 926031619, 354821114, 64463335, 376241594, 128724775, 863563465, 590690381, 161166511, 483499533, 846838028, 540514070, 412964270, 238892803, 640233792, 920701369, 834094183, 502282535, 654585554, 963756655, 235908691, 707726073, 966070969, 898212893, 695145078, 85435220, 838821349, 516464033, 546959346, 640878031, 592337655, 777012958, 346054017, 38162044, 294634628, 883903884, 744168699, 232506083, 325659950, 976979850, 408307040, 224921113, 525645031, 576935086, 834446447, 503339327, 529318429, 587955280, 754750813, 264252425, 997563696, 992691074, 733777317, 201331937, 339987512, 19962529, 474857053, 424571152, 362953016, 88859041, 263847717, 791543151, 608012633, 824037892, 457315520, 371946553, 590663190, 771989563, 257937936, 773813808, 681358272, 44074802, 744146644, 232439918, 592994073, 778982212, 632811145, 898433428, 983970103, 951910295, 760193602, 280580792, 94176858, 282530574, 265973868, 797921604, 7689419, 23068257, 379446974, 138340915, 562552571, 687657706, 182191319, 546573957, 778808720, 336426146, 441385469, 324156400, 872240522, 616721552, 270947494, 812842482, 9700807, 29102421, 44478204, 133434612, 590159696, 770479081, 278883171, 836649513, 917551271, 752653799, 479010966, 437032891, 323389506, 970168518, 923384119, 770152343, 156043937, 468131811, 386086325, 158258968, 98045036, 294135108, 506444545, 519333628, 324851475, 974554425, 977682411, 933047219, 562556768, 687670297, 539079786, 617239351, 819791630, 459374876, 134899816, 404699448, 193085808, 579257424, 981522703, 944568095, 830407759, 491223263, 488630231, 465890686, 543918909, 631756720, 796822921, 390468749, 3695898, 11087694, 900011636, 700034894, 699695457, 99086357, 438161208, 314483617, 492416906, 477250711, 843140801, 529422389, 629404562, 888213679, 25808499, 77425497, 729779906, 189339704, 170242583, 510727749, 435118255, 305354758, 199661295, 598983885, 957429903, 872289695, 801918862, 405756572, 606741840, 820225513, 318333821, 955001463, 879438131, 638314379, 68646018, 205938054, 640639587, 921918754, 283918858, 851756574, 167493237, 502479711, 655184883, 965554642, 576972247, 730916734, 345729096, 37187281, 848195673, 544587005, 189473286, 568419858, 648033014, 944099035, 347166262, 41498779, 392363656, 177090961, 452041289, 356123860, 152973633, 458920899, 20312106, 60936318, 480057063, 440171182, 873589357, 620768057, 916877063, 750631175, 232096239, 696288717, 951552408, 854657210, 912274381, 736823129, 382502455, 147507358, 970524885, 911574641, 582837023, 748511062, 74369526, 223108578, 938541823, 815625455, 570030128, 710090377, 344623240, 33869713, 677856204, 33568598, 464197517, 392592544, 165953935, 497861805, 3749093, 11247279, 570925441, 712776316, 662166575, 986499718, 310596741, 931790223, 717675709, 153027113, 312568302, 937704906, 130507013, 391521039, 699492569, 98477693, 138895061, 416685183, 541619196, 624857581, 994495982, 983487932, 250343003, 751029009, 863184545, 589553621, 984075563, 952226675, 894943693, 684831065, 600801532, 802404589, 940512415, 821537231, 262523331, 787569993, 36703647, 110110941, 894583928, 683751770, 505500536, 516501601, 568550228, 705650677, 160783396, 482350188, 588443103, 765329302, 640500262, 921500779, 781824234, 345472688, 448099935, 344299798, 658282180, 974846533, 412793052, 238379149, 329076388, 987229164, 904345139, 713035403, 125154502, 375463506, 696082636, 88247894, 772243692, 316731062, 778134161, 334402469, 112856181, 338568543, 440664992, 321994969, 396399680, 189199033, 111272159, 333816477, 727815291, 183445859, 58652859, 175958577, 92434809, 277304427, 142424018, 427272054, 893950653, 681851945, 862774311, 588322919, 833689517, 501068537, 567100932, 701302789, 608358868, 825076597, 163577098, 490731294, 315739721, 947219163, 641842894, 925528675, 915170002, 745509992, 528012841, 584038516, 86314945, 258944835, 346859995, 40579978, 101612819, 304838457, 407544897, 222634684, 941552603, 824657795, 931261859, 793785563, 65294597, 195883791, 366433658, 99300967, 313880454, 941641362, 932358823, 797076455, 948259485, 844778441, 161884732, 485654196, 134506022, 403518066, 965306083, 895918235, 614728407, 844185214, 736056887, 208170647, 743267673, 229803005, 736661834, 209985488, 566526407, 699579214, 723041561, 169124669, 510440532, 531321589, 118481469, 355444407, 354896784, 64690345, 284134347, 852403041, 513074675, 539224018, 69861117, 209583351, 23488062, 70464186, 755217383, 265652135, 929961229, 789883673, 271946276, 815838828, 228634389, 685903167, 617896185, 853688548, 196006084, 588018252, 966015888, 898047650, 71898364, 215695092, 106562595, 319687785, 962563356, 887690054, 776336879, 329010623, 673207831, 19623479, 635064240, 905192713, 77147583, 231442749, 807109810, 421329416, 461045338, 383136007, 665662662, 996987979, 862478753, 587436245, 185069797, 555209391, 144312693, 432938079, 100919860, 302759580, 835475323, 506425955, 18744716, 56234148, 303317336, 909952008, 70442890, 211328670, 64918290, 194754870, 333562088, 686257, 615371129, 846113380, 254233249, 762699747, 493224022, 479672059, 143670612, 431011836, 497840117, 493520344, 37615314, 112845942, 335061334, 5183995, 126830165, 380490495, 794487426, 383462264, 629338078, 888014227, 178270833, 534812499, 867779071, 603337199, 547409195, 642227578, 752845921, 258537749, 46530872, 139592616, 961015340, 883046006, 385179413, 155538232, 488980403, 466941202, 414002081, 242006236, 829733985, 489201941, 52682250, 158046750, 598776060, 796328173, 43209754, 129629262, 685251188, 55753550, 221046452, 663139356, 621575700, 864727093, 576869136, 730607401, 373607485, 120822448, 82575952, 247727856, 761377590, 284132756, 23691180, 71073540, 26983832, 80951496, 583453782, 750361339, 345212001, 35635996, 179567851, 538703553, 18636717, 55910151, 200687345, 602062035, 204593688, 613781064, 244467894, 733403682, 462448324, 387344965, 344397544, 33192625, 351871624, 55614865, 383469758, 150409267, 6986226, 20958678, 831948315, 495844931, 558112638, 674337907, 938411705, 815235101, 178097373, 534292119, 216677786, 650033358, 785098387, 355295147, 552695927, 658087774, 910274985, 730824941, 46178842, 138536526, 343436631, 30309886, 53483591, 160450773, 209563553, 628690659, 457101191, 371303566, 387394951, 162184846, 206945094, 620835282, 558918515, 676755538, 166834550, 500503650, 929423439, 788270303, 115049344, 345148032, 140505878, 421517634, 831589566, 494768684, 408309793, 224929372, 74459294, 223377882, 364758330, 94274983, 999557810, 998673416, 75080495, 225241485, 307823888, 923471664, 114474493, 343423479, 845169521, 535508549, 569804225, 709412668, 758929285, 276787841, 196518523, 589555569, 894126511, 682379519, 106526792, 319580376, 918482155, 755446451, 122918323, 368754969, 317965103, 953895309, 959086561, 877259669, 778238766, 334716284, 690370558, 71111660, 995834419, 987503243, 185861235, 557583705, 98569232, 295707696, 623351677, 870055024, 327853317, 983559951, 702349152, 107047442, 627405997, 882217984, 469693222, 409079659, 532114441]
    
    # dp[i][j][k] := i 文字目まで見て、j 文字できてて、k 文字は余計に打ってて後で消す
    N = int(input())
    S = input()
    J = len(S)
    
    half = N//2+1
    L = np.array(B[:half*2], dtype=np.int64)
    step = 2
    J_ = J
    while J_:
        if J_%2:
            if (N-J)%2==0:
                L[::2] = convolve_mod(L[::2], A)[:half]
            else:
                L[1::2] = convolve_mod(L[1::2], A)[:half]
            L %= mod
        J_ //= 2
        A = convolve_mod(A, A)[:half*2] % mod
    print(L[N-J])

main()