P5418 [CTSC2016] NOIP十合一（数据疑似有误）

这是一道 **提交答案题**。

在 NOIP2044 的赛场上，小 D 遇到了这样一道题： 给出一个 $n$ 个点的图，其中有 $m$ 条带边权的有向边，有 $q$ 个询问，每个询问形如从 $u$ 号点走到 $v$ 号点，长度为 $w$ 的道路数量有多少？你只需要输出答案对 $P$ 取模的结果即可。 小 D 思考了良久也不会做这道题，悻悻离场后，他从官网上取得了这道题的数据，共有 $10$ 组数据。小 D 怎么也想做出来这道题，于是他开始寻求你的帮助，将 $10$ 组数据的输入给了你。聪明的你一定可以帮小 D 计算出每组数据的输出的！

无

无

### 样例一解释： 对于第一组询问，一共有两条从 $1$ 号点到 $3$ 号点、长度为 $5$ 的路径。假定边的编号从 $1$ 到 $4$，则这两条路径经过的边为： 第 $1$ 条：$2 \rightarrow 4$ 第 $2$ 条：$1 \rightarrow 1 \rightarrow 3$。 ### 有关其他样例 在测试数据下载中提供了每个测试点对应的sampleout，分别对应每个测试点第一个询问的正确输出 ### 输入数据下载 [下载链接](https://share.weiyun.com/5sk5wqh) ### 评分办法 暂无spj，按照 **传统题** 评分办法进行评测，只有你的答案与标准输出 **完全相同** 才能得到测试点的分数 ### 提示 本题可能用到的知识： **特征多项式**：对于 $n \times n$ 的矩阵 $A$，定义以 $\lambda$ 为变量的 $n$ 次多项式 $f(\lambda)=\det(\lambda I-A)$，其中 $I$ 是 $n$ 阶单位矩阵，$\det$ 是行列式。称 $f(\lambda)$ 为 $A$ 的特征多项式。 **Cayley-Hamilton 定理**：对于方阵 $A$ 的特征多项式 $f(\lambda)$，一定有 $f(A)=0$。即将矩阵本身作为变量带入特征多项式，结果为零矩阵。