Falcom is a historical company whose work "Ys VIII -Lacrimosa of DANA-" is highly acclaimed.

Remoon wants to get the platinum trophy of this game for all versions, and he notices that the game has versions, indexed from to . A quick way to achieve this is to copy data between different versions. Unfortunately, due to compatibility issues, data in each version cannot be loaded in other versions. Nevertheless, remoon gets editors, where the -th editor can rewrite data in version , such that the rewritten data can be loaded in version . It is also possible to use the -th editor to change data in version to data in version . It is guaranteed that any two versions can transform into each other through the editors.

To distinguish between each version, remoon gives each version a magic integer . If for any editor, . Then remoon can distinguish whether the editor has correctly rewritten a version or not. Besides, to limit the magic number's size, remoon gives an upper bound integer sequence and require that for , we have .

Remoon wonders how many ways to choose so that he can correctly distinguish between the versions. Two ways and are considered different if and only if there exists such that . As the answer may be too large, you only need to output the answer modulo .

The first line contains an integer , denoting the number of versions. 


The second line contains  integers , denoting the upper bound on the magic integer on each version.

Then  lines follow, where the -th line  contains two integers  and , denoting the -th editor can copy data between version  and .

Output an integer in a line, denoting the answer taken modulo .

5
1 2 3 4 5
1 2
2 3
3 4
4 5

24