Independent Set

Time limit2sMemory limit512 MB

Summary

Count vectors of n nonnegative integers summing to m where positions flagged by a and parent-child pairs in the implicit binary heap cannot both be positive, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Tree, Combinatorics, Math
Solved: No attempts yet

Problem

Bobo has a binary sequence $a_1 a_2 \dots a_n$ . He wants to count the number of sequences $x_1, x_2, \dots, x_n$ satisfying the following conditions modulo $(10^9+7)$ .

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

Input

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$ ).

Output

A single number denotes the number of sequence.

Examples2

Example 1
Input
```
2 2
00
```
Expected output
```
2
```
Example 2
Input
```
10 3
0101010101
```
Expected output
```
26
```