CF283C.Coin Troubles

In the Isle of Guernsey there are n different types of coins. For each i (1 ≤ i ≤ n), coin of type i is worth a__i cents. It is possible that a__i = a__j for some i and j (i ≠ j).

Bessie has some set of these coins totaling t cents. She tells Jessie q pairs of integers. For each i (1 ≤ i ≤ q), the pair b__i, c__i tells Jessie that Bessie has a strictly greater number of coins of type b__i than coins of type c__i. It is known that all b__i are distinct and all c__i are distinct.

Help Jessie find the number of possible combinations of coins Bessie could have. Two combinations are considered different if there is some i (1 ≤ i ≤ n), such that the number of coins Bessie has of type i is different in the two combinations. Since the answer can be very large, output it modulo 1000000007 (109 + 7).

If there are no possible combinations of coins totaling t cents that satisfy Bessie's conditions, output 0.

在根西岛（Isle of Guernsey）共有 $n$ 种不同的硬币。对于每个 $i$（$1 \le i \le n$），第 $i$ 类硬币面值为 $a_i$ 分。可能存在某些 $i$ 和 $j$（$i \ne j$），使得 $a_i = a_j$。

贝茜拥有一组上述硬币，总面值恰好为 $t$ 分。她告诉杰西 $q$ 对整数。对每个 $i$（$1 \le i \le q$），该对整数 $(b_i, c_i)$ 表示：贝茜所拥有的第 $b_i$ 类硬币的数量严格大于第 $c_i$ 类硬币的数量。已知所有 $b_i$ 互不相同，且所有 $c_i$ 也互不相同。

请帮助杰西计算贝茜可能拥有的硬币组合总数。若存在某个 $i$（$1 \le i \le n$），使得两种组合中第 $i$ 类硬币的数量不同，则认为这两种组合不同。由于答案可能非常大，请将结果对 $1000000007$（即 $10^9 + 7$）取模后输出。

若不存在任何总面值恰好为 $t$ 分、且满足贝茜所述条件的硬币组合，则输出 $0$。

The first line contains three space-separated integers, n, q and t (1 ≤ n ≤ 300; 0 ≤ q ≤ n; 1 ≤ t ≤ 105). The second line contains n space separated integers, _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 105). The next q lines each contain two distinct space-separated integers, b__i and c__i (1 ≤ b__i, c__i ≤ n; b__i ≠ c__i).

It's guaranteed that all b__i are distinct and all c__i are distinct.

第一行包含三个用空格分隔的整数 $n$、$q$ 和 $t$（$1 ≤ n ≤ 300$；$0 ≤ q ≤ n$；$1 ≤ t ≤ 10^5$）。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, ..., a_n$（$1 ≤ a_i ≤ 10^5$）。
接下来的 $q$ 行每行包含两个用空格分隔的互异整数 $b_i$ 和 $c_i$（$1 ≤ b_i, c_i ≤ n$；$b_i ≠ c_i$）。

保证所有 $b_i$ 互不相同，且所有 $c_i$ 互不相同。

A single integer, the number of valid coin combinations that Bessie could have, modulo 1000000007 (109 + 7).

一个整数，表示奶牛贝茜可能拥有的有效硬币组合数，对 $1000000007$（即 $10^9 + 7$）取模的结果。

For the first sample, the following 3 combinations give a total of 17 cents and satisfy the given conditions: {0 of type 1, 1 of type 2, 3 of type 3, 2 of type 4}, {0, 0, 6, 1}, {2, 0, 3, 1}.

No other combinations exist. Note that even though 4 occurs in both b__i and c__i,  the problem conditions are still satisfied because all b__i are distinct and all c__i are distinct.

对于第一个样例，以下 3 种组合的总金额为 17 分，且满足给定条件：{0 枚类型 1、1 枚类型 2、3 枚类型 3、2 枚类型 4}，{0, 0, 6, 1}，{2, 0, 3, 1}。

不存在其他组合。注意，尽管数字 4 同时出现在 $b_i$ 和 $c_i$ 中，问题条件依然满足，因为所有 $b_i$ 互不相同，且所有 $c_i$ 也互不相同。