8362: BZOJ4362:Graph
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
给出一张n个点的有向图G(V,E)。对于任意两个点u,v(u可以等于v),u向v的连边数为: ∑OUT(u,i) * IN(v,i),其中1<=i<=K 其中k和数组out,in均已知,现在给出m个询问,每次询问给出三个参数u,v,d,你需要回答从节点 u出发,经过不超过d条边到达节点v的路径有多少种。答案模10^9+7。
输入格式
第一行两个整数n,k。 接下来n行,第i行有2k个整数,前k个整数描述outi,后k个数描述ini。 接下来一行一个整数m。 接下来m行,每行三个整数u,v,d(0<=d<2^31),描述一组询问。
输出格式
对于每个询问,输出一行一个整数,描述答案。
样例输入
5 2 2 5 4 3 7 9 2 4 0 1 5 2 6 3 9 2 2147483647 1000000001 233522788488 10 1 1 0 2 2 1 2 4 5 4 3 10 3 4 50 1 5 1000
样例输出
1 51 170107227 271772358 34562176 890241289
提示
1<=N<=1000 1<=K<=20 1<=M<=50
题目来源
没有写明来源