← 返回题目列表

Codeforces · 283/C

C. 硬币问题

中文机器翻译题面 查看原题

根西岛有 n 种不同类型的硬币。对于每个 i (1 ≤ i ≤ n),类型 i 的硬币价值 ai 美分。对于某些 i 和 j (i ≠ j),可能有 ai = aj。

贝西有一套这样的硬币,总价值为 t 美分。她告诉 Jessie q 对整数。对于每个 i (1 ≤ i ≤ q),bi,ci 对告诉 Jessie,Bessie 拥有 bi 类型硬币的数量严格多于 ci 类型硬币的数量。已知所有bi 都是不同的并且所有ci 都是不同的。

帮助杰西找出贝西可能拥有的硬币组合的数量。如果存在某个 i (1 ≤ i ≤ n),则两个组合被认为是不同的,使得 Bessie 拥有的类型 i 的硬币数量在两个组合中不同。由于答案可能非常大,因此输出它对 1000000007 (109 + 7) 求模。

如果没有可能的总计 t 美分的硬币组合满足 Bessie 的条件,则输出 0。

输入

第一行包含三个以空格分隔的整数 n、q 和 t (1 ≤ n ≤ 300;0 ≤ q ≤ n;1 ≤ t ≤ 105)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ 105)。接下来的 q 行每行包含两个不同的空格分隔整数 bi 和 ci(1 ≤ bi,ci ≤ n;bi ≠ ci)。

保证所有 bi 不同且所有 ci 不同。

输出

一个整数,Bessie 可以拥有的有效硬币组合的数量,模 1000000007 (109 + 7)。

示例

输入 #1

4 2 17
3 1 2 5
4 2
3 4

输出 #1

3

输入 #2

3 2 6
3 1 1
1 2
2 3

输出 #2

0

输入 #3

3 2 10
1 2 3
1 2
2 1

输出 #3

0

注意

对于第一个样本,以下 3 个组合总共为 17 美分,并满足给定条件:{0 类型 1、1 类型 2、3 类型 3、2 类型 4}、{0, 0, 6, 1}、{2, 0, 3, 1}。

不存在其他组合。请注意,即使 4 出现在 bi 和 ci 中,问题条件仍然满足,因为所有 bi 都是不同的,并且所有 ci 都是不同的。