题目描述

给出 $n$ 行 $m$ 列的数字矩阵。

从矩阵中选出一些数，并将选出的数相乘，求满足相乘结果被 $k$ 整除 的选数方案数。

选数规则：从第一行的数列中选一个数字，从最后一行的数列中选一个数字，从其它的行中每行取一到两个数。

输入格式

第一行给出 $n \ m \ (3≤n≤200,3≤m≤10^4)$，

第二行给出 $k \ P \ (2≤k≤2×10^5 ,2≤P≤3×10^4)$ 。

下面有 $n$ 行 $m$ 列，用于描述数字矩阵，矩阵中所有的数都是 $[1,10^6]$ 中的整数且互不相同。

输出格式

一行一个整数，输出结果模 $P$ 的值。

样例输入

3 3
12 100
5 2 1
2 1 2
3 7 4 

样例输出

12