A36054.符文锁

时间限制: 1000ms
内存限制: 128MB

Yuilice在提瓦特大陆冒险的时候拿到了$N$个符文，我们以$1,2,3,\cdots,N$的序号来给他们命名。

在符文隐藏的信息当中，Yuilice找到了符文所对应的宝藏$Y$，你最少需要$M$个被符文锁记录的符文才可以打开这份宝藏。

目前Yuilice已经进行了$q$次的解锁，第$i$次的测试结果如下表示:

1. Yuilice将$K_i$个符文$a_{i,1},a_{i,2},\cdots,a_{i,K_i}$放入了锁中。
2. 符文锁返回字符o，代表符文锁已解锁。返回x,代表未解锁。

现在请你根据解锁的结果，判断哪些符文被记录在锁中，哪些没有。同时计算出有 多少种不与解锁结果冲突 的符文组合解锁方式。

PS: 如果不存在任何一种确定的解锁方式，那么请输出0。

第一行输入三个整数$N,q,M$，表示符文的数量，以及Yuilice解锁的次数,$Y$符文锁中包含的符文数量。

随后$q$行，每行输入的第一个数字代表$K_i$，表示第$i$次解锁时放入锁中的符文数, 随后输入$K_i$个整数$a_{i,1},a_{i,2},\cdots,a_{i,K_i}$，表示第$i$次解锁时放入锁中的符文的序号。 最后输出一个字符$C_i$，代表本次解锁的结果。

输出一个数字，代表所有解锁的符文组合方案。

样例解释

【样例1】

Yuilice进行了两次测试，同时符文锁记录了2个符文。

• 在第一次测试中，使用了符文 $1, 2, 3$ 符文锁打开。
• 在第二次测试中，使用了符文 $2, 3$ 符文锁没有打开。

总计有两种情况:

• 符文 $1,3$ 为被记录的符文，但是符文 $2$ 没有。
• 符文 $1,2$ 为被记录的符文，但是符文 $3$ 没有。

【样例2】

无法寻找到任何一组不与已知解锁结构冲突的组合方式

【数据范围】

• $1 \le M \le N \le 15$
• $1 \le q \le 100$
• $1 \le K_i,A_{i,j} \le N$
• $A_{i,j} \neq A_{i,k}$ 如果 $j \neq k$ .
• 数据保证 $N$ 、 $M$ 、 $q$ 、 $K_i$ 和 $A_{i,j}$ 为整数,$C_i$ 一定为 o 或 x。