Description

“凡人想以复杂的手法掩饰某件事时，往往因复杂而自掘坟墓，可是天才不会这样做。他们会选用极为单纯，但常人想象不到也绝不会选择的方法，将问题一口气复杂化。”

警察共发现了$n$个证据，然而其中有一些是石神伪造的。

通过证据的两两组合，警察可以作出一些假设，每个假设有一定价值。

现在要求你选取其中的一部分假设，使得总价值最大。

选取假设的要求是:

将证据看成点

将假设看成带权的无向边

所有的点和选取的边构成$k$个联通块

不允许出现环，避免作出的假设出现矛盾

我们称选取的假设有用，是指该假设所在的联通块中不包含伪造的证据。总价值等于所有选取的有用的假设的价值乘积。

求最大可能的总价值。

如果无法构成$k$个联通块则输出$-1$，如果能构成$k$个联通块但没有有用的假设则输出$1$。

Input Format

输入文件名为evidence.in。

第一行包含三个数$n m$和$k$，$n$表示证据的数量，$m$表示可以作出的假设数，$k$表示最终的联通块的数量。

第二行包含$n$个数$fact_i$，由$0$和$1$组成，如果$fact_i$是$0$则表示这个证据是伪造的，如果是$1$则表示这个证据是有价值的。

接下来m行每行包含三个数$x_i y_i$和$z_i$，表示第$i$条假设需要用到第$x_i$和第$y_i$个证据，同时这个假设的价值是$z_i$。

Output Format

输出文件名为evidence.out。

输出一行，包含一个整数，表示最大可能的总价值。

由于答案可能很大，所以对1000000007取模后输出。

Sample

样例输入一：

4 4 2
1 1 1 1
1 2 2
2 3 3
3 4 1
4 1 2

样例输出一：

6

样例输入二：

5 5 2
1 0 1 1 1
1 2 1
2 3 2
1 4 3
4 5 4
2 4 5

样例输出二：

12

Hint

对于30%的数据，$m \le 20$

对于50%的数据，不包含伪造的证据

对于100%的数据，$n \le 100000$，$m \le 200000$，权值$\le 100$