CF283C Coin Troubles

在根西岛上有 $n$ 种不同类型的硬币。对于每个 $i$（$1 \leq i \leq n$），第 $i$ 种硬币的面值为 $a_i$ 分。可能存在某些 $i$ 和 $j$（$i \ne j$），使得 $a_i = a_j$。 Bessie 拥有一些这些硬币，其总面值为 $t$ 分。她告诉 Jessie $q$ 对整数。对于每个 $i$（$1 \leq i \leq q$），数对 $b_i, c_i$ 告诉 Jessie，Bessie 拥有的第 $b_i$ 种硬币的数量严格大于第 $c_i$ 种硬币的数量。已知所有 $b_i$ 均不相同，且所有 $c_i$ 均不相同。 请帮助 Jessie 计算 Bessie 最多可能有哪些不同的硬币组合。若存在某个 $i$（$1 \leq i \leq n$），使得两种组合中 Bessie 拥有的第 $i$ 种硬币数量不同，则这两种组合被认为是不同的组合。由于答案可能很大，请输出其对 $1000000007$（$10^9+7$）取模的结果。 如果不存在满足 Bessie 条件、且总面值为 $t$ 分的硬币组合，请输出 $0$。

第一行包含三个用空格分隔的整数 $n, q, t$（$1 \leq n \leq 300; 0 \leq q \leq n; 1 \leq t \leq 10^5$）。 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, ..., a_n$（$1 \leq a_i \leq 10^5$）。 接下来的 $q$ 行每行包含两个不同的用空格分隔的整数 $b_i$ 和 $c_i$（$1 \leq b_i, c_i \leq n; b_i \ne c_i$）。 保证所有 $b_i$ 两两不同，所有 $c_i$ 两两不同。

输出一个整数，表示 Bessie 可能拥有的、满足条件的硬币组合数，对 $1000000007$ 取模。

对于第一个样例，以下 3 种组合总面值均为 17 分，并满足题目条件：$\{0 \text{ 枚 1 型}, 1 \text{ 枚 2 型}, 3 \text{ 枚 3 型}, 2 \text{ 枚 4 型}\}, \{0, 0, 6, 1\}, \{2, 0, 3, 1\}$。 不存在其他组合。注意，尽管 $4$ 同时出现在 $b_i$ 和 $c_i$ 中，但因为所有 $b_i$ 都不同、所有 $c_i$ 都不同，所以题目的条件仍然成立。 由 ChatGPT 5 翻译