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 自动生成