Hace mucho tiempo existió un rey en el gran reino de IslaGrande. Había n ciudades en el reino, algunas de ellas estaban conectadas por m senderos. Los senderos eran unidireccionales porque sería peligroso si dos carruajes que viajaban en direcciones opuestas se encontraban en un sendero. Una vez el rey decidió que le gustaría establecer estaciones de bomberos y ordenó construir las estaciones de bomberos en algunas ciudades. Pero como sus finanzas son limitadas, sólo le gustaría construir k estaciones en diferentes ciudades. Quisiera construirlas de tal manera que se cumplieran las siguientes condiciones:

• es posible llegar por los senderos de cada ciudad a alguna ciudad con estación de bomberos;

• es posible llegar por los senderos a cada ciudad desde alguna ciudad con estación de bomberos.

El rey quiere saber cuántas maneras distintas hay de hacer la construcción de las ~k~ estaciones bajo las condiciones dichas. Por lo que su tarea es ayudarlo a encontrar la respuesta a esta pregunta haciendo un programa que la compute.

Entrada

La primera línea de la entrada contiene ~n, m~ y ~k~, el número de ciudades, senderos en el reino, y el número de estaciones de bomberos a construir respectivamente (~1 \le n \le 100, 0 \le m \le 20 000, 1 \le k \le n~). Las siguientes m líneas contienen dos números de ciudad cada uno y describen senderos, recuerde que sólo es posible viajar a lo largo de ellos en una dirección, de la primera ciudad a la segunda. Dos ciudades pueden estar conectadas por más de un sendero.

Salida

Imprima un único número entero, el número de formas de cumplir la solicitud del rey. Como este número puede ser muy grande imprímelo módulo ~1000000007(10^9+7~).

Ejemplo de Entrada

6 7 3
1 2
2 3
3 1
3 4
4 5
5 6
6 5

Ejemplo de Salida

15