题目描述

给出 $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 \le n \le 200, 3 \le m \le 10 ^ 4, 2 \le k \le 2 \times 10 ^ 5, 2 \le l \le 3 \times 10 ^ 4$，保证矩阵中所有的数都是 $[1, 10 ^ 6]$ 中的整数且互不相同。