#2614. 梦的困境

题目描述

"每一个OIer上辈子都是折翼的天使……"。

OIer喜欢做梦，尤其是关于OI题目的梦。

TT同学便是折翼天使的典范。在NOI2010 day1的前夜，TT梦见自己被困在一个房间里，房间里摆放着 _n_ 个箱子。他还看到墙上贴着一张告示。作为折翼天使的典范，他就像读题一样开始浏览告示。只见告示上写道：

天使大牛，在你面前摆放着 _n_ 个魔法箱，每个魔法箱里各有 _m_ 个碟子，每个碟子上写着一个正整数。然后我们还会给你两个整数 _k_ 和 _l_ 。

现在要求你从这 _n_ 个魔法箱中各取出1个或2个碟子(取碟子是有顺序的)，但是请 ** _注意_** ：由于某种原因，你从第1个箱子和第 _n_ 个箱子中都只能各取出一个碟子。

你取出的所有碟子上的数的乘积必须能被 _k_ 整除。

令T:=满足上述条件的取碟子方案数 mod _l_ 。(mod为取模符号)

为了能够解开这个房间大门的密码锁，而这个密码便是 _T_ 。

TT急了，这明摆着不就是一道OI题么。哥明天还得考NOI呢，今晚就要刷题啦？醒醒啊，醒醒啊……

可就是醒不来，他走到门边，发现上面又有一张告示：如果密码输入错误，你明天比赛必然挂掉……

请你写一个程序帮助TT求出密码 _T_ 。

输入格式

。第一行包含两个整数 n 、 m 。第二行包含两个整数 k 、 l 。接下来给出 n × m 的矩阵。( x ， y )元表示第x个箱子中的第y个碟子上的整数。(数与数之间以空格隔开。)

输出格式

一个整数 T 。

样例

样例输入

3 3  

12 100  

5 2 1  

2 1 2  

3 7 4  

样例输出

12

数据范围与提示

.jpg)