3528: CF283 - C. Coin Troubles
[Creator : ]
Description
In the Isle of Guernsey there arendifferent 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 Jessieqpairs 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 allbiare distinct and allciare 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 $10^9+7$.
If there are no possible combinations of coins totalingtcents that satisfy Bessie's conditions, output 0.
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 $10^9+7$.
If there are no possible combinations of coins totalingtcents that satisfy Bessie's conditions, output 0.
Input
The first line contains three space-separated integers, $n,q,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, c_i\ (1≤b_i,c_i≤n;\ b_i≠c_i)$.
It's guaranteed that all $b_i$ are distinct and all ci are distinct.
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, c_i\ (1≤b_i,c_i≤n;\ b_i≠c_i)$.
It's guaranteed that all $b_i$ are distinct and all ci are distinct.
Output
A single integer, the number of valid coin combinations that Bessie could have, modulo $10^9+7$.
Sample 1 Input
4 2 17
3 1 2 5
4 2
3 4
Sample 1 Output
3
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}.
Sample 2 Input
3 2 6
3 1 1
1 2
2 3
Sample 2 Output
0
Sample 3 Input
3 2 10
1 2 3
1 2
2 1
Sample 3 Output
0