#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; ll MOD; vector> matrixmul(int l, int m, int n, vector> a, vector> b){ vector> c(l, vector(n)); for(int i=0; i> matrixpow(int n, vector> a, ll k){ vector> ap=a, ans(n, vector(n)); for(int i=0; i>=1; } return ans; } int main() { int n, m; ll t; cin>>n>>m>>t; vector> mat(n, vector(n)); for(int i=0; i>a>>b; mat[a][b]++; } bool ok[101]; fill(ok, ok+n, 1); random_device rd; mt19937 mt(rd()); uniform_int_distribution rnd(900000000, 1000000000); for(int loop=0; loop<2; loop++){ MOD=rnd(mt); auto matp=matrixpow(n, mat, t); for(int i=0; i