If we examine the adjacency matrix of the graph given, along with how the state of the graph changes after this matrix is applied some number of times, we notice that the adjacency matrix can first be multiplied by itself some number of times before it is applied to the state of the graph for the same result. After multiplying the matrix by itself some number of times for each query, apply it to the initial state of the graph where node ~(1,a)~ has a source of ~a~ in the first row, and there is ~1~ way to travel there. To apply a matrix, relax all existing edges.

Fast matrix exponentiation on the adjacency matrix, where coordinate ~(x,y)~ of the matrix represents the number of ways to move to ~y~, starting from ~x~, yields an ~\mathcal O(QN^3\log(q^{max}))~ solution. This is still inadequate for the time limit, so notice that it only takes ~\mathcal O(N^2)~ time to apply a matrix. By precomputing all matrices which are the adjacency matrix raised to some power of 2 (up to ~10^{13}~), several matrices can be applied per query in ~\mathcal O(N^2)~ time each, and each query can be answered using ~\mathcal O(\log(q_i))~ matrix applications.

The final time complexity is ~\mathcal O(N^3\log(q^{max}) + QN^2\log(q^{max}))~.

It should also be noted that, very occasionally, a matrix result will be non-zero and be divisible by ~10^9+7~. This could cause an incorrect answer when applying the matrix to the state of the graph, which can be prevented by maintaining a boolean matrix in parallel with the adjacency matrix to represent which nodes can reach which other nodes. Since this collision usually requires the matrix to be raised to a relatively high exponent, there is another small chance that this will affect the answer. However, with such a large modulo value, such cases are rare and absent in the test data.