1752. Happy Ending

It's a beautiful day outside. Birds are singing, flowers are blooming... On days like these, kids like you...should take a fantastic trip to the Blue Planet.

Here, Baicha would share nice white tea with you, Sangze would take your girl suit photos with Jinle and Guodong would PS it elaborately. Miming would teach you useful gameplay tips, and then Xingyue would become your teammate and explore the magic-made games like ONU and the Land of the Kernel with you. If tired, Hefeng would tell you the tales happened in these hundreds of years and Yunyan would heal you with the Abyss power. While Tianjiang would watching you on the sly.

Enjoy yourself in the Blue Planet!

There're n activities indexed from 1 to n (inclusive) on the Blue Planet. And there're m restrictions, each restriction (u,v) denotes that activity v can be be held only after u has been held. If any of the restrictions (u,v) is satisfied, then v can be held. Holding the activity i needs a_i hours. You can hold only one activity each time. You only hope to finish holding the activity n within no more than t hours in total. Suppose there're r schemes can satisfy your hope, you should calculate r\bmod(10^9+7) .

输入

Input the first line with three integers n,m,t(2\le n\le10^4,1\le m\le3\times 10^4,1\le t\le10^3) .

Input the second lines with n integers, the i-th integer denotes a_i(1\le a_i\le10^3) .

Then input m lines, each line contains two integers u,v(1\le u, v\le n,u\neq v) .

It's guaranteed that every activity can be held, i.e. there's no restriction cycles in the given data.

输出

Output one line with one integer r\bmod(10^9+7) .

样例

标准输入 复制文本
4 5 10
2 2 3 5
1 2
1 3
2 3
2 4
3 4
标准输出 复制文本
2
标准输入 复制文本
4 5 8
2 2 3 5
1 2
1 3
2 3
2 4
3 4
标准输出 复制文本
0
标准输入 复制文本
4 4 8
2 2 8 5
2 4
2 1
1 4
3 4
标准输出 复制文本
1

提示

In the first example, two schemes are holding (1,2,4),(1,3,4) in order.

In the second example, none of schemes are available.

In the third example, the only scheme is holding (2,4) in order.

2023/4/4 Update statement.

来源

2022 软件学院 ACM 集训队筛选赛

登录以提交代码。
单点时限 2 秒
内存限制 256 MB
提交 132
通过 37