Problem Description

There are $ N $ chairs arranged in a circle. The chairs are numbered from $ 1 $ to $ N $. For each $ i $ such that $2 \leq i \leq N-1$, the $ i $th chair is adjacent to the $ i-1 $th and $ i+1 $th chairs. The $ 1 $st chair is adjacent to the $ 2 $nd and $ N $th chairs. The $ N $th chair is adjacent to the $ 1 $st and $ N-1 $th chairs.

$ A $ wolves and $ N-A $ foxes will sit in the $ N $ chairs, one animal per chair. Some of them are already seated. Specifically, a string $ S $ of length $ N $ consisting of W, F, and ? is given. When the $ i $th character of $ S $ is W, a wolf is already seated in the $ i $th chair. When the $ i $th character of $ S $ is F, a fox is already seated in the $ i $th chair. When the $ i $th character of $ S $ is ?, no one is seated in the $ i $th chair yet.

When there are $ x $ wolves and $ y $ foxes left to be seated, considering that wolves and foxes are indistinguishable among themselves, there are $ _{x+y}C_x $ ways for the remaining wolves and foxes to sit. For all these arrangements, find the total number of places where two adjacent chairs have different types of animals seated, and output the sum modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ S $ $ A $

Output Format

Output the answer modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

??FFW
2

Sample Output #1

6

Sample Input #2

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

Sample Output #2

73788

Notes/Hints

Constraints

• $3 \leq |S| \leq 10^6$
• $ N = |S| $
• $0 \leq A \leq N$
• $ S $ is a string consisting of W, F, and ?
• The number of W in $ S $ is at most $ A $
• The number of F in $ S $ is at most $ N-A $

Sample Explanation 1

There are $ 2 $ possible arrangements for the remaining wolves and foxes: WFFFW and FWFFW.
- In the case of WFFFW, there are $ 2 $ places where different types of animals are seated.
- In the case of FWFFW, there are $ 4 $ places where different types of animals are seated.
Therefore, the answer is $ 2 + 4 = 6 $.

见题面 Input 部分

见题面 Output 部分