记录编号	606672	评测结果	AAAAAAAAAA
题目名称	3946.信使	最终得分	100
用户昵称	郑霁桓	是否通过	通过
代码语言	C++	运行时间	7.377 s
提交时间	2025-10-01 17:24:13	内存使用	10.46 MiB

#include<bits/stdc++.h> 
using namespace std;
long long n,m,M,x,y,z;
long long f[55][105][105],s[55][105][105],a[55][105][105];
vector<long long>v[105];
inline int read()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
inline void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
int main(){
    freopen("messenger.in","r",stdin);
    freopen("messenger.out","w",stdout);
    n=read(),m=read(),M=read();
    for(register int i=1;i<=m;i++) x=read(),y=read(),v[x].push_back(y);
    for(int i=1;i<=n;i++) f[0][i][i]=1;
    for(int i=0;i<50;i++) for(int j=1;j<=n;j++) for(int k=0;k<v[j].size();k++) for(int l=1;l<=n;l++)
        f[i+1][j][l]+=f[i][v[j][k]][l],f[i+1][j][l]%=M;
    for(int d=0;d<=50;d++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) continue;
                a[d][i][j]=f[d][i][i],s[d][i][j]=f[d][i][j];
                for(int k=1;k<d;k++){
                    a[d][i][j]-=s[k][i][j]*f[d-k][j][i]%M+a[k][i][j]*f[d-k][i][i]%M;
                    s[d][i][j]-=a[k][i][j]*f[d-k][i][j]%M+s[k][i][j]*f[d-k][j][j]%M;
                    a[d][i][j]=(a[d][i][j]%M+M)%M,s[d][i][j]=(s[d][i][j]%M+M)%M;
                }
            }
        }
    }
    m=read();
    while(m--) x=read(),y=read(),z=read(),cout<<(s[z][x][y]%M+M)%M<<"\n";
    return 0;
}