根西岛有 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 都是不同的。