Loop nest

Problem Description

There are $m$ sets $P_i,Q_i$£¬$\forall i(1\leq i\leq m),Pi,Qi\subseteq \{1¡­i-1\}$. There are nested loops with $m$ layers, and for the $j$th layer, the loop variable is $i_j$, the lower bound equals $\max\{i_k(k\in P_j)\}$(especially, when $P_j$ is empty set, it means the lower bound equals $1$), the upper bound equals $\min\{i_k(k\in Q_j)\}$(especially, when $Q_j$ is empty set, it means the upper bound equals $n$). HazelFan want to know how many times the loop body will be executed, module $p$.

Input

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases. For each test case: The first line contains three positive integers $m,n,p(1\leq m\leq15,1\leq n\leq10^9,2\leq p\leq10^9+7)$. The next $m$ lines, the $i$th line contains several nonnegative integers describing the sets $P_i,Q_i$. The first integer is $A_i$, denoting the size of $P_i$, then next $A_i$ integers denotes the elements of $P_i$. The next integer is $B_i$, denoting the size of $Q_i$, then next $B_i$ integers denotes the elements of $Q_i$.

Output

For each test case: A single line contains a nonnegative integer, denoting the answer.

Sample Input

2

2 10 233

0 0

1 1 0

6 10 987654321

0 0

1 1 0

0 0

1 3 0

0 1 4

1 2 2 1 2

Sample Output

55

3850

Source

2017 Multi-University Training Contest - Team 7

https://acm.hdu.edu.cn/showproblem.php?pid=6131