In Memory of $\text{F}\rule{66.8px}{6.8px}$.

Let's keep the problem statement simple.

• Given $n, m$, and a $\tt{01}$ string $S$ of length $n + m$.
• For a $\tt{01}$ string $T$, define $f(T)$ as the length of the longest prefix of $S$ that is a subsequence $^\dagger$ of $T$.
• For every $\tt{01}$ string $T$ that contains exactly $n$ $\tt 1$s and $m$ $\tt 0$s, calculate the sum of $f(T)$. The answer should be taken modulo $2933256077^\ddagger$.

$\dagger$: Note that a subsequence does not have to be contiguous. In other words, $a$ is a subsequence of $b$ if and only if $a$ can be obtained by deleting $\geq 0$ characters from $b$. Note that the empty string is always a subsequence of any string.

$\ddagger$: The modulus is a prime number.

Input

The first line contains two integers $n, m$.

The second line contains a $\tt 01$ string $S$ of length $n + m$.

Output

Output a single integer representing the answer modulo $2933256077$.

Examples

Input 1

2 1
000

Output 1

3

Note

The only possible common subsequence is $\texttt{0}$. Since there are exactly $3$ different strings $T$ ($\tt 110, 101, 011$), the answer is $1 \times 3 = 3$.

Input 2

5 5
0010111011

Output 2

1391

Constraints

For all test cases, it is guaranteed that $1 \leq n, m \leq 3\times 10^6$.

This problem uses bundled testing.

• Subtask 1 (13 points): $\max(n, m) \leq 5$.
• Subtask 2 (13 points): $\max(n, m) \leq 100$.
• Subtask 3 (34 points): $\max(n, m) \leq 3 \times 10^3$.
• Subtask 4 (40 points): No additional restrictions.