梦的困境

“每一个 OIer 上辈子都是折翼的天使……”

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

在 NOI $2010$ Day $1$ 的前夜，TT 梦见自己被困在一个房间里，房间中摆放着 $n$ 个箱子。他还看到墙上贴着一张告示，上面写着：

在你面前有 $n$ 个魔法箱，每个箱子中都有 $m$ 个碟子，每个碟子上写着一个正整数。此外，还会给出两个整数 $k$ 和 $l$ 。

你需要从每个魔法箱中依次取出 $1$ 个或 $2$ 个碟子。取碟子的顺序不同视为不同方案。但需要特别注意：从第 $1$ 个箱子和第 $n$ 个箱子中都只能取出 $1$ 个碟子。

所有取出的碟子上所写整数的乘积必须能被 $k$ 整除。

设满足上述条件的取碟子方案数对 $l$ 取模后的结果为 $T$ ，即：

T=\text{满足条件的方案数}\bmod l。

房间大门的密码正是 $T$ 。如果输入了错误的密码，TT 明天的比赛就会遭遇不幸。

请你编写程序，帮助 TT 求出密码 $T$ 。

输入格式

第一行包含两个整数 $n$ 、 $m$ 。

第二行包含两个整数 $k$ 、 $l$ 。

接下来输入一个 $n\times m$ 的整数矩阵，其中第 $x$ 行第 $y$ 列的元素表示第 $x$ 个箱子中第 $y$ 个碟子上所写的正整数。同一行中的整数之间以空格分隔。

输出一个整数 $T$ ，表示满足条件的取碟子方案数对 $l$ 取模后的结果。

本题题面与测试数据整理自 BZOJ 2614。