题目描述

小 $Q$ 通过研究发现灭霸之所以能成功打出响指，关键在于无限手套上的宝石中有至少 $K$ 颗包含 能量。为了更进一步的研究，他向宇宙管理局收集了目前已知的所有无限宝石，一共是 $N$ 颗，编号从 $1-N$ ，他想知道这 $N$ 颗宝石中哪些有能量，哪些没有能量的方案数量。

所以，他邀请灭霸先生帮助他进行测试，并给了他新的无限手套，一次可以放任意数量的宝石，然后尝试打响指。如果成功打出响指，代表目前手套上的宝石中有至少 $K$ 颗包含 能量 。

小 $Q$ 制定了 $M$ 次测试计划，每次选择 $C$ 颗宝石，编号分别是 $A_1,A_2,A_3...A_C$，并且，灭霸先生会告诉你此次计划能否成功打出响指。

已知 $N$ 颗宝石一共有 $2^N$ 种方案，小 $Q$ 想知道其中一共有多少种可能方案可以符合上述 $M$ 次测试的结果。

输入格式

第一行 3 个整数 $N,M,K$，

接下来 $M$ 行，

每行的第 1 个整数为 $C$，代表接下来有 $C$ 个整数，分别代表本次测试选择宝石编号 $A_1,A_2...A_C$，作为测试对象，

每行的最后是一个字符，这个字符仅为 Y 或者 N ，分别代表响指成功和失败。

输出格式

一个整数，代表满足所有测试结果的方案数。

样例数据

3 2 1
2 2 3 Y
1 1 N

3

样例1解释：

测试1：选择序列中的第2颗宝石，第3颗宝石，字符Y代表成功打出响指。

测试2：选择序列中的第1颗宝石，字符N代表打响指失败。

下面合理方案里用0代表没有 能量 ，1代表有。

符合上述两次测试的方案有 3 种，分别为：{011}，{001}，{010}

7 5 2
6 4 5 2 3 1 7 Y
3 5 3 1 N
4 4 2 6 5 Y
5 6 1 3 2 4 Y
6 1 7 4 3 5 2 N

0

数据范围

• 对于 $10\%$ 的数据，保证结果为 $0$
• 对于 $100\%$ 的数据，$1\le N,K\le 15,1\le M\le 100,1\le C,A_i\le N$。