提示: 欢迎访问OurACM平台。
Problem 2170 花生的序列

Accept: 149    Submit: 444
Time Limit: 3000 mSec    Memory Limit : 32768 KB

Problem Description

“我需要一个案件!!!”,没有案件卷福快疯了。花生不忍心看卷福这个样子,他决定帮卷福找点事情做。

花生拿了两个长度为N的相同的序列,序列都为WB(WBWBWB...)相间,并且由W开头。他将两个序列并在了一起,其中属于同个序列的元素相对位置不变。花生高兴的把新序列拿给卷福,要求卷福给每个元素标上1或2编号,表示这个元素是原来的第几个序列的元素。

卷福看完花生的序列,哭笑不得。“笨蛋!你难道不知道这个标号不唯一么!那你知道有多少种不同的标号方案么?”

可怜的花生给自己挖了个坑。快来帮他解决这个问题!

Input

输入第一行包含一个整数t,表示输入组数。

每组数据第一行为一个整数N(1<=N<=3000),表示每个原序列的长度。

接下来一行为一个只包含’W’, ’B’的字符串,长度为2*N。

Output

输出一个整数占一行,为标号的方案数。由于答案比较大,请将答案mod 1000000007。

Sample Input

3 2 WBWB 2 WWBB 2 BBWW

Sample Output

2 4 0

Submit  Back  Status  Discuss