One ominous late October night you recieve a startling message:

------BEGIN MESSAGE------

From: <REDACTED>

Hello MCPT user. I have inserted an array ~A~ initially consisting of ~N~ integers, as well as a set of ~M~ instructions onto this website.

Each instruction is in the form x y, stating that for all indices ~i \ (1 \le i < |A|)~, if ~a_i + a_{i+1} = x~, ~y~ is inserted between indices ~i~ and ~i+1~ of the array. Note that ~|A|~ represents the size of the current array.

Now comes the fun part. During an iteration, each instruction will be performed on all valid indices simultaneously, exactly once. My array will theoretically keep growing forever and ever, taking up all the resources and memory on this website.

There is hope. The array will stop growing if you can print out the correct stop key. The stop key is found by determining the sum of all integers within the array after exactly ~K~ iterations, modulo ~10^9 + 7~. I'm almost certain there is no possible way to do this.

------END MESSAGE------

Help save MCPT! Print out the stop key.

Constraints

~1 \le N \le 2 \times 10^3~

~1 \le x, \ M \le 200~

~1 \le y, \ a_i, \ K \le 100~

all ~x~ are distinct.

Subtask 1 [20%]

~1 \le K \le 5~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain ~N~, ~M~, and ~K~, space-separated.

The next line will contain ~N~ integers ~a_i~.

The next ~M~ lines will contain ~2~ integers ~x~ and ~y~.

Output Specification

Output the stop key, the sum of all integers within the array after ~K~ iterations, modulo ~10^9 + 7~.

Sample Input

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

Sample Output

24

Explanation

After the first iteration, the array is:

~[1,4,2,1,3,1,4,2]~

After the second iteration, the array is:

~[1,1,4,2,4,1,3,1,1,4,2]~

The sum of all integers in this array is ~24~.