어떤 나라의 교통망은 \(V\) 개의 도시와 \(E\) 개의 일방통행 도로로 이루어져 있다. 각 도로는 한 도시에서 다른 도시로(혹은 같은 도시로 되돌아오는 자기 순환일 수도 있다) 한쪽 방향으로만 통행할 수 있다. 두 도시 사이에는 여러 개의 도로가 있을 수도 있으며, 이들은 서로 다른 도로로 취급한다.

당신은 도시 \(s\) 에서 출발하여 도시 \(t\) 에 도착하되, 정확히 \(K\) 개의 도로를 사용하는 서로 다른 이동 경로(걷기, walk)의 수가 궁금하다. 같은 도시나 같은 도로를 여러 번 지나도 상관없으며, 사용한 도로의 순서열이 다르면 서로 다른 경로로 센다.

이 경로의 수는 매우 클 수 있고 \(K\) 또한 천문학적으로 클 수 있으므로, 답을 \(10^9+7\) 로 나눈 나머지를 출력하라.

\(K = 0\) 인 경우, 도로를 하나도 사용하지 않는 길이 \(0\) 의 경로는 \(s = t\) 일 때 정확히 한 가지가 존재하고, \(s \ne t\) 이면 존재하지 않는다.

\(1 \le V \le 50\)

\(0 \le E \le V^2\)

\(0 \le K \le 10^{18}\)

\(1 \le s, t \le V\)

\(1 \le u, v \le V\) (자기 순환 및 다중 도로 허용)

첫째 줄에 다섯 정수 \(V\), \(E\), \(K\), \(s\), \(t\) 가 공백으로 구분되어 주어진다 (\(1 \le V \le 50\), \(0 \le E \le V^2\), \(0 \le K \le 10^{18}\), \(1 \le s, t \le V\)).

다음 \(E\) 개의 줄에는 각각 두 정수 \(u\), \(v\) (\(1 \le u, v \le V\)) 가 주어지며, 도시 \(u\) 에서 도시 \(v\) 로 가는 일방통행 도로가 있음을 뜻한다. \(u = v\) (자기 순환) 와 같은 \((u, v)\) 의 중복(다중 도로)이 모두 허용된다.

도시 \(s\) 에서 도시 \(t\) 로 정확히 \(K\) 개의 도로를 사용해 이동하는 서로 다른 경로의 수를 \(10^9+7\) 로 나눈 나머지를 한 줄에 출력한다.

riseoj 작성

출처 Original