독립 집합

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}^0$, $x_1 + x_2 + \dots + x_n = m$;
2. 모든 $1 \leq i \leq n$에 대해 $a_i \cdot x_i = 0$;
3. 모든 $2 \leq i \leq n$에 대해 $x_{\lfloor i / 2 \rfloor} \cdot x_i = 0$.

첫째 줄에 정수 $n, m$이 주어진다 ($1 \leq n \leq 5000000, 1 \leq m \leq 10$).

둘째 줄에 $n$개의 정수 $a_1 a_2 \dots a_n$이 주어진다 ($0 \leq a_i \leq 1$).

수열의 개수를 출력한다.