给定一个 $n$ 个节点、$m$ 条边的**有向图**，节点和边都有权值，保证对于任意两个节点 $u,v$，从 $u$ 指向 $v$ 的边最多只有一条。
**路径** $P$ 是一个节点序列 $u_1,\cdots,u_k$，其中对于任意 $1\leq i < k$，$u_i$ 有指向 $u_{i+1}$ 的边（这条边记为 $e_i$）。则定义 $P$ 的**边权**是所有 $e_i$ 的权值的乘积，其**点权**是所有 $u_i$ 权值的和，其**长度**为 $k$。特别地，如果 $k=1$，则定义其**边权**为 $1$。
对于两条路径 $P_1,P_2$，长度分别为 $L_1,L_2$，包含的节点序列记为 $u_1,\cdots,u_{L_1}$ 和 $v_1,\cdots,v_{L_2}$。定义它们是**相同**的，当且仅当 $L_1=L_2$，且对于所有 $1\le i \le L_1$ 有 $u_i=v_i$。
给定正整数 $V$，请求出所有不相同的「**点权**为 $V$ 的路径」的**边权**之和。答案可能很大，请对 $998244353$ 取模后输出。
**题目的输入数据下载链接：[Link1](https://pan.baidu.com/s/1Gn0T5DNQBwC41oR-0hsh4A)，提取码：`92ih`；**
备用下载路径与操作方法：[Link2](https://www.luogu.com.cn/paste/xkqpnptw)。
## Input
第一行一个正整数 $T$，表示测试点编号。
第二行三个正整数 $n,m,V$，意义如题目描述。
第三行 $n$ 个正整数 $a_1,\cdots,a_n$，$a_i$ 表示了编号为 $i$ 的节点的权值。
接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，表示编号为 $u_i$ 的点有一条权值为 $w_i$ 的边指向 $v_i$。
## Output
输出一行一个整数，表示答案。
[samples]
## Background
完全抽象的，只在数学中被允许的**无限**的「自由」。
****
「自由之光」，未知数的骑士 —— 知修。哪怕面对的是无限的绝望，他也能将其转变为无限的自由。
## Note
【样例 $1$ 解释】
样例中 $V=12$，满足点权为 $12$ 的路径有：
（给出的是路径中节点的编号，样例中每个节点的权值恰好为其编号的两倍）
- $1 \to 1\to 1\to 1\to 1\to 1$，边权为 $2^5=32$。
- $1\to 1\to 1\to 1 \to 2$，边权为 $3\times 2^3=24$。
- $1\to 2 \to 3$，边权为 $3\times 5=15$。
- $2\to 3\to 1$，边权为 $5\times 7=35$。
- $3\to 1\to 1\to 1$，边权为 $7\times 2^2=28$。
- $3\to 1\to 2$，边权为 $7\times 3=21$。
故答案为 $32+24+15+35+28+21=155$。
【数据信息】
| 测试点编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| 测试点名称 | W | K\_1 | K\_2 | K\_3 | MP\_1 | MP\_2 | MP\_3 | MP\_4 | R | Finale |
| 测试点分数 | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ | $10$ |
对于全部的数据，$1\le n \le10^5$，$1\le m \le \min(n^2,10^6)$，$1\le V \le 10^{10000000}$。
【提示】
**时间**是宝贵的。代码运行需要时间，你的思考也需要时间。好在这两件事可以同时进行，希望你可以在这有限的时间内做更多的事，拿到更好的成绩。