题目描述

某次IOI总决赛比赛有3道题。第i题的分值是P[i]分。如果选手提交了第i题，那么选手该题可能的得分是1至P[i]分；如果选手不提交第i题，那么该选手第i题得分肯定是0分。现在比赛结束了，你很想看一下“排名榜”。“排名榜”按照选手的总分从高到低排序，每一个选手都有3列，第1列是该选手第1题的得分，第2列是该选手第2题的得分，第3列是该选手第3题的得分。本次总决赛很特殊，不进行网络直播，所以只有在总决赛现场的人才能看到“排名榜”。作为今年NOIP不到500分的选手，很显然，你不在总决赛现场。于是你打电话给在总决赛现场的朋友FJ。FJ不直接告诉你“排名榜”，而是按照“排名榜”从第1名到最后1名的顺序，给你一个N行3列的二维数组submit[1..N][1..3]，其中submit[i][j]要么是'Y'要么是'N'，表示第i个选手是否提交了第j题, 而且FJ还明确告诉你：所有选手的总分都不相同。那么，现在的问题是：有多少种不同的“排名榜”满足上述的题意？答案模1000000007。由于FJ可能忽悠你，所以当不存在方案满足题目的要求时，输出0。

输入格式

多组测试数据。

第一行，一个整数G，表示有G组测试数据。1 <G<=3。

每组测试数据格式如下：

第一行，3个整数，分别是P[1],P[2],P[3]。25000<=P[1]<=30000，  45000<=P[2]<=60000,   90000<=P[3]<=110000。
第二行，一个整数N。1 <= N <= 20。

接下来是N行3列的二维矩阵。每个元素要么是'Y'，要么是'N'， submit[i][j]=‘Y’表示选手i提交了第j题。submit[i][j]=‘N’表示选手i没有提交第j题。

输出格式

共G行，每行一个整数。

输入/输出例子1

3
25000 50000 100000
2
YNN
NNN
30000 60000 90000
2
NYN
NYN
25000 45000 110000
2
NNN
YYY

25000
799969993
0