给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。
刷AC自动机的时候用到这种思想了才刷的这道题.
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define rep(i,aa,n) for (int i=aa;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define oo cout<<"!!!"<<endl;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
//head//HDU 2157.离散数学里的一个结论.AC自动机那几道题的解法来源于这道题const int maxn = 111;
const int mod = 1000;
struct matrix
{int m[maxn][maxn];
};matrix mul(matrix a,matrix b,int sz)
{matrix c;rep(i,0,sz)rep(j,0,sz){c.m[i][j] = 0;rep(k,0,sz)c.m[i][j] = (c.m[i][j] + a.m[i][k]*b.m[k][j]) % mod;}return c;
}matrix pow(matrix a,int n,int sz)
{matrix res;rep(i,0,sz)rep(j,0,sz)res.m[i][j] = i==j;while(n){if(n & 1)res = mul(a,res,sz);a = mul(a,a,sz);n >>= 1;}return res;
}int main()
{int n,m,q;while(cin>>n>>m,n||m){int x,y;matrix mat;ms(mat.m);rep(i,0,m)cin>>x>>y,mat.m[x][y]=1;cin>>q;int a,b,k;while(q--){cin>>a>>b>>k;matrix ans = pow(mat,k,n);cout<<ans.m[a][b]<<endl;}}return 0;
}