En la isla de Guernsey hay ~n~ tipos de monedas. Por cada ~i \; (1 \leq i \leq n)~, la moneda de tipo ~i~ vale ~a_i~ centavos. Es posible que ~a_i = a_j~ para algún ~i~ y ~j \; (i \neq j)~.

Bessie tiene un conjunto de estas monedas que en total suman ~t~ centavos. Ella le dice a Jessie ~q~ pares de enteros. Por cada ~i \; (1 \leq i \leq q)~, el par ~b_i~, ~c_i~ le dice a Jessie que Bessie tiene estrictamente más monedas de tipo ~b_i~ que de tipo ~c_i~. Se sabe que todos los ~b_i~ son distintos y todos los ~c_i~ son distintos.

Ayuda a Jessie a hallar el número de combinaciones de monedas que Bessie puede tener. Dos combinaciones son consideradas distintas si existe un ~i \; (1 \leq i \leq n)~, tal que el número de monedas que Bessie tiene de tipo ~i~ es distinto en las dos combinaciones. Como la respuesta puede ser muy grande imprímala modulo ~10^9 + 7~.

Si no hay combinaciones de monedas que satisfagan las condiciones de Bessie, imprima ~0~.

Entrada

La primera línea contiene los enteros ~n~, ~q~ y ~t \; (1 \leq n \leq 300; 0 \leq q \leq n; 1 \leq t \leq 10^5)~ separados entre sí por un espacio.

La segunda línea contiene ~n~ enteros separados entre sí por un espacio, ~a_1, a_2, \ldots, a_n \; (1 \leq a_i \leq 10^5)~.

Las siguientes ~q~ líneas contienen los enteros ~b_i~ y ~c_i \; (1 \leq b_i, c_i \leq n; b_i \neq c_i)~ separados por un espacio.

Se garantiza que todos los ~b_i~ son distintos y todos los ~c_i~ son distintos.

Salida

Imprima en una única línea la respuesta del problema.

Ejemplos

Entrada 1

4 2 17
3 1 2 5
4 2
3 4

Salida 1

3

Entrada 2

3 2 6
3 1 1
1 2
2 3

Salida 2

0

Entrada 3

3 2 10
1 2 3
1 2
2 1

Salida 3

0

Explicación del primer ejemplo

Las combinaciones son:

• ~[0, 1, 3, 2]~
• ~[0, 0, 6, 1]~
• ~[2, 0, 3, 1]~

Cada columna de cada arreglo es la cantidad de monedas de tipo ~i \; (1 \leq i \leq n)~ en cada combinación.

Ninguna otra combinación que satisfaga todas las condiciones existe.

Nota que aunque ~4~ aparece en ~b_i~ y ~c_i~, las condiciones del problema se cumplen ya que todos los ~b_i~ son distintos y todos los ~c_i~ son distintos.