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.