19129번 - Independent Set 다국어

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.