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
print("_RANDOM_GUESS_1690496282.6828997")# 1690496282.6829193