J19 例题-5 校园小路

题目描述

春天到了，校园里开满了花， 姹紫嫣红，非常美丽。葱头是个爱花的人，看着校花校草竞相开放，漫步校园，心情也变得舒畅。为了多看看这迷人的校园， 葱头决定，每次上课都走不同的路线去教室，但是由于时间问题，每次只能经过k个地方，比方说，这次葱头决定经过 $2$ 个地方，那他可以先去问鼎广场看看喷泉，再去教室，也可以先到体育场跑几圈，再到教室。他非常想知道，从 $A$ 点恰好经过 $k$ 个点到达 $B$ 点的方案数, 当然这个数有可能非常大, 所以你只要输出它模上 $1000$ 的余数就可以了。你能帮帮他么?? 你可决定了葱头一天能看多少校花哦。

输入格式

输入数据有多组, 每组的第一行是 $2$ 个整数 $n, m$，表示校园内共有 $n$ 个点, 为了方便起见, 点从 $0$ 到 $n-1$ 编号,接着有 $m$ 行, 每行有两个整数 $s, t$ ( $0 \le s,t< n$) 表示从 $s$ 点能到 $t$ 点, 注意图是有向的。 接着的一行是两个整数 $T$，表示有 $T$组询问, 接下来的 $T$ 行, 每行有三个整数 $A, B, k$, 表示问你从 $A$ 点到 $B$ 点恰好经过 $k$ 个点的方案数, 可以走重复边。如果不存在这样的走法, 则输出 $0$ 。 当 $n, m$ 都为 $0$ 的时候输入结束。

输出格式

计算每次询问的方案数，由于走法很多，输出其对 $1000$ 取模的结果。

样例输入

4 4
0 1
0 2
1 3
2 3
2
0 3 2
0 3 3
3 6
0 1
1 0
0 2
2 0
1 2
2 1
2
1 2 1
0 1 3
0 0

样例输出

2
0
1
3

样例分析

如上所述。

数据范围

$100\%$ 的数据：$1 \le T \le 100$, $0 \lt n \le 20, m \le 100$, $k < 20$。