Considere un grafo dirigido con ~n~ nodos y ~m~ aristas. Su tarea consiste en contar el número de caminos del nodo ~1~ al nodo ~n~ con exactamente ~k~ aristas.

Entrada

La primera línea de entrada contiene tres enteros ~n, m~ y ~k~: el número de nodos y aristas, y la longitud del camino. Los nodos se numeran ~1,2,\dots,n~. Luego, hay ~m~ líneas que describen las aristas. Cada línea contiene dos enteros ~a~ y ~b~: hay una arista del nodo ~a~ al nodo ~b~.

Salida

Imprima el número de caminos módulo ~10^9+7~.

Restricciones

• ~1 \leq n \leq 100~
• ~1 \leq m \leq n(n-1)~
• ~1 \leq k \leq 10^9~
• ~1 \leq a,b \leq n~

Ejemplo de Entrada

3 4 8
1 2
2 3
3 1
3 2

Ejemplo de Salida

2

Explicación: Las rutas son ~1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 3~ y ~1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 3~.