题目描述

给定一个大小为 $K$ 的环 $R$。

环是一类包含两种运算（乘法 $\otimes$ 和加法 $\oplus$）的代数系统，满足结合律、交换律、单位元、逆元等代数性质。

考虑所有 $N$ 维向量 $\boldsymbol{u} = (u_1, u_2, \dots, u_N)$（每个分量都是 $R$ 中的元素），定义向量加法和数量乘法。

对于一个向量集合 $S = \{\boldsymbol{s_1}, \boldsymbol{s_2}, \dots, \boldsymbol{s_n}\}$，称其能够表示 $\boldsymbol{u}$ 当且仅当存在 $a_1, a_2, \dots, a_n \in R$ 使得 $\sum_{i=1}^n a_i \boldsymbol{s_i} = \boldsymbol{u}$。

称一个 $N$ 维向量集合 $S$ 是一个完全表示，当且仅当它能够表示所有 $N$ 维向量。

求所有 $N$ 维完全表示的大小的 $M$ 次方和对 $164511353$（一个质数）取模的结果。

输入格式

第一行输入三个数 $N, K, M$。

第二行输入一个数 $tp$。

我们认为 $R$ 中的每个元素唯一对应 $[0, K)$ 中的一个整数。特别地，保证加法单位元对应 $0$，乘法单位元对应 $1$。

如果 $tp = 1$，则 $\forall i,j \in R$，$i \oplus j = (i + j) \bmod K$，$i \otimes j = (i \times j) \bmod K$。

如果 $tp = 2$，接下来输入 $2K$ 行每行 $K$ 个数。

• 对于前 $K$ 行，第 $i+1$ 行的第 $j+1$ 个元素表示 $i \oplus j$
• 对于后 $K$ 行，第 $i+1$ 行的第 $j+1$ 个元素表示 $i \otimes j$

输出格式

输出一行一个数，表示答案对 $164511353$ 取模的结果。

样例 1

输入

2 2 3
2
0 1
1 0
0 0
0 1

输出

196

全体完全表示为：$\{(0,0),(0,1),(1,0)\}$，$\{(0,0),(0,1),(1,1)\}$，$\{(0,0),(1,0),(1,1)\}$，$\{(0,0),(0,1),(1,0),(1,1)\}$，$\{(0,1),(1,0)\}$，$\{(0,1),(1,1)\}$，$\{(1,0),(1,1)\}$，$\{(0,1),(1,0),(1,1)\}$，答案为 $3 \times 2^3 + 4 \times 3^3 + 1 \times 4^3 = 196$

样例 2

输入

2 3 3
2
0 1 2
1 2 0
2 0 1
0 0 0
0 1 2
0 2 1

输出

61995

该样例输入等价于

2 3 3
1

样例 3

输入

2 4 1
2
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
0 0 0 0
0 1 2 3
0 2 3 1
0 3 1 2

输出

524132

数据范围与提示

对于所有数据，$1 \leq N \leq 100000$，$2 \leq K \leq 100000$，$0 \leq M \leq 1000$，$\forall i,j \in R, i \oplus j, i \otimes j \in [0, K)$，保证输入是一个合法的环。

子任务编号	$N$	$K$	$M$	$tp$	特殊性质	分值
1				1	$K^N \leq 20$	10
2	$\leq 20$	是质数	$= 0$			15
3	$\leq 1000$					5
4
5		$\leq 100$				15
6						5
7	$\leq 100$		$\leq 100$			15
8
9		$\leq 20$		$2$