P5418 [CTSC2016] NOIP Ten-in-One (The testdata seems to be incorrect)

This is an output-only problem.

At the contest site of NOIP2044, Little D encountered the following problem: You are given a graph with $n$ vertices, $m$ directed edges with weights, and $q$ queries. Each query asks: how many paths are there from vertex $u$ to vertex $v$ with total length $w$? You only need to output the answer modulo $P$. Little D thought for a long time but still could not solve it. After leaving in disappointment, he obtained the testdata for this problem from the official website. There are $10$ test cases in total. Little D really wants to solve this problem, so he asks for your help and gives you the input of these $10$ test cases. You, being smart, can surely help Little D compute the output for each test case.

The input files noip1.in~noip10.in are already included in the download package. The first line of each input file contains $4$ positive integers $n,m,q,P$, representing the number of vertices, the number of edges, the number of queries, and the modulus. The vertices are numbered as integers from $1$ to $n$. The next $m$ lines describe the weighted directed edges. In the $i$-th line there are $3$ integers $a_i,b_i,c_i$, meaning the $i$-th edge starts at $a_i$, ends at $b_i$, and has weight $c_i$. The next $q$ lines describe the queries. In the $k$-th line there are $3$ integers $u_k,v_k,w_k$, meaning the $k$-th query asks for the number of paths from vertex $u_k$ to vertex $v_k$ with total length $w_k$, modulo $P$.

The output files are noip1.out~noip10.out, corresponding to the respective input files. Each output file contains at most $q$ lines. Each line contains a non-negative integer less than $P$, representing the answers to the first $q$ queries of that test case.

### Explanation for Sample 1: For the first query, there are exactly two paths from vertex $1$ to vertex $3$ with length $5$. Assume the edges are numbered from $1$ to $4$. Then the edges passed by these two paths are: Path $1$: $2 \rightarrow 4$ Path $2$: $1 \rightarrow 1 \rightarrow 3$. ### About the other samples The download package provides sampleout for each test case, which corresponds to the correct output for the first query of each test case. ### Input data download [Download link](https://share.weiyun.com/5sk5wqh) ### Scoring There is no special judge. The judging follows the **traditional problem** scoring method. You get points for a test case only if your output is **exactly the same** as the standard output. ### Notes This problem may use the following knowledge: **Characteristic polynomial**: For an $n \times n$ matrix $A$, define an $n$-th degree polynomial in $\lambda$ as $f(\lambda)=\det(\lambda I-A)$, where $I$ is the $n \times n$ identity matrix and $\det$ is the determinant. We call $f(\lambda)$ the characteristic polynomial of $A$. **Cayley-Hamilton theorem**: For the characteristic polynomial $f(\lambda)$ of a square matrix $A$, we always have $f(A)=0$. That is, if we substitute the matrix itself into the characteristic polynomial, the result is the zero matrix. Translated by ChatGPT 5