狼と狐翻译

题目描述

独狼将N把椅子放在一张圆桌旁，椅子的编号为1 ~ N，他有A只狼和N-A只狐狸，每把椅子上各坐1只动物，其中有几只已经坐在椅子上了。独狼将此时的情况描述为一个由W，F和？组成的字符串S，对于第i个字符，如果它是W，则此位置上是一只狼，是F，则此位置上是一只狐狸，是问号,则这是把空椅子。当然，他还是需要把余下的动物安排在空椅子上的。

座位安排满后，把相同动物所在的区间叫做同类区，如W(1)W(2)F(3)W(4)中有两个同类区：W(4)W(1)W(2)，F(3)。为了方便接下来安排这些动物的伙食，独狼需要知道在所有的就座方案中，同类区有几个。但他还有事，因此把这个任务交给了你。

给出S和A，求出一共会产生多少个同类区；另外，因为答案可能很大，将答案对10^9+7取模。

输入输出格式

输入

第一行一个字符串S，含义同题面；

第二行一个整数A，表示狼的数量。

输出

一个整数，代表总共会产生的同类区数目对10^9+7取模的结果。

说明/提示

• 3$\leq$N$\leq$10^6；
• 0$\leq$A$\leq$N；
• S是由W, F， ?组成的字符串；
• S中W的个数在A以下；
• S中F的个数不超过N-A。

样例1解释

剩下的狼和狐狸的就座方案有2种，分别是WFFFW和FWFFW。在第一个方案中，会产生2个同类区；在第二个方案中，会产生4个同类区。因此，得到的答案是2+4=6。