Background

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.

Problem Description

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, extraction code: 92ih;
Backup download link and instructions: Link2.

Input Format

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 Format

Output one line with one integer, representing the answer.

0
3 5 12
2 4 6
2 3 5
1 2 3
3 1 7
3 2 11
1 1 2

155

Hint

[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]

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