Counting Valid 01‐Substrings Partitions and Their Recursive Sums

We define a 01-string as a binary string that is valid if and only if its first character is 0 and its last character is 1. For any valid 01-string \(T\), let its weight \(f(T)\) be the number of ways to partition \(T\) into one or more contiguous substrings, each of which is a valid 01-string. For example, \(f(\mathtt{001}) = 1\) because the only valid partition is \([\mathtt{001}]\). Also, \(f(\mathtt{0101101}) = 4\) since it can be partitioned in the following four ways:

• [0101101] (the entire string is valid)
• [01, 01101]
• [01011, 01]
• [01, 011, 01]

If the string is not valid (for example, (\mathtt{1001010101})), we define (f(T)=0).

Now, given a binary string \(S\) of length \(n\) (which may or may not be a valid string) and a non-negative integer \(k\), we define a recursive function \(f_k(l, r)\) on the substring \(S_{l\dots r}\) (1-indexed) as follows:

[ f_k(l, r)=\begin{cases} f(S_{l\dots r}) & \text{if } k=0,\[8pt] \displaystyle \sum_{l \le l' \le r' \le r} f_{k-1}(l', r') & \text{if } k > 0. \end{cases} ]

Your task is to compute \(f_k(1, n)\) modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(k\) (with \(n\) being the length of the binary string and \(k \ge 0\)). The second line contains a binary string \(S\) of length \(n\), consisting only of characters 0 and 1.

outputFormat

Output one integer: the value of \(f_k(1, n)\) modulo \(10^9+7\).

sample

3 0
001

1