Chains of flights

counting graph matrix divide and conquer precomputation contests

Flights run between n airports. From airport a to airport b there may be several, different callsigns, and each counts as a separate way to make that flight. A chain is a sequence of exactly k flights, each next one departing from where the previous one arrived; airports in a chain may repeat.

Answer q questions: how many chains of exactly k flights lead from s to t? The numbers are huge, so print the remainder modulo 10⁹ + 7.

The second example is the real network of flights between 21 airports (the Virtual Radar Server callsign database, CC0, snapshot of 10.10.2026); airport 1 is Almaty, 5 is Astana.

Input

The first line holds n and m (1 ≤ n ≤ 30, 0 ≤ m ≤ n²). Then m lines a b c: c callsigns fly from a to b (1 ≤ c ≤ 10⁹); a pair may occur several times, in which case the callsigns add up, and a flight may lead to the same airport. Then q (1 ≤ q ≤ 200) and q lines s t k (0 ≤ k ≤ 10¹⁸).

Output

For each question, the number of chains modulo 10⁹ + 7. For k = 0 the chain is empty: the answer is 1 if s = t, and 0 otherwise.

Examples

Example 1

Input

Output

2
2
0

Example 2

Input

21 108
1 2 1
1 3 1
1 5 72
1 6 5
1 7 2
1 8 2
1 9 23
1 10 6
1 11 3
1 12 14
1 13 11
1 14 9
1 15 8
1 16 8
1 17 8
1 18 20
1 19 14
1 20 9
1 21 7
2 1 1
3 1 1
4 5 2
5 1 75
5 4 2
5 7 1
5 8 3
5 9 17
5 10 1
5 11 1
5 13 7
5 14 4
5 15 8
5 16 4
5 17 3
5 18 8
5 19 7
5 20 7
5 21 7
6 1 5
6 18 1
7 1 2
7 5 1
7 9 1
8 1 2
8 5 4
8 20 1
8 21 1
9 1 24
9 5 25
9 6 1
9 7 1
9 12 1
9 15 3
9 16 1
9 17 2
9 18 3
9 19 1
9 20 2
9 21 2
10 1 6
10 5 1
10 21 1
11 1 3
11 5 1
12 1 15
12 9 1
13 1 11
13 5 7
13 19 1
14 1 8
14 5 3
14 18 3
14 19 1
15 1 8
15 5 7
15 9 3
16 1 8
16 5 4
16 9 2
17 1 7
17 5 4
17 9 2
18 1 21
18 5 8
18 6 1
18 9 5
18 14 3
18 19 11
18 20 2
19 1 14
19 5 6
19 9 2
19 13 1
19 14 2
19 18 10
19 20 1
20 1 9
20 5 9
20 8 1
20 9 2
20 18 1
20 19 1
21 1 6
21 5 7
21 8 1
21 9 1
21 10 1
21 20 2
5
1 5 1
1 5 2
1 1 2
1 5 10
1 1 1000000000000000000

Output

Limits

Time · Python: 6000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

How many chains of two flights lead from s to t? Go over the transfer airport and see what the resulting sum looks like.

2Hint 2

The answer to a question is an entry of the matrix C^k, and it can be raised to the power in fewer than 120 products. But there are two hundred questions. Does each question need the whole matrix?

3The idea

By the claim in the article, the number of chains is (C^k)_st, where C_ab is the number of callsigns from a to b. Raising C to the power anew for every question is about 200 · 90 products of n³ multiplications each, too much for Python. But the powers of two C, C², C⁴, …, C^2⁵⁹ do not depend on the question: compute them once. And a question needs one row of C^k: start with a vector that has a one at s and multiply it by the powers of two whose bits are set in k. A vector times a matrix is n², not n³.

4Walkthrough

Add the callsigns into a matrix modulo the prime. Precomputation: 59 squarings. A question: the vector e_s, a pass over the bits of k from the lowest: if a bit is set, multiply the vector by the corresponding power. Matrix multiplications cannot be reordered in general, but here all the factors are powers of the one matrix C, and they commute with each other, so the order of the bits does not matter. The answer is coordinate t of the vector.

The second example shows how the numbers grow: from Almaty to Astana in two flights there are 1192 chains, and in ten 38,516,548,485,362,965,772, already more than fits in 64 bits; that is why the remainder is taken after each multiplication.

4+Solution

5Complexity

Precomputation is 60·n³ ≈ 1.6·10⁶ multiplications, each question at most 60·n², all questions about 10⁷. Naive exponentiation per question is 200·90·n³ ≈ 5·10⁸.

6Common mistakes

The power anew for each question. Correct, but dozens of times slower: the sixth test does not fit in the time limit in Python.
Overflow. The product of two remainders is up to 10¹⁸, and a sum of thirty of them exceeds 2⁶³. In Go and C++ the remainder has to be taken after each term.
Repeated pairs. Two lines with the same pair a, b are a sum of callsigns, not a replacement.
k = 0. There is one empty chain, from an airport to itself.

Algorithms behind it

NUM Algorithm Matrices and recurrences A matrix power: walks of length k in a graph, linear recurrences, the transfer matrix and Markov chains. O(m³ log k) for A^k of size m × m 2 problems NUM Algorithm Fast exponentiation aⁿ in O(log n) multiplications: squares over the bits of the exponent. O(log n) multiplications 2 problems