問題文

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 以下

入力例 1

??FFW
2

出力例 1

6

残りの狼と狐の座り方は 2 通りあり、 WFFFW と FWFFW が可能な座り方です。

• WFFFW の場合、2 箇所において異なる種類の動物が座っています。
• FWFFW の場合、4 箇所において異なる種類の動物が座っています。

よって、求める答えは 2+4=6 です。

入力例 2

FW???WF??????W??????
10

出力例 2

73788