2596: 都市环游

因为SJY干的奇怪事情过多，SJY收到了休假的通知，于是他准备在都市间来回旅游。SJY有一辆车子，一开始行驶性能为0，每过1时间行驶性能就会提升1点。每个城市的道路都有性能要求。SJY一共有t时间休息，一开始他位于1号城市（保证1号城市道路要求为0），他希望在n号城市结束旅程。每次穿过一条城市间的路会花费1时间，当然他也可以停留在一个城市不动而花费1时间。当且仅当车子的行驶性能大于等于一个城市，我们才能到达那里。SJY希望知道，旅游的方案模10086后的答案。（只要在某一时刻通过的道路存在一条不相同，就算不同的方案）

    第一行三个数n,m,t，表示有n个城市m条道路t时间。    

第二行n个数，hi表示第i个城市的道路性能要求。

第三到m+2行，每行两个数u,v，表示城市u与城市v之间有一条单向道路连接（可能有重边）。

包括一个数字，表示旅游的方案模10086。

5 17 7
0 2 4 5 3 
1 2
2 1
1 3
3 1
1 4
4 1
4 5
5 4
5 3
4 1
2 1
5 3
2 1
2 1
1 2
2 1
1 3

245