Description

小春现在很清闲, 面对书桌上的 \(n\) 张牌, 他决定给每张染色, 目前小春只有 3 种颜色: 红色, 蓝色, 绿色. 他询问 Sun 有多少种染色方案, Sun 很快就给出了答案. 进一步, 小春要求 染出 \(S_r\) 张红色,\(S_b\) 张蓝色,\(S_g\) 张绿色. 他又询问有多少种方案, Sun 想了一下, 又给出了正确答案. 最后小春发明了 \(m\) 种不同的洗牌法, 这里他又问 Sun 有多少种不同 的染色方案.

两种染色方法相同当且仅当其中一种可以通过任意的洗牌法 (即可以使用多种洗牌法, 而每种方法可以使用多次) 洗成另一种. Sun 发现这个问题有点难度, 决定交给你, 答案可能 很大, 只要求出答案除以 \(P\) 的余数 (\(P\) 为质数).

Input

第一行输入 5 个整数:\(S_r, S_b, S_g, m, p (m \leq 60, m+1 \lt p \lt 100), n = S_r + S_b + S_g\).

接下来 \(m\) 行, 每行描述一种洗牌法, 每行有 \(n\) 个用空格隔开的整数 \(X_1, X_2, \ldots, X_n\), 恰为 \(1\) 到 \(n\) 的一个排列, 表示使用这种洗牌法, 第 \(i\) 位变为原来的 \(X_i\) 位的牌. 输入数据保证任意多次洗牌都可用这 \(m\) 种洗牌法中的一种代替, 且对每种洗牌法, 都存在一种洗牌法使得能回到原状态.

Output

输出一个整数, 表示不同染法除以 \(P\) 的余数.

Sample Input

1 1 1 2 7
2 3 1
3 1 2

Sample Output

2

Data Range

100% 数据满足 \(max(S_r, S_b, S_g) \leq 20\).

Explanation

Burnside 定理: 有 m 个置换 k 种颜色, 所有本质不同的染色方案数就是每种置换的不变元素的 个数的平均数. 所谓不变元素就是一种染色方案经过置换变换后和没变化之前一样. 所以 现在就是需要求出不变元素, 同时还要满足各种颜色数量的限制. 置换的循环在不变元素中一定是一个颜色, 然后可以求一个三维的 01 背包的方案数. 而最后的除法需要利用扩展 欧几里得求乘法的逆元.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxm = 100, maxn = 100;

int modr = 0;
int s1, s2, s3, n, m, p;
int arr[maxm][maxn];

int dp[maxm][maxn][maxn];
int d[maxn];
bool vis[maxn];
int eval(int x)
{
    for (int i = 1; i <= n; i++)
        vis[i] = false;
    int sum = 0, p;
    // Iterate through colours 1 ~ n
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        // Circulate around the scheme
        d[++sum] = 1; p = i;
        vis[p] = true;
        while (!vis[arr[x][p]]) {
            d[sum] += 1;
            vis[arr[x][p]] = 1;
            p = arr[x][p];
        }
    }
    // Clean dp setup
    for (int i = s1; i >= 0; i--)
        for (int j = s2; j >= 0; j--)
            for (int k = s3; k >= 0; k--)
                dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    // Dynamic programming
    #define modr_add(__x,__y) __x=(__x+__y)%modr
    for (int h = 1; h <= sum; h++)
        for (int i = s1; i >= 0; i--)
            for (int j = s2; j >= 0; j--)
                for (int k = s3; k >= 0; k--) {
                    if (i >= d[h])
                        modr_add(dp[i][j][k], dp[i - d[h]][j][k]);
                    if (j >= d[h])
                        modr_add(dp[i][j][k], dp[i][j - d[h]][k]);
                    if (k >= d[h])
                        modr_add(dp[i][j][k], dp[i][j][k - d[h]]);
                }
    // Returning results
    return dp[s1][s2][s3];
}

void ext_gcd(int a, int b, int &x, int &y)
{
    if (b == 0) {
        x = 1, y = 0;
        return ;
    }
    ext_gcd(b, a % b, x, y);
    int t = x; x = y;
    y = t - a / b * y;
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d%d%d%d%d", &s1, &s2, &s3, &m, &p);
    n = s1 + s2 + s3;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &arr[i][j]);
    modr = p; // Modulo
    // This points to itself (retains data)
    m += 1;
    for (int j = 1; j <= n; j++)
        arr[m][j] = j;
    // Retrieving results
    int res = 0;
    for (int i = 1; i <= m; i++)
        res = (res + eval(i)) % modr;
    // modr-base division modulo
    int x, y;
    ext_gcd(m, modr, x, y);
    while (x <= 0)
        x += modr, y -= m;
    printf("%d\n", res * x % modr);
    return 0;
}