In a kingdom, cities are connected by simple roads. To better manage traffic and determine the number of routes possible between cities, the administrator has asked for your help in performing some calculations.

Specifically, the kingdom has ~N~ cities and ~M~ roads. Each road directly connects two cities and has a weight of ~1~. The administrator has prepared a set of queries to calculate specific routes.

For each query, you are given three integers ~u~, ~v~, and ~K~, and you must calculate the number of paths from city ~u~ to city ~v~ with a total weight exactly equal to ~K~. You may revisit the same city multiple times if necessary to achieve the required total weight.

Your task is to help the administrator answer these queries. For each query, compute the number of paths from city ~u~ to city ~v~ with a weight of ~K~, and return the result modulo ~10^9 + 7~.

Input:

1. The first line contains two integers ~N~ and ~M~ ~(M \leq \frac{N(N-1)}{2})~.
2. The next ~M~ lines each contain two integers ~u~ and ~v~, indicating a direct road between city ~u~ and city ~v~ ~(1 \leq u \leq v \leq N)~.
3. The following line contains an integer ~Q~, the number of queries.
4. The next ~Q~ lines each contain three integers ~u~, ~v~, and ~K~, representing a query.

Output:

• ~Q~ lines, each containing an integer: the number of paths from city ~u~ to city ~v~ with a total weight of ~K~, modulo ~10^9 + 7~.

Sample Input

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

Sample Output

3
1

Notes

For query ~1~, the paths are:

• ~1 \to 3 \to 1 \to 3~
• ~1 \to 3 \to 2 \to 3~
• ~1 \to 3 \to 4 \to 3~

For query ~2~, the path is:

• ~2 \to 3 \to 1~

Constraints:

• Subtask ~1~ (~40\%~ of points): ~N, Q, K \leq 10~.
• Subtask ~3~ (~15\%~ of points): ~N \leq 10, K \leq 20,~ and ~Q \leq 10^5~.
• Subtask ~4~ (~15\%~ of points): ~N \leq 100, K \leq 10,~ and ~Q \leq 20~.
• Subtask ~5~ (~15\%~ of points): ~N \leq 100, K \leq 50,~ and ~Q \leq 10^5~.
• Subtask ~6~ (~15\%~ of points): ~N \leq 100, K \leq 10^5,~ and ~Q \leq 10~.