Background

This is an output-only problem.

Problem Description

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.

Input Format

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$.

Output Format

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.

3 4 2 10
1 1 2
1 2 2
1 3 1
2 3 3
1 3 5
1 3 3

2
1

Hint

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

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