[Balkan2007]Dream

时间限制:10s      空间限制:162MB

题目描述

给出N行M列的数字矩阵. 从第一行的数列中选一个数字,从最后一行的数列中选一个数字. 从其它的行中,每行取一到两个数. 将取出来的数字相乘,希望其可以被K整除. 你只需要输出结果Mod L的值.


输入格式

第一行给出N,M 第二行给出K,L 下面有N行M列,用于描述数字矩阵其值在[1,1000000]各不相同. N在[3,200] M在[3,10000] K在[2,200000] L在[2,30000]


输出格式

取法总数Mod L


样例输入

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

样例输出

12

提示

以下为样例的12种取法. 5 2 1 2 1 2 3 7 4 Pic. 1 5 2 1 2 1 2 3 7 4 Pic. 2 5 2 1 2 1 2 3 7 4 Pic. 3 5 2 1 2 1 2 3 7 4 Pic. 4 5 2 1 2 1 2 3 7 4 Pic. 5 5 2 1 2 1 2 3 7 4 Pic. 6 5 2 1 2 1 2 3 7 4 Pic. 7 5 2 1 2 1 2 3 7 4 Pic. 8 5 2 1 2 1 2 3 7 4 Pic. 9 5 2 1 2 1 2 3 7 4 Pic. 10 5 2 1 2 1 2 3 7 4 Pic. 11 5 2 1 2 1 2 3 7 4 Pic. 12


题目来源

没有写明来源