超时空军团¶

参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
内存限制：256 MB

背景故事¶

一名超时空军团兵潜入游戏中的苏军基地，准备切断建筑之间的通信链路。但只要有两座建筑无法相互通信，警报就会响起。

他打算在始终保持通信畅通的前提下，破坏尽可能多的链路。指挥官还想知道，一共有多少种不同的行动顺序。

基地位于 \(N\) 行、\(M\) 列的网格内，有 \(K\) 座带编号的建筑。建筑 \(i\) 位于 \((X_i,Y_i)\) ，建造时间为 \(T_i\) .建造时间互不相同，但不同建筑可以占据同一格，计数时仍视为不同建筑。

以建筑 \(i\) 为中心、非负整数 \(r\) 为半径的范围，包含所有满足

\[ \max(|X_j-X_i|,|Y_j-Y_i|)\le r \]

的建筑 \(j\) .范围包含中心建筑自身；半径可以为 \(0\) ，此时包括同一坐标上的所有建筑。

建筑 \(i\) 有 \(P_i\) 个阈值 \(D_{i1},\ldots,D_{iP_i}\) .对每个阈值 \(D\) ，按以下方式生成链路：

阈值可以重复。无论同一对建筑被选择多少次，最终都只有一条链路。保证最终的无向图连通。

每次行动删除一条当前存在的链路，要求每次删除后图仍然连通。求删除条数达到最大值的行动序列数量，对输入整数 \(\mathrm{mod}\) 取模。两序列只要某一步删除的链路不同，就算不同方案；空序列计为一种方案。

第一行包含四个整数 \(N,M,K,\mathrm{mod}\) .

接下来 \(K\) 行，第 \(i\) 行先给出 \(X_i,Y_i,T_i,P_i\) ，再给出 \(P_i\) 个整数 \(D_{i1},\ldots,D_{iP_i}\) .

输出一行一个整数，表示方案数对 \(\mathrm{mod}\) 取模的结果。

前两座建筑分别与第三座相连，得到一棵树。不能再删除任何链路，只有空序列一种方案。

1 4 3 12
1 1 1 2 2 3
1 2 2 1 3
1 4 3 1 3

三座建筑两两相连。最多删除一条链路，三条链路都可以选择。

1 2 3 1000000007
1 1 1 2 1 3
1 1 2 1 3
1 2 3 1 3

第一座建筑的阈值 \(1\) 对应半径 \(0\) ，范围内同时有第一、第二座建筑，故连接第二座。其余阈值还生成到第三座的链路，最终得到三角形。

1 1 1 2
1 1 0 1 1

唯一建筑不会和自己相连，空序列是唯一方案。

\(1\le N,M\) ，\(NM\le10^6\) ，\(1\le K\le200\) .
\(1\le X_i\le N\) ，\(1\le Y_i\le M\) ，\(0\le T_i\le10^{18}\) ；所有 \(T_i\) 互不相同。
\(1\le P_i\le K\) ，\(1\le D_{ij}\le K\) ；阈值可以重复。
\(2\le\mathrm{mod}\le1000000500\) ，不保证为质数。
所有输入量均为整数，生成的链路图保证连通。\(K=1\) 时也视为连通。