自由（Freedom）

完全抽象的，只在数学中被允许的**无限**的「自由」。 **** 「自由之光」，未知数的骑士 —— 知修。哪怕面对的是无限的绝望，他也能将其转变为无限的自由。

给定一个 $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)。

第一行一个正整数 $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 | 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}$。 【提示】 **时间**是宝贵的。代码运行需要时间，你的思考也需要时间。好在这两件事可以同时进行，希望你可以在这有限的时间内做更多的事，拿到更好的成绩。