시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 0 0 0.000%

문제

Bobo has a binary sequence $a_{1} a_2 \dots a_{n}$. And he wants to count the number of sequences as $x_1, x_2, \dots, x_n$ satisfying the following conditions modulo $(10^9+7)$.

  1. $x_1, x_2, \dots, x_n \in \mathbb{N}^0$, $x_1 + x_2 + \dots + x_n = m$;
  2. For all $1 \leq i \leq n$, $a_i \cdot x_i = 0$;
  3. For all $2 \leq i \leq n$, $x_{\lfloor i / 2 \rfloor} \cdot x_i = 0$.

입력

The first line contains $2$ integers $n, m$ ($1 \leq n \leq 5000000, 1 \leq m \leq 10$).

The second line contains $n$ integers $a_{1} a_{2} \dots a_{n}$ ($0 \leq a_i \leq 1$).

출력

A single number denotes the number of sequence.

예제 입력 1

2 2
00

예제 출력 1

2

예제 입력 2

10 3
0101010101

예제 출력 2

26