题目背景

完全抽象的，只在数学中被允许的无限的「自由」。

「自由之光」，未知数的骑士 —— 知修。哪怕面对的是无限的绝望，他也能将其转变为无限的自由。

题目描述

给定一个 $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，提取码：92ih；
备用下载路径与操作方法：Link2。

输入格式

第一行一个正整数 $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$。

输出格式

输出一行一个整数，表示答案。

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

155

提示

【样例 $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\le n \le10^5$，$1\le m \le \min(n^2,10^6)$，$1\le V \le 10^{10000000}$。

【提示】
时间是宝贵的。代码运行需要时间，你的思考也需要时间。好在这两件事可以同时进行，希望你可以在这有限的时间内做更多的事，拿到更好的成绩。