救赎之道，就在其中

L 来到了一座罪恶之国。罪恶之国由 $n$ 个城市和 $m$ 条单向道路组成，其中没有一条路径能经过一个城市两次，并且任何两个城市之间最多只有一条直接连接的道路。

罪恶之国的每个城市都有一个罪恶值 $a_i$。L 希望离开这里，不幸的是，当 L 的罪恶值超过 $k$ 时，L 将永远留在这个国家。L 可以选择从任何城市出发，并且他初始的罪恶值为出发城市的罪恶值 $a_i$。之后每当 L 到达一座城市时，L 的罪恶值将会乘上该城市的罪恶值 $a_i$。

L 因为天天“云顶，启动！”，所以已经不想动脑了。于是 L 来问你，一共有多少条不同的路径，使得 L 的罪恶值最后不超过 $k$。两条路径不同当且仅当其对应的城市序列不同，且允许存在起点和终点相同的路径。

请输出答案对 $998244353$ 取模后的结果。

测试点包含多组数据。第一行包含一个整数 $T$（$1\leq T\leq5$），表示数据组数。每组数据输入格式如下：

第一行包含三个整数 $n$，$m$ 和 $k$（$1\leq n,m\leq1000$，$1\leq k\leq10^9$），分别表示城市的数量、道路的数量和罪恶值的上限。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\leq a_i\leq10^9$），分别表示每个城市的罪恶值。

接下来 $m$ 行，每行包含两个不同的整数 $u$ 和 $v$（$1\leq u,v\leq n$），表示存在一条 $u$ 到 $v$ 的单向道路，保证没有一条路径能经过一个城市两次，并且任何两个城市之间最多只有一条直接连接的道路。

每组数据包含一个整数，表示路径数量对 $998244353$ 取模后的结果。

1
4 6 99999999  
100 100 100 100  
1 2  
1 3  
2 3  
3 4  
2 4  
1 4

14

样例中，共有 $14$ 条合法路径，分别是 $[1,2,3]$、$[1,2,4]$、$[1,3,4]$、$[2,3,4]$、$[1,2]$、$[1,3]$、$[1,4]$、$[2,3]$、$[2,4]$、$[3,4]$、$[1]$、$[2]$、$[3]$ 和 $[4]$。只有路径 $[1,2,3,4]$ 不符合条件。

“华为杯”杭州电子科技大学2023新生编程大赛