题目描述

给出 n 行 m 列的数字矩阵。从第一行的数列中选一个数字，从最后一行的数列中选一个数字。

从其它的行中，每行取一到两个数。将取出来的数字相乘，希望其可以被 k 整除。你只需要输出结果模 l 的值。

输入格式

第一行给出 n,m，第二行给出 k,l。下面有 n 行 m 列，用于描述数字矩阵。

输出格式

一行一个整数表示答案。

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

12

数据规模与约定

对于 100% 的数据，3≤n≤200,3≤m≤104,2≤k≤2×105,2≤l≤3×104，保证矩阵中所有的数都是 [1,106] 中的整数且互不相同。