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

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

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

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

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

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

然后一个正整数k（k<=n*n），表示查询次数。

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

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