Description

Let's keep the problem statement simple.

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

$\dagger$: Note that a subsequence does not need 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 Format

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

The second line contains a binary string $S$ of length $n + m$.

Output Format

Output a single integer, representing the result modulo $2933256077$.

2 1
000

3

5 5
0010111011

1391

Hint

Sample Explanation #1

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

Constraints

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

Subtasks are used in this task.

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