bobo 有一个二进制序列 $a_1 a_2 \dots a_n$。他想要计算满足以下条件的序列 $x_1, x_2, \dots, x_n$ 的数量，结果对 $(10^9 + 7)$ 取模：

1. $x_1, x_2, \dots, x_n \in \mathbb{N}$，$x_1 + x_2 + \dots + x_n = m$；
2. 对于所有 $1 \le i \le n$，$a_i \cdot x_i = 0$；
3. 对于所有 $2 \le i \le n$，$x_{\lfloor i/2 \rfloor} \cdot x_i = 0$。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 5000000, 1 \le m \le 10$)。 第二行包含 $n$ 个整数 $a_1 a_2 \dots a_n$ ($0 \le a_i \le 1$)。

输出格式

一个整数，表示满足条件的序列数量。

样例

样例输入 1

2 2
00

样例输出 1

2

样例输入 2

10 3
0101010101

样例输出 2

26