题目背景

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$。
• 对于每个 恰包含 $\boldsymbol n$ 个 $\tt 1$ 和 $\boldsymbol 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$ 取模后的结果。

样例 1 输入

2 1
000

样例 1 输出

3

样例 1 解释

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

样例 2 输入

5 5
0010111011

样例 2 输出

1391

数据范围

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

本题采用捆绑测试。

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