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