题目背景

English statement. You must submit your code at the Chinese version of the statement.

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

题目描述

题面还是简单一点好。

• 给定 $n, m$，以及一个长为 $n + m$ 的 $\tt{01}$ 串 $S$。
• 对于 $\tt 01$ 串 $T$，定义 $f(T)$ 为 $S$ 的最长的前缀的长度，使得该前缀是 $T$ 的子序列 $^\dagger$。
• 对于每个 恰包含 $\bm n$ 个 $\tt 1$ 和 $\bm m$ 个 $\tt 0$ 的 $\tt{01}$ 串 $T$，求 $f(T)$ 的和。答案对 $2933256077^\ddagger$ 取模。

$\dagger$：请注意，子序列可以不连续。换句话说，$a$ 是 $b$ 的子序列，当且仅当在 $b$ 中删去 $\geq 0$ 个字符后，可以得到 $a$。注意，空串总是任何串的子序列。

$\ddagger$：模数为质数。

输入格式

第一行包含两个整数 $n, m$。

第二行包含一个长度为 $n + m$ 的 $\tt 01$ 串 $S$。

输出格式

输出一行一个整数，表示答案对 $2933256077$ 取模后的结果。

2 1
000

3

5 5
0010111011

1391

提示

「样例解释 #1」

所有可能的序列有且仅有公共序列 $\texttt{0}$。因为恰有 $3$ 种不同的 $T$（$\tt 110, 101, 011$），所以答案为 $1\times 3 = 3$。

「数据范围」

对于所有测试数据，保证 $1 \leq n, m \leq 3\times 10^6$。

本题采用捆绑测试。

• 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）：无特殊限制。