P10326 Freedom (Freedom).

Completely abstract, the **infinite** “freedom” that is only allowed in mathematics. **** “Light of freedom”, the knight of the unknown — Zhi Xiu. Even when facing infinite despair, he can turn it into infinite freedom.

Given a **directed graph** with $n$ nodes and $m$ edges, both nodes and edges have weights. It is guaranteed that for any two nodes $u, v$, there is at most one edge from $u$ to $v$. A **path** $P$ is a node sequence $u_1,\cdots,u_k$, where for any $1\leq i < k$, there is an edge from $u_i$ to $u_{i+1}$ (denote this edge as $e_i$). Define the **edge weight** of $P$ as the product of the weights of all $e_i$, its **node weight** as the sum of the weights of all $u_i$, and its **length** as $k$. In particular, if $k=1$, define its **edge weight** to be $1$. For two paths $P_1, P_2$ with lengths $L_1, L_2$, and node sequences $u_1,\cdots,u_{L_1}$ and $v_1,\cdots,v_{L_2}$ respectively, they are defined to be **the same** if and only if $L_1=L_2$ and $u_i=v_i$ holds for all $1\le i \le L_1$. Given a positive integer $V$, compute the sum of the **edge weights** of all distinct paths whose **node weight** is $V$. The answer may be very large; output it modulo $998244353$. **Input testdata download link: [Link1](https://pan.baidu.com/s/1Gn0T5DNQBwC41oR-0hsh4A), extraction code: `92ih`;** Backup download link and instructions: [Link2](https://www.luogu.com.cn/paste/xkqpnptw).

The first line contains a positive integer $T$, indicating the test point ID. The second line contains three positive integers $n, m, V$, with meanings as described above. The third line contains $n$ positive integers $a_1,\cdots,a_n$, where $a_i$ is the weight of node $i$. The next $m$ lines each contain three positive integers $u_i, v_i, w_i$, indicating that there is an edge from node $u_i$ to node $v_i$ with weight $w_i$.

Output one line with one integer, representing the answer.

[Sample $1$ Explanation] In the sample, $V=12$. The paths whose node weight is $12$ are: (What is given are the node IDs on the path; in the sample, each node’s weight happens to be twice its ID.) - $1 \to 1\to 1\to 1\to 1\to 1$, edge weight is $2^5=32$. - $1\to 1\to 1\to 1 \to 2$, edge weight is $3\times 2^3=24$. - $1\to 2 \to 3$, edge weight is $3\times 5=15$. - $2\to 3\to 1$, edge weight is $5\times 7=35$. - $3\to 1\to 1\to 1$, edge weight is $7\times 2^2=28$. - $3\to 1\to 2$, edge weight is $7\times 3=21$. So the answer is $32+24+15+35+28+21=155$. [Data Information] | Test Point ID | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | Test Point Name | W | K\_1 | K\_2 | K\_3 | MP\_1 | MP\_2 | MP\_3 | MP\_4 | R | Finale | | Score | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | For all testdata, $1\le n \le10^5$, $1\le m \le \min(n^2,10^6)$, $1\le V \le 10^{10000000}$. [Reminder] **Time** is precious. Running code takes time, and your thinking also takes time. Fortunately, these two things can happen at the same time. Hopefully, within this limited time, you can do more and achieve a better score. Translated by ChatGPT 5