问题描述

小春最近很清闲，面对书桌上的n张牌，他决定给每张牌染色。目前小春只有3种颜色：红色（r），蓝色（b），绿色（g），他询问Sun有多少种染色方案，Sun很快给出了答案，这让小春很吃惊。进一步，小春要求染出Sr张红色，Sb张蓝色，Sg张绿色，他又询问Sun对此有多少种染色方案，Sun稍微想了一会儿有给出了正确答案。
最后小春发明了m种不同洗牌法，这时他又问Sun有多少种不同的染色方法，其中两种染色方法相同且仅当两种染色方法中的一种通过任意的洗牌法（即可以使用多种洗牌法而且每种洗牌法可以使用多次）洗成另一种方法，所以只要求出这个答案除p之后的余数即可（p为质数）。

数据输入

从文件cards.in中读入数据，文件中第1行有5个用空格隔开的整数，分别是Sr、Sb、Sg、m和p，n=Sr+Sb+Sg。接下来的m行，每行描述一种洗牌法，每行有n个用空格隔开的整数x1 x2 … xn,它恰好构成从1到n这n个整数的一个排列，表示经过使用这种洗牌法一次后，第i位的牌为原来第xi位的牌。输入数据保证任意多次洗牌都可以用这m种洗牌法中的一种代替，且对每种洗牌法，都存在一种洗牌法使得能回到原状态。其中m<=60，p为质数且m+1 < p < 100。20%的输入数据满足：n=Sr+Sb+Sg<20。100%的输入数据满足：Max{Sr，Sb，Sg}<=20。

数据输出

输出文件cards.out中仅包含一个整数，表示不同的染色方法总数除p之后的余数。

输入输出样例

cards.in

1 1 1 2 7
2 3 1
3 1 2

cards.out

2

Limitation

1s, 256MiB for each test case.

样例说明

共有2中本质上不同的染色方法RGB和RBG。使用洗牌法2 3 1一次可得GBR和BGR，使用洗牌法3 1 2一次可得BRG和GRB。

Source

2020年广东省第二十届信息学重点中学邀请赛（GDKOI2020）模拟试题-1 ( 第一试 )