[HNOI2008]Cards

题目描述

小春现在很清闲,面对书桌上的 $n$ 张牌,他决定给每张牌染色,目前小春拥有 $3$ 种颜色:红色,蓝色,绿色。他询问 Sun 有多少种染色方案,Sun 很快就给出了答案。 进一步,小春要求染出 $S_r$ 张红色,$S_b$ 张蓝色,$S_g$ 张绿色。他又询问有多少种方案,Sun 想了一下,又给出了正确答案。最后小春发明了 $m$ 种不同的洗牌法,这里他又问 Sun 有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种。 Sun 发现这个问题有点难度,决定交给你,由于答案可能很大,你只需要求出答案对于 $P$ 取模的结果。 保证 $P$ 为一个质数。

输入输出格式

输入格式


第一行输入 $5$ 个整数,依次表示:$S_r,S_b,S_g,m,P$($m\le 60,m+1<p<100$)。其中,题面所提及的 $n$ 为 $S_r+S_b+S_g$,即 $n=S_r+S_b+S_g$。 接下来 $m$ 行,每行描述一种洗牌法,每行有 $n$ 个用空格隔开的整数 $X_1X_2...X_n$,保证其为 $1$ 到 $n$ 的一个排列,表示使用这种洗牌法,第 $i$ 位变为原来的 $X_i$ 位的牌。输入数据保证任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替,且对每种洗牌法,都存在一种洗牌法使得能回到原状态。 同时,对于 $100\%$ 的数据满足 $\max\{S_r,S_b,S_g\}\le 20$ 。

输出格式


不同的染色方法对 $P$ 取模的结果。

输入输出样例

输入样例 #1

1 1 1 2 7
2 3 1
3 1 2

输出样例 #1

2

说明

有 $2$ 种本质上不同的染色法:`RGB` 和 `RBG`,使用洗牌法 `231` 一次,可得 `GBR` 和 `BGR`,使用洗牌法 `312` 一次,可得 `BRG` 和 `GRB`。