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)$ .

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.