Sum of Edge Products on Paths with Given Vertex Sum

You are given a directed graph with n vertices and m edges. Each vertex has a weight and each edge has a weight. It is guaranteed that there is at most one edge from vertex u to vertex v for any two vertices.

A path P is defined as a sequence of vertices \(u_1, u_2, \ldots, u_k\) such that for each \(1 \le i < k\) there exists a directed edge from \(u_i\) to \(u_{i+1}\) (denote this edge as \(e_i\)). The edge weight of the path is defined as the product of the weights of all \(e_i\) (and if \(k=1\), i.e. a trivial path with a single vertex, its edge weight is defined to be \(1\)). The vertex weight of the path is the sum of the weights of all vertices in the path. The length of the path is \(k\). Two paths \(P_1\) and \(P_2\) (with lengths \(L_1\) and \(L_2\) and vertex sequences \(u_1,\ldots,u_{L_1}\) and \(v_1,\ldots,v_{L_2}\), respectively) are considered identical if and only if \(L_1 = L_2\) and \(u_i = v_i\) for every \(1 \le i \le L_1\).

Given a positive integer \(V\), your task is to compute the sum of the edge weights of all distinct paths whose vertex weight equals \(V\). Since the answer might be very large, output the result modulo \(998244353\).

Input data download link: Link1 (extraction code: 92ih); Alternate download link and instructions: Link2.

inputFormat

The first line contains three integers \(n\), \(m\), and \(V\) (the number of vertices, the number of edges, and the target vertex weight sum, respectively).

The second line contains \(n\) integers: the weights of the vertices \(w_1, w_2, \ldots, w_n\).

Then follow \(m\) lines, each containing three integers \(u\), \(v\), and \(w_e\) indicating that there is a directed edge from vertex \(u\) to vertex \(v\) with weight \(w_e\).

It is guaranteed that there is at most one edge from any vertex \(u\) to any vertex \(v\).

outputFormat

Output a single integer --- the sum of the edge weights of all distinct paths whose vertex weight equals \(V\), taken modulo \(998244353\).

sample

3 3 6
1 2 3
1 2 2
2 3 3
1 3 5

6