AT_relay2018_e 狼と狐

在一个圆环上有 $N$ 张椅子，编号为 $1$ 到 $N$。每张椅子都与其左右相邻的椅子相连。具体关系为，第 $1$ 张椅子和第 $2$ 以及第 $N$ 张椅子相邻，第 $N$ 张椅子和第 $1$ 及第 $N-1$ 张椅子相邻，对于每个 $i$ 满足 $2 \le i \le N-1$，第 $i$ 张椅子与第 $i-1$ 和第 $i+1$ 张椅子相邻。 在这 $N$ 张椅子上，要分别坐下 $A$ 只狼和 $N-A$ 只狐狸。现在有些椅子上已经坐了动物。具体的分布由一个长度为 $N$ 的字符串 $S$ 描述，其中 `W` 表示该位置坐了一只狼，`F` 表示坐了一只狐狸，`?` 表示该椅子上还未有人坐。 接下来，我们需要安排剩余的 $x$ 只狼和 $y$ 只狐狸的座位。这些动物可以有 $_{x+y}C_x$ 种不同的安排方式。对于每一种安排方式，我们计算相邻椅子上坐不同种类动物的对数，并将所有可能安排下的这种对数相加，最后对 $10^9+7$ 取模。

输入通过标准输入给出，格式如下： > $ S $ $ A $

输出相邻椅子上坐不同种类动物的对数总和对 $10^9+7$ 取模的结果。

- $3 \le |S| \le 10^6$ - $N = |S|$ - $0 \le A \le N$ - $S$ 是由 `W`、`F`、`?` 三种字符组成 - $S$ 中 `W` 的数量不超过 $A$ - $S$ 中 `F` 的数量不超过 $N-A$ ### 示例解释 对于给定的情况，可能的排列有两种：`WFFFW` 和 `FWFFW`。 - 在 `WFFFW` 中，有 $2$ 对相邻椅子上坐了不同动物； - 在 `FWFFW` 中，有 $4$ 对相邻椅子上坐了不同动物。 因此，结果是 $2 + 4 = 6$。 **本翻译由 AI 自动生成**