Coin Troubles

题意翻译

有$n$种不同的硬币，每个硬币有一个价值$a_i$（不同硬币价值可能相同). $Bessie$有若干种选择硬币的方法使得选出的硬币总价值为$t.Bessie$会给你$q$对$(b,c),$并告诉你第$b$种硬币的数量严格大于第$c$种硬币的数量.保证这$q$对$(b,c)$中所有$b$都不同且所有$c$也都不同。 问有多少种选择硬币的方法满足选出的硬币总价值为$t?$ $Bessie$认为两种方案不同指的是两种方案存在至少一种硬币数量不同。 答案对$10^9+7$取模。

题目描述

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 $ $ (10^{9}+7) $ . If there are no possible combinations of coins totaling $ t $ cents that satisfy Bessie's conditions, output 0.

输入输出格式

输入格式

The first line contains three space-separated integers, $ n,q $ and $ t $ $ (1<=n<=300; 0<=q<=n; 1<=t<=10^{5}) $ . The second line contains $ n $ space separated integers, $ a_{1},a_{2},...,a_{n} $ $ (1<=a_{i}<=10^{5}) $ . 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.

输出格式

A single integer, the number of valid coin combinations that Bessie could have, modulo $ 1000000007 $ $ (10^{9}+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

说明

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.