题目描述

某次 $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 \lt G \le 3$ )。

每组测试数据格式如下：

第一行，$3$ 个整数，分别是 $P[1],P[2],P[3]$ ( $25000 \le P[1] \le 30000$， $45000 \le P[2] \le 60000$, $90000 \le P[3] \le 110000$。

第二行，一个整数 N ($1 <= N <= 20$ )。

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

输出格式

共 $G$ 行，每行一个整数。

样例

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

25000
799969993
0