#include #define ll long long ll X, Y; void egcd(ll a, ll b) { if (b == 0) { X = 1; Y = 0; } else { egcd(b, a % b); ll T = X - (a / b) * Y; X = Y; Y = T; } } ll inv(ll a, ll n) { if (a < 0) a += n; egcd(a, n); if (X < 0) X += n; return X % n; } #define N 111 int n, e, x; ll k; ll adj[N][N]; ll adj1[N][N]; ll adj2[N][N]; ll temp1[N][N]; ll temp2[N][N]; #define lap temp1 #define olap temp2 // add identity #define madd_iden(a) do {\ for (int i = 0; i < n; i++) {\ a[i][i]++;\ }\ } while (0) // clear matrix #define mclear(m) do {\ for (int i = 0; i < n; i++) {\ for (int j = 0; j < n; j++) {\ m[i][j] = 0;\ }\ }\ } while (0) // a = a * adj #define mmul_adj(a) do {\ mclear(temp2);\ for (int i = 0; i < n; i++) {\ for (int k = 0; k < n; k++) {\ if (adj[i][k]) {\ for (int j = 0; j < n; j++) {\ temp2[i][j] += a[k][j];\ }\ }\ }\ }\ for (int i = 0; i < n; i++) {\ for (int j = 0; j < n; j++) {\ a[i][j] = temp2[i][j] % x;\ }\ }\ } while (0) // a = a * temp1 #define mmul(a) do {\ mclear(temp2);\ for (int i = 0; i < n; i++) {\ for (int k = 0; k < n; k++) {\ ll v = a[i][k];\ if (v) {\ for (int j = 0; j < n; j++) {\ temp2[i][j] += v * temp1[k][j];\ }\ }\ }\ for (int j = 0; j < n; j++) {\ a[i][j] = temp2[i][j] % x;\ }\ }\ } while (0) // computes adj1 = adj^k and adj2 = adj^(k-1) + adj^(k-2) + ... + adj^1 + adj^0 void mgeom(ll k) { if (k == 1) { return; } else if (k & 1) { mgeom(k-1); mmul_adj(adj1); mmul_adj(adj2); madd_iden(adj2); } else { mgeom(k>>1); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { temp1[i][j] = adj1[i][j]; } } mclear(temp2); mmul(adj1); madd_iden(temp1); mmul(adj2); } } // computes the determinant of 'olap' modulo prime p ll compute_det(ll p) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { lap[i][j] = olap[i][j]; } } ll det = 1; for (int i = 0; i < n; i++) { int m = i; while (m < n && lap[m][i] == 0) m++; if (m == n) return 0; if (m != i) for (int j = i; j < n; j++) { ll temp = lap[i][j]; lap[i][j] = lap[m][j]; lap[m][j] = temp; } ll sc = lap[i][i]; det *= sc; det %= p; sc = inv(sc, p); for (int j = i; j < n; j++) { lap[i][j] *= sc; lap[i][j] %= p; } for (int j = i+1; j < n; j++) { sc = lap[j][i]; if (sc) for (int k = i; k < n; k++){ lap[j][k] -= sc * lap[i][k]; lap[j][k] %= p; } } } if ((det %= p) < 0) det += p; return det; } // operations for big numbers in base 'BASE', represented as arrays #define BASE 1000000000 // A *= v, where v ~ BASE #define vmul(A,v) do {\ ll carry = 0;\ for (int i = 0; i < A##d; i++) {\ A[i] *= v;\ A[i] += carry;\ carry = A[i] / BASE;\ A[i] %= BASE;\ }\ while (carry) {\ A[A##d++] = carry % BASE;\ carry /= BASE;\ }\ } while (0) // A += B #define vadd(A,B) do {\ while (A##d < B##d) A[A##d++] = 0;\ while (B##d < A##d) B[B##d++] = 0;\ ll carry = 0;\ for (int i = 0; i < A##d; i++) {\ A[i] += B[i];\ A[i] += carry;\ carry = A[i] / BASE;\ A[i] %= BASE;\ }\ while (carry) {\ A[A##d++] = carry % BASE;\ carry /= BASE;\ }\ } while (0) // A = B #define vcopy(A,B) do {\ for (int i = 0; i < B##d; i++) A[i] = B[i];\ A##d = B##d;\ } while (0) // primes #define PC 112 ll ps[PC] = {1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103, 1000000123, 1000000181, 1000000207, 1000000223, 1000000241, 1000000271, 1000000289, 1000000297, 1000000321, 1000000349, 1000000363, 1000000403, 1000000409, 1000000411, 1000000427, 1000000433, 1000000439, 1000000447, 1000000453, 1000000459, 1000000483, 1000000513, 1000000531, 1000000579, 1000000607, 1000000613, 1000000637, 1000000663, 1000000711, 1000000753, 1000000787, 1000000801, 1000000829, 1000000861, 1000000871, 1000000891, 1000000901, 1000000919, 1000000931, 1000000933, 1000000993, 1000001011, 1000001021, 1000001053, 1000001087, 1000001099, 1000001137, 1000001161, 1000001203, 1000001213, 1000001237, 1000001263, 1000001269, 1000001273, 1000001279, 1000001311, 1000001329, 1000001333, 1000001351, 1000001371, 1000001393, 1000001413, 1000001447, 1000001449, 1000001491, 1000001501, 1000001531, 1000001537, 1000001539, 1000001581, 1000001617, 1000001621, 1000001633, 1000001647, 1000001663, 1000001677, 1000001699, 1000001759, 1000001773, 1000001789, 1000001791, 1000001801, 1000001803, 1000001819, 1000001857, 1000001887, 1000001917, 1000001927, 1000001957, 1000001963, 1000001969, 1000002043, 1000002089, 1000002103, 1000002139, 1000002149, 1000002161, 1000002173, 1000002187, 1000002193, 1000002233, 1000002239, 1000002277, 1000002307}; ll ds[PC]; ll det[PC+9], prod1[PC+9], prod2[PC+9]; int detd = 0, prod1d = 0, prod2d = 0; int main() { scanf("%d%d%d%lld\n", &n, &e, &x, &k); // compute adj for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { adj[i][j] = 0; } } while (e--) { int a, b; scanf("%d%d", &a, &b); a--, b--; adj[a][b]++; adj[b][a]++; } // initialize for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { temp1[i][j] = temp2[i][j] = 0; adj1[i][j] = adj[i][j]; adj2[i][j] = i == j; } } // compute number of paths of length at most k mgeom(k+1); // compute laplacian matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { olap[i][j] = 0; } for (int j = 0; j < n; j++) { olap[i][i] += adj2[i][j]; olap[i][j] -= adj2[i][j]; } } n--; // compute determinant prod1[prod1d++] = prod2[prod2d++] = 1; for (int I = 0; I < PC; I++) { // garner's algorithm: compute I'th digit ll v = compute_det(ps[I]); ll pr = 1; ll total = 0; for (int j = 0; j < I; j++) { total += pr * ds[j]; total %= ps[I]; pr *= ps[j]; pr %= ps[I]; } ds[I] = (v - total) * inv(pr, ps[I]) % ps[I]; if (ds[I] < 0) ds[I] += ps[I]; // adjust big determinant vmul(prod1,ds[I]); vadd(det,prod1); vcopy(prod1,prod2); vmul(prod1,ps[I]); vcopy(prod2,prod1); } // print determinant bool found = false; if (detd == 0) det[detd++] = 0; for (int i = detd-1; i >= 0; i--) { if (found) { printf("%09lld", det[i]); } else if (det[i]) { printf("%lld", det[i]); found = true; } } if (!found) printf("0"); puts(""); }