题目描述

在提瓦特大陆上有一个神秘的商贩，他现在有 $n$ 种不同面值的货币，每种货币 $a_i$ 元。他现在要花 $w$ 元买一块原石，让你求出有多少种购买方法并对 $10^9+7$ 取模。

他知道这对你来说太简单了，于是给了你 $m$ 条形如 $(b_i,c_i)$ 的限制，表示使用第 $b_i$ 种货币的数量必须大于使用第 $c_i$ 种货币的数量。

输入格式

第一行三个整数 $n,m,w$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

接下来 $m$ 行每行两个整数表示 $b_i,c_i$。

输出格式

一个整数表示答案。

4 2 17
3 1 2 5
4 2
3 4

3

10 4 18
9 2 8 2 7 4 9 5 10 9
7 9
9 2
2 5
5 10

0

数据范围

对于 $100\%$ 的数据，满足 $m\le n\le 300;1\le w, a_i\le 10^5;1 \le b_i,c_i \le n$，$\forall i\ne j$，都满足 $b_i\ne b_j$ 且 $c_i\ne c_j$。

• 子任务 1 (20 分): $n \le 10$
• 子任务 2 (10 分): $m = 0$
• 子任务 3 (20 分): 保证 $b,c$ 两个集合中所有数互不相同
• 子任务 4 (50 分): 无特殊限制

本题启用捆绑测试。