邻接矩阵+矩阵快速幂 可以求i点到其他点的方案数

矩阵：a,c
c=a*a
矩阵a的第i行k列 * a的k行j列 （!=0的话）
表示i点可以到达k点，而k点又可以到达j点,即i点可以到达j点
所以c[i][j] (c的i行j列)表示i到j(是否可行）或方案数
//

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e2+7;
int const mod=1000000007;
int n,m,k,s;
struct mat{
    ll a[N][N];
    mat(){
        memset(a,0,sizeof a);  //这里一定要初始化 
    }
    void init(){
        for(int i=1;i<=n;++i){
            a[i][i]=1;
        }
    }
    mat operator*(mat const &b){
        mat res;
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                for(int k=1;k<=n;++k){
                    res.a[i][j]=(res.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
                }
            }
        }
        return res;
    }
}mr,z;
mat ksm(mat a,ll b){
    mat res;res.init();
    while(b){
        if(b&1) res=res*a;
        a=a*a;
        b >>= 1;
    }
    return res;
} 
int main(){
    cin >> n >> m >> k >> s;
    for(int i=1;i<=m;++i){
        int b,c;
        cin >> b >> c;
        mr.a[b][c]++;
    }
    z=ksm(mr,k);
    ll ans=0;
    for(int j=1;j<=n;++j){
        if( z.a[s][j]&&j!=s ) ans+=z.a[s][j]%mod;
    }
    cout << ans%mod;
    return 0;
}