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 (109 + 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 ≤ 105). The second line contains n space separated integers, a1, a2, ..., an(1 ≤ ai ≤ 105). The next q lines each contain two distinct space-separated integers, bi and ci(1 ≤ bi, ci ≤ n; bi ≠ ci).It's guaranteed that all bi are distinct and all ci are distinct.
输出描述:
A single integer, the number of valid coin combinations that Bessie could have, modulo 1000000007(109 + 7).
示例1
输入
4 2 17<br />3 1 2 5<br />4 2<br />3 4<br />3 2 6<br />3 1 1<br />1 2<br />2 3<br />3 2 10<br />1 2 3<br />1 2<br />2 1<br />
备注:
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 bi and ci, the problem conditions are still satisfied because all bi are distinct and all ci are distinct.
加载中...