Insane Cube Persecution Corporation

Time Limit: 3 Seconds Memory Limit: 65536 KB

You wake up in a corner of a room without remembering how you got there. You see 6 other people and some doors. The strange thing is that there are doors on the walls (not so strange), the ceiling, and the floor! You remember a movie you saw a while back. The name had something like ”Cube” in it?

Oh $#!%! This was real?!?! You see the logo of the company (ICPC) on a guys shirt! He should know everything about it. He starts explaining:

”The company is called Insane Cube Persecution Corporation (ICPC). We need to get from this room (room 1) to the last room (room n) but the number written on this key should be k when we want to exit room n”. ”What do you mean?” you ask. ”The number on the key changes when we go to other rooms. It becomes the lowest common multiplier of the value before you enter and the number written on the wall of the room we enter, which might not be the same as the room number” he explains. You check the number on the key and it’s equal to the number on the wall (remember that you are in room 1). ”But what if the value remains the same when entering a room?” another guy asks. ”Well,...” he hesitates, ”we’ll all die!”.

Being a problem solver, you want to know how many ways are there to safely get out.

Input

The input contains several test cases.

In the first line of input comes T (0 < T ≤ 10), the number of test cases.

Each test case begins with three numbers 2 ≤ n ≤ 2000, 2 ≤ m ≤ 20000, and 2 ≤ k ≤ 10⁶, separated with space. The next line contains n integers, p₁,...,p_n 1 ≤ p_i ≤ 10⁶ the numbers written on the wall of each room. Then comes m lines describing the connection between rooms. Each line contains a sentence like: ”There is a door from room u to room v.”, where u and v are integers (1 ≤ u,v ≤ n, u≠v). This means that you can go from room u to room v but you might not be able to come back (Yuhahhahaha!).

Output

For each test case, you should print a line containing a single integer, the number of paths to safely get out modulo 1000000007.

Sample Input

1
5 6 84
1 5 4 12 21
There is a door from room 1 to room 2.
There is a door from room 2 to room 5.
There is a door from room 1 to room 3.
There is a door from room 3 to room 5.
There is a door from room 1 to room 4.
There is a door from room 4 to room 5.

Sample Output

Submit

Source: 13th Iran Nationwide Internet Contest - UT