Visita a JOI-kun

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 512M

Author:

eblabrada

Problem type

Allowed languages

C++

OCI-kun quiere visitar a su gran amigo JOI-kun para retarlo a resolver los problemas del último concurso Esperanzas Olímpicas.

Ambos viven en una ciudad que puede ser representada como un grafo no dirigido de $n$ ~n~ nodos, numerados del $1$ ~1~ al $n$ ~n~, y $m$ ~m~ aristas. OCI-kun se encuentra en el nodo $1$ ~1~ y JOI-kun vive en el nodo $n$ ~n~.

Un camino entre dos nodos se puede expresar como una secuencia de nodos $x_1, x_2, \ldots, x_k$ ~x_1, x_2, \ldots, x_k~, donde $x_1$ ~x_1~ es el nodo inicial, $x_k$ ~x_k~ es el nodo final, y existe una arista entre cualesquiera dos nodos consecutivos. Por ejemplo, en el siguiente grafo $(1,2,4)$ ~(1,2,4)~ describe un camino que va desde el nodo $1$ ~1~ al nodo $2$ ~2~ y luego desde el nodo $2$ ~2~ al nodo $4$ ~4~.

Como OCI-kun tiene prisa por empezar a programar, quiere saber cuántos caminos existen desde su casa en el nodo $1$ ~1~ hasta la casa de JOI-kun en el nodo $n$ ~n~ cuya cantidad de nodos esté relativamente cerca del menor número de nodos posible. Específicamente, debes contar los distintos caminos que contienen menos de $p$ ~p~ nodos adicionales.

Por ejemplo, considera el grafo anterior con $n = 4$ ~n = 4~ y $m = 5$ ~m = 5~ que contiene todas las aristas posibles excepto la que une al nodo $1$ ~1~ con el nodo $4$ ~4~. Si $p = 3$ ~p = 3~, el menor número de nodos en un camino válido de $1$ ~1~ a $4$ ~4~ es $3$ ~3~. Debes contar los siguientes caminos:

$0$ ~0~ nodos extra: $(1, 2, 4)$ ~(1, 2, 4)~ y $(1, 3, 4)$ ~(1, 3, 4)~ ( $2$ ~2~ caminos).
$1$ ~1~ nodo extra: $(1, 2, 3, 4)$ ~(1, 2, 3, 4)~ y $(1, 3, 2, 4)$ ~(1, 3, 2, 4)~ ( $2$ ~2~ caminos).
$2$ ~2~ nodos extra: $(1, 2, 1, 2, 4)$ ~(1, 2, 1, 2, 4)~, $(1, 2, 1, 3, 4)$ ~(1, 2, 1, 3, 4)~, $(1, 2, 3, 2, 4)$ ~(1, 2, 3, 2, 4)~, $(1, 2, 4, 2, 4)$ ~(1, 2, 4, 2, 4)~, $(1, 2, 4, 3, 4)$ ~(1, 2, 4, 3, 4)~, $(1, 3, 1, 2, 4)$ ~(1, 3, 1, 2, 4)~, $(1, 3, 1, 3, 4)$ ~(1, 3, 1, 3, 4)~, $(1, 3, 2, 3, 4)$ ~(1, 3, 2, 3, 4)~, $(1, 3, 4, 2, 4)$ ~(1, 3, 4, 2, 4)~ y $(1, 3, 4, 3, 4)$ ~(1, 3, 4, 3, 4)~ ( $10$ ~10~ caminos).

Entrada

La primera línea contiene tres enteros $n$ ~n~, $m$ ~m~ y $p$ ~p~ ( $2 \le n \le 10^5$ ~2 \le n \le 10^5~, $1 \le m \le 2 \cdot 10^5$ ~1 \le m \le 2 \cdot 10^5~, $1 \le p \le 10$ ~1 \le p \le 10~) $-$ ~-~ la cantidad de nodos, la cantidad de aristas y el parámetro $p$ ~p~.

Cada una de las siguientes $m$ ~m~ líneas contiene dos enteros $u$ ~u~ y $v$ ~v~ ( $1 \le u, v \le n$ ~1 \le u, v \le n~) $-$ ~-~ indicando que existe una arista bidireccional entre los nodos $u$ ~u~ y $v$ ~v~.

Se garantiza que existe al menos un camino entre el nodo $1$ ~1~ y el nodo $n$ ~n~, y que hay a lo sumo una arista entre cualquier par de nodos.

Salida

Imprime $p$ ~p~ enteros $-$ ~-~ el número de caminos con exactamente $0, 1, \ldots, p-1$ ~0, 1, \ldots, p-1~ nodos extra, respectivamente.

Como el número de caminos puede ser muy grande, imprime las respuestas módulo $10^9+7$ ~10^9+7~.

Subtareas

Subtarea	Puntos	Restricciones adicionales	Dependencias
$1$ ~1~	$9$ ~9~	$2 \le n \le 10$ ~2 \le n \le 10~, $1 \le m \le 20$ ~1 \le m \le 20~	$-$ ~-~
$2$ ~2~	$19$ ~19~	$p=2$ ~p=2~	$-$ ~-~
$3$ ~3~	$22$ ~22~	$p=3$ ~p=3~	$-$ ~-~
$4$ ~4~	$18$ ~18~	$2 \le n \le 1000$ ~2 \le n \le 1000~, $1 \le m \le 2000$ ~1 \le m \le 2000~	$1$ ~1~
$5$ ~5~	$32$ ~32~	Sin restricciones adicionales	$1-4$ ~1-4~

Ejemplos

Entrada 1

Salida 1

2 2 10

Comments

There are no comments at the moment.