You are given a binary string *s* (each character of this string is either 0 or 1).

Let's denote the cost of string *t* as the number of occurences of *s* in *t*. For example, if *s* is 11 and *t* is 111011, then the cost of *t* is 3.

Let's also denote the Fibonacci strings sequence as follows:
-  *F*(0) is 0;-  *F*(1) is 1;-  *F*(*i*) = *F*(*i* - 1) + *F*(*i* - 2) if *i* &gt; 1, where  +  means the concatenation of two strings.
Your task is to calculate the sum of costs of all subsequences of the string *F*(*x*). Since answer may be large, calculate it modulo 10<sup class="upper-index">9</sup> + 7.
The first line contains two integers *n* and *x* (1 ≤ *n* ≤ 100, 0 ≤ *x* ≤ 100) — the length of *s* and the index of a Fibonacci string you are interested in, respectively.

The second line contains *s* — a string consisting of *n* characters. Each of these characters is either 0 or 1.
none
2 4
11
14
10 100
1010101010
553403224
10 5
0110111100
0
100 100
0001010101110010010100111011010101101111110001101101010111011101010000111000110001111010001001000001
365717046
50 50
00011100010110111111011100101010000001101001001001
211494411
100 50
0110110011111110010000000101010110011001011100000010110100110000000111001011011010110111000010000001
355763668
50 100
11001000000100001111111111100011011110001000110101
225470550
10 5
0110010110
0
100 100
0001000111111101010001010000110001001000011010001001110000110001001010110010101101010001101110100100
399119859
50 50
01011000110110000111110010001111101100010111110000
714948296
100 50
0110101011101001010110011110010001101110110111100101000111001111011101110001000010011111010001100101
848198292
50 100
00000110100111111010111000110011110111010110010101
479111747
10 5
0001000110
0
100 100
0011111110011110110011101011100011101101000100001111000001011011110000011110100111011001111111100100
890610403
50 50
01001010111011110110111100110111010101011101010100
681685300
100 50
0000000000000110011010100101101011000010001001100001100010101101110011011000011000010110100110011101
887847887
50 100
00010100101010011011010110000111010110011101101100
114941842
10 5
0001111100
0
100 100
0110100100001000110111110000100100011011101101101111100010100100011110100100011100000000101000010000
313325649
50 50
01100100001000001111000111100111011110101010001101
296269628
100 50
0001010000010001111100011010101001100101000000000001100001000001001001110010000001011110100101011001
178648298
50 100
00110000001011100010011100111100001111101011101111
769038034
10 5
1001100101
0
100 100
0100001100000111000001001100001110010110010011101010000101000010100100001111000100101000001011111100
923483202
50 50
00100010000101111110000001011010100111110000101100
409708636
100 50
0001001010110010101101010001101110100100111010000101010110101111111001101100011011110101010000111101
404698837
50 100
01101110010011010010101010001100100100110000000110
858303348
10 5
1110010111
0
100 100
0101011110100000000100110111001100110011111001001110010110001100011110101011011110101001011100011101
807081430
50 50
00111110100101010010101111101000000111011111000101
619349549
100 50
0110110000110101001011101000011100000000010100000011110101001001010111001100000011101101000011011100
883337527
50 100
01101000110100101011100101111101001001011010110110
815093980
10 5
1110011111
0
100 100
0001100111110111101110111100011011010001100100001100110101100010111000010001000110100111000101111001
302237139
50 50
00011000010100100011000001011001101110000101010101
740098237
100 50
0110100001101010001101010011011000101111101101100010010110110111101101100111011001001000011100100000
530774696
50 100
01000100110101011110001011000001110000000100011111
138545018
10 5
1110000101
0
100 100
0011111101010100101010000111111001110100001110101000011000000110100010011011011100001110100010001101
860040906
50 50
01000010011011011010010110100001010001011010110100
707347275
100 50
0110011011001101101000001100011011011010100011100110000011011000110111011011100011000000111111000100
66265147
50 100
00010110001100100111100101110001010001110111001110
352965752
10 5
1001111110
0
100 100
0110001111011011111100111000111111011011110101101100101011111000011000110010000110000111110001000101
893503058
50 50
01000110111010101011111100010101111000111000001101
734862374
100 50
0001010011001110101110100111110101111100011000000010100000111110011001110001101010001001101010100000
299420410
50 100
00011000101000010101110111100000111011111001100110
470403317
10 5
1001111000
0
100 100
1001101110100101001011001111100101011111111000100010110101001101111010010000001011101000011000100011
867372444
50 50
10101100011100111101010100100111010000111101110110
841531413
100 50
1111000101010001011011110000101001110111101100010110101001000101010110000000110110111001011100010001
227967423
50 100
10111010110100011110011000100110011000001000011011
357273337
1 0
0
1
1 1
0
0
1 0
1
0
1 1
1
1
1 100
0
16747890
1 100
1
731582592
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * n + v

n, x = map(int, input().split())
mod = pow(10, 9) + 7
s = list(input().rstrip())
m = 105
inv2 = pow(2, mod - 2, mod)
fib = [1, 1]
p = [2, 2]
ip = [inv2, inv2]
for _ in range(m):
    fib.append((fib[-1] + fib[-2]) % mod)
    p.append(p[-1] * p[-2] % mod)
    ip.append(ip[-1] * ip[-2] % mod)
if n == 1:
    dp1, dp2 = [0] * (m + 1), [0] * (m + 1)
    dp1[0], dp2[1] = 1, 1
    for i in range(2, m + 1):
        dp1[i] = (dp1[i - 1] + dp1[i - 2]) % mod
        dp2[i] = (dp2[i - 1] + dp2[i - 2]) % mod
    u = dp1[x] if not s[0] & 1 else dp2[x]
    ans = u * p[x] % mod * inv2 % mod
    print(ans)
    exit()
elif fib[x] < n:
    ans = 0
    print(ans)
    exit()
dp1, dp2 = [0] * (n * n), [0] * (n * n)
dpp1, dpp2 = [0] * n, [0] * n
dps1, dps2 = [0] * n, [0] * n
for i in range(n):
    if not s[i] & 1:
        dp1[f(i, i)] = 1
    else:
        dp2[f(i, i)] = 1
if not s[0] & 1:
    dpp1[0] = inv2
else:
    dpp2[0] = inv2
if not s[-1] & 1:
    dps1[-1] = inv2
else:
    dps2[-1] = inv2
ans = 0
for u in range(2, x + 1):
    dp3 = [i + j for i, j in zip(dp1, dp2)]
    for i in range(n):
        for j in range(i, n):
            for k in range(j + 1, n):
                dp3[f(i, k)] += dp2[f(i, j)] * dp1[f(j + 1, k)] % mod
    c = fib[x - u]
    for i in range(n - 1):
        ans += dpp2[i] * dps1[i + 1] % mod * c % mod
    dpp3, dps3 = list(dpp2), list(dps1)
    for i in range(1, n):
        for j in range(i, n):
            dpp3[j] += dp1[f(i, j)] * dpp2[i - 1] % mod
    for i in range(n - 1):
        for j in range(i, n - 1):
            dps3[i] += dp2[f(i, j)] * dps1[j + 1] % mod
    dpp3 = [(dpp3[i] % mod * ip[u - 2] + dpp1[i]) % mod for i in range(n)]
    dps3 = [(dps3[i] % mod * ip[u - 1] + dps2[i]) % mod for i in range(n)]
    dp1 = dp2
    dp2 = [i % mod for i in dp3]
    dpp1, dps1 = dpp2, dps2
    dpp2, dps2 = dpp3, dps3
ans = ans % mod * p[x] % mod
print(ans)