Flip

Program time limit: 1 second

Program memory limit: 512 MB

Given a bit string $S$ of length $n$, each second, you choose a range $(l, r)$ uniformly at random where $1 \leq l \leq r \leq n$, and flip all bits in $S$ from index $l$ to $r$ (inclusive).

After $m$ seconds, compute the expected number of $1$ bits in the bit string $S$.

This expected value can be represented as the the fraction in lowest term $\frac{p}{q}$ where $p$ and $q$ are coprime integers, write your answer in the form $p \cdot q^{-1} \mod 1\;000\;000\;007$.

Input

The first line contains two space seperated integers $n$ and $m$, the length of the bit string and the number of seconds.

The second line contains a bit string $S$ of length $n$ consisting of only $0$s and $1$s.

Constraints

For all test cases:

• $1 \leq n \leq 100\;000$.
• $1 \leq m \leq 1\;000\;000\;000$.

Output

Output a single integer representing the expected number of $1$ bits after $m$ seconds, modulo $1\;000\;000\;007$.

In Python, you could use the line print(answer).

In C or C++, you could use the line printf("%d\n", answer);.

Sample Input 1

1 1
0

Sample Output 1

1

Sample Input 2

4 5
0100

Sample Output 2

285760004

Explanation 1

There is only one bit in the string, and after one second, the bit is flipped from $0$ to $1$. Thus, the expected number of $1$ bits is $1$.

Scoring

Your program will be run on the 1 sample case and multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves the task. Recall that your final score on the task is the score of your highest scoring submission.

Submit

Past submissions

You haven't submitted to this task.