← 返回题目列表

AtCoder · relay2018_e

E. 狼和狐狸

中文机器翻译题面 查看原题

配点 : 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