The Patterns

对于一个1到n的全排列Q，我们定义Q对应的字符串S_Q,其中:

例如对于n=5,Q=32154, S_Q=DDUD。
本任务为给定一个仅包含字符’U’与’D’长度为m的模式串P以及一个正整数n，求解1到n的任意全排列中模式串出现次数的期望值。例如某个S_Q=UUU,P=UU,则P出现次数为2次。
例如n=3,P=U,则1到n的所有全排列方案对应的模式串P出现次数分别为:


则1到n的任意全排列中模式串出现次数的期望值
E=(2+1+1+1+1+0)/6=1.0

为了避免浮点数精度误差，请输出(E*n!) mod (10⁹ +7)， 其中mod为取模操作，具体定义以及运算规则参见： 链接地址

输入数据第一行为一个整数T（1 <= T <= 3333），表示有 T 组测试数据。
下面T组数据，每组数据第一行包含2个正整数n, m，接下来一行包含一个字符串P(仅包含字符’U’与’D’)

数据规模:
1 <= m <= 1000  
m<n<=1000000

对于第k组数据，第一行输出Case #k:，第二行输出(E * n!) mod (10^9 + 7)。

5
4 3
UUU
4 2
UU
10 8 
UUUUDDDD
2 1
U
2 1
D

Case #1:
1
Case #2:
8
Case #3:
1400
Case #4:
1
Case #5:
1

2014年百度之星程序设计大赛 - 复赛