配点 : 100 点
問題文
N 椅子排成一圈。在椅子上 它的编号为 1 〜 N 并且2 ≤ i ≤ N-1 是 i 对于每个, 第i 椅子是 i-1 第椅子和 毗邻第 i+1 把椅子。1 椅子是 2 第椅子和 毗邻第 N 把椅子。 N 椅子是 1 第椅子和 毗邻第 N-1 把椅子。
狼 A 动物和狐狸 N-A 鱼 N 椅子 1 我决定一一坐下。其中一些人已经坐在椅子上。具体来说,
长度由W, F, ? 组成
给出了 N 字符串 S 。
S 的 i 第一个字母是
当 W 时,
一只狼已经坐在i 椅子上。
一只狐狸已经坐在
S 的 i 第一个字母是
当 F 时,
一只狼已经坐在i 椅子上。
尚未有人坐在
S 的 i 第一个字母是
当 ? 时,
一只狼已经坐在i 椅子上。
狼还没有坐在椅子上。 x 一只狐狸 y 当有狼和狐狸的时候,如果我们不区分狼和狐狸,那么剩下的狼和狐狸的坐姿是一样的。 _{x+y}C_x 方法有很多。 与所有这些相邻 2 如果你计算一张椅子上不同类型的动物坐在的位置,并将它们加起来,你会得到多少个位置? 由10^9+7 求余数。 打印除以
制約
- 3 ≤ |S| ≤ 10^6
- N = |S|
- 0 ≤ A ≤ N
- S 是
W,F,?组成的字符串 包含在 - S 中
W的数量是 A 以下 - S 中
F的数量是 N-A 以下
入力
输入将以以下形式通过标准输入给出。
S A
出力
答案10^9+7 后的余数。
入力例 1
??FFW 2
出力例 1
6
其余的狼和狐狸如何坐 2 有一条街, WFFFW 和
将其放在 FWFFW 是一种可能的坐姿。
WFFFW,2 不同种类的动物坐在不同的地方。FWFFW,4 不同种类的动物坐在不同的地方。
因此,您正在寻找的答案是 2+4=6 。
入力例 2
FW???WF??????W?????? 10
出力例 2
73788