Dumitru 做了一个非常奇怪的梦：他梦见自己被锁在一个房间里。在房间里，他发现了 $n$ 个盒子，每个盒子里面恰好装有 $m$ 张小牌子，每张牌子上都写着一个大于或等于 $1$ 的整数。他还发现了一张小纸条，上面写着 $2$ 个整数 $k$ 和 $l$，并规定了以下任务：

步骤 1：从第一个盒子中选择一张牌，在笔记本上记录下牌上的数字，将牌上的数字修改为 $1$，然后将牌放回盒子中。随后，以相同的方式，从第二个盒子中选择一张牌，然后从第三个盒子中选择一张，依此类推，直到第 $n$ 个（最后一个）盒子（含），每次从相应的盒子中选择一张牌，在笔记本上记录其数字，将该牌上的数字修改为 $1$，然后将牌放回该盒子中。

步骤 2：在此之后，以相同的方式，从第 $n - 1$ 个盒子中选择一张牌，然后从第 $n - 2$ 个盒子中选择一张，然后从第 $n - 3$ 个盒子中选择一张，依此类推，直到第二个盒子（含），每次从相应的盒子中选择一张牌。

为了打开房门并走出去，Dumitru 需要求出按照上述方案选择牌的不同方式总数 $T$，使得笔记本中记录的数字之积能被 $k$ 整除。由于 $T$ 可能非常大，他需要求出 $T$ 除以 $l$ 的余数。

Dumitru 对这个梦感到非常困惑，因此他试图寻找上述任务的答案。

请编写一个程序来帮助 Dumitru 解决这个任务。

输入格式

输入的第一行包含 $2$ 个整数 $n$ 和 $m$，由单个空格分隔。

第二行包含 $2$ 个整数 $k$ 和 $l$，由单个空格分隔。

接下来的 $n$ 行，每行包含 $m$ 个由单个空格分隔的整数。其中第一行包含在第一个盒子中找到的牌上的 $m$ 个数字，第二行包含在第二个盒子中找到的牌上的数字，依此类推。

输出格式

输出应包含一个整数，即 $T$ 除以 $l$ 的余数。

样例

输入样例 1

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

输出样例 1

12

说明

根据任务中描述的步骤，共有 $12$ 种不同的选牌方式，使得笔记本中记录的数字之积能被 $12$ 整除。所有 $12$ 种方式如下图所示，其中在步骤 1中选择的牌上的数字用单直线标出，在步骤 2中选择的牌上的数字用双直线标出，而在两个步骤中都被选择的牌上的数字用波浪线标出。

12 种不同的选牌方式

如上图所示，图 1 和图 2 展示了 $2$ 种不同的选牌方式，即使在这两种情况下选择的是同一组牌。在图 3 中，第二行的第一张牌在步骤 1和步骤 2中都被选中，因此在这种情况下，笔记本中记录的数字之积等于 $2 \times 2 \times 3 \times 1 = 12$。这是因为在步骤 1中选中该牌后，牌上的数字 $2$ 被改写为了 $1$，因此在步骤 2中再次选中它时，记录的数字为 $1$。

数据范围

• $3 \le n \le 200$
• $3 \le m \le 10\,000$
• $2 \le k \le 200\,000$
• $2 \le l \le 30\,000$

盒子中牌上的数字为 $1$ 到 $1\,000\,000$ 之间的整数（包含边界）。