【題解】Codeforces GYM 102644D. Count Paths

#include <iostream>
using namespace std;
 
long long n, m, k, x, y, a[105][105], ans[105], mod = 1e9+7;
 
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++){
        ans[i] = 1;
    }
    for (int i = 0; i < m; i++){
        cin >> x >> y;
        x--;
        y--;
        a[y][x] = 1;
    }
    while (k){
        if (k & 1){
            long long tmp[105] = {};
            for (int i = 0; i < n; i++){
                for (int k = 0; k < n; k++){
                    tmp[i] += a[i][k]*ans[k];
                    tmp[i] %= mod;
                }
            }
            for (int i = 0; i < n; i++){
                ans[i] = tmp[i];
            }
        }
        long long tmp[105][105] = {};
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                for (int k = 0; k < n; k++){
                    tmp[i][j] += a[i][k]*a[k][j];
                    tmp[i][j] %= mod;
                }
            }
        }
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                a[i][j] = tmp[i][j];
            }
        }
        k >>= 1;
    }
    for (int i = 1; i < n; i++){
        ans[0] += ans[i];
        ans[0] %= mod;
    }
    cout << ans[0] << "\n";
}