Problem 26850 --收集数码晶体

26850: 收集数码晶体

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 241  Solved: 45
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][76kb]

Description

数码世界的国王Shoutmon想要在n个小岛上举办一个游戏,来让数码宝贝们好好玩耍。背景是这样的:在这n个小岛之间事先安放了一些单向通道,每个通道连接两个不同的小岛,且只能按一个给定的方向通过。数码宝贝每次由通道到达一个小岛时都会令体内增加一个“数码晶体”。

Shoutmon制定了一项规则,即数码宝贝们可以从某个小岛出发,到达一个目的小岛,如果到达目的小岛后体内的“数码晶体”数量恰好为L,那么此时可以在小岛上的兑奖处领取奖品(领完奖品后自动退出游戏)。注意,到达目的小岛后如果“数码晶体”数量不足,那么仍然可以离开小岛,直到某次回到目的小岛时“数码晶体”的数量恰好为L。每个小岛(包括起始小岛和目的小岛)与每条通道都不限制到达和通过次数。初始状态下体内的“数码晶体”数量为0

为了保证活动正常进行,Shoutmon想要知道,有多少条路径可以从起始小岛S到达目的小岛T并领奖(可能有多次查询)。

Input

每个输入文件中一组数据。

第一行三个整数nmL2<=n<=300<=m<=n*(n-1)1<=L<=100),分别代表小岛个数、单向通道条数、恰好需要的“数码晶体”数。

接下来m行,每行两个整数uv,代表从小岛u到小岛v有一条单向通道(假设小岛编号为从0n-1)。数据保证u不等于v,且相同的有序对(u,v)最多出现一次。

然后一个正整数kk<=n*n),表示查询次数。

接着k行,每行两个整数ST,表示需要查询有多少条路径可以从起始小岛S到达目的小岛T并领奖。

Output

输出k行,每行一个整数,对应查询的结果,即从起始小岛到达目的小岛并领奖的路径条数。由于路径条数可能很多,因此将结果模上1000000007

Sample Input

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

Sample Output

0
2
1

HINT

Source

[Submit][Status]