public class UniqueMST{
    int mod;

    int add(int a, int b){a += b; if(a >= mod) a -= mod; return a;}

    int sub(int a, int b){a -= b; if(a < 0) a += mod; return a;}

    int mul(int a, int b){return (int)((a * 1L * b) % mod);}

    int powr(int a, long b){
        int ret = 1;
        for(; b > 0; b >>= 1, a = mul(a, a)) if(b % 2 == 1) ret = mul(ret, a);
        return ret;
    }

    int inv(int a){
        return powr(a, mod - 2);
    }

    int lagrange(int [] v, int x){
        int k = v.length - 1;
        if(x <= k) return v[x];
        int ret = 0;
        for(int i = 0; i <= k; i++){
            int num = 1, den = 1;
            for(int j = 0; j <= k; j++) if(j != i){
                num = mul(num, sub(x, j));
                den = mul(den, sub(i, j));
            }
            ret = add(ret, mul(v[i], mul(num, inv(den))));
        }
        return ret;
    }

    public int count(int N, int K, int M){
        if(N == 2) return K;
        mod = M;
        int E = (N * (N - 1))/2;

        int [][] C = new int[N + 1][N + 1];
        int [][] dp = new int[N + 1][E + 1];
        int [] F = new int[N + 1];
        int [] H = new int[N + 1];
        
        for(int i = 0; i <= N; i++){
            C[i][0] = 1;
            for(int j = 1; j <= i; j++){
                C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
            }
        }
        
        for(int k = 0; k <= E; k++){
            dp[1][k] = 1;
            dp[2][k] = k;
        }

        for(int n = 3; n <= N; n++){
            for(int k = 1; k <= E && k < K; k++){
                int inv_choices = inv(K - k);
                int curr = inv_choices, P = 1;
                F[0] = 1;
                for(int m = 1; m <= n; m++){
                    P = mul(P, inv_choices);
                    H[m] = mul(mul(n * m, dp[m][k - 1]), curr);
                    curr = mul(curr, P);
                    F[m] = 0;
                    for(int r = 1; r <= m; r++){
                        F[m] = add(F[m], mul(C[m - 1][r - 1], mul(H[r], F[m - r])));
                    }
                }
                dp[n][k] = mul(inv(n * n), mul(powr(K - k, (n * (n - 1)) / 2 + 1), F[n]));
            }
        }

        if(K <= E + 1) return dp[N][K - 1];
        return lagrange(dp[N], K - 1);
    }
}