UOJ Logo

NOI.AC

1S 512MB

#329. chess

Statistics

【问题描述】

一种新型的国际象棋游戏,棋盘中有N行M列的方格,每格上有一个数字,这组成了一个数字矩阵。

象棋的规则是,从第一行的数中选一个数字,从最后一行的数中选一个数字. 从其它的行中,每行取一到两个数. 将取出来的数字相乘,希望其可以被A整除.

求所有取法数量 Mod H 的值.

【输入格式】

第一行给出N,M

第二行给出A,H

下面有N行M列,用于描述数字矩阵其值在[1,1000000]各不相同.

N在[3,200]

M在[3,10000]

A在[2,200000]

H在[2,30000]

【输出格式】

一行,取法总数Mod H

【输入输出样例 1】

in

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

out

12

【数据规模与约定】

20% 的数据,n <= 10, m <= 30

40% 的数据,n <= 20, m <= 100

100% 的数据,3 <= n <= 200, 3 <= m <= 10000, 2 <= A <= 200000, 2 <= H <= 300000