#2159 남김 없는 여행

1 s   128 MB  

Description

올해로 솔로 22주년(2015년도기준)을 맞게 된(모태솔로 인건 비밀로 하자) 박씨는 마침내 자신은 절대 여자친구가 생기지 않을 것이라 확신하게 되었다.
 
여자 친구라 불리 우는, 마치 전설의 포켓몬과 같은 그 존재는 사람들의 외로움이 만들어 낸 허상이라는 것을 깨닫게 된다.
 
세상의 진리를 터득한 그는 속세에 미련 없이 입대 날짜만을 기다리고 있다.
 
그에게 남은 것은 아르바이트를 하여 모은 돈뿐이었다.
 
입대를 얼마 앞두지 않은 어느날, 그는 결심했다.
 
“이 돈을 이 세상의 모든 이들이 여자친구라는 허상에서 벗어나게 하는데에 쓰리라.”
 
그렇게 박씨는 여행을 떠나기로 했다. 박씨가 가진 것은 돈과 지도밖에 없었다.
 
당신은 그런 박씨의 아름다운 여행의 일정을 짜는 것으로 박씨에게 도움을 주려고 한다.
 
자 당신은 $N$개의 도시($0$ ~$ N-1$)를 알고 있으며, 각각의 도시가 어떻게 연결되어 있는지를 입력 받는다.
 
한 도시에서 다른 도시로 이동하는 데에는 $1$원의 돈이 소요된다.
 
박씨가 $K$원을 가지고 여행을 떠난다고 했을 때, 박씨가 정확히 $K$원을 사용하여 $0$번 도시에서 출발하여 다시 $0$번 도시에 도착할 수 있는 경우의 수를 구하시오.
 
박씨가 갔던 곳을 또 가더라도 귀찮으니 신경 쓰지 않고싶은 당신은, 이미 방문했던 도시와 도로도 다시 이용할 수 있다고 가정한다.

Input

첫 줄에 테스트 케이스의 수 T가 주어진다.
그리고 각 테스트 케이스의 첫 줄에는 도시의 수 $N(2 \leq N \leq 10)$과 도로의 수 $M(1 \leq M \leq 100)$, 그리고 박씨가 가진 돈 $K(2 \leq K \leq 2,000)$가 주어진다. 
도시의 번호는 $0$번부터 $(N-1)$번까지 이다.
그 후 $M$줄에 각 줄에 정수 $2$개가 주어진다. 이 정수는 도로의 연결 정보를 나타낸다. 정수 $A$와 $B$가 주어졌을 경우 이는 $A$도시에서 $B$도시로 가는 도로가 존재한다는 뜻이다.
단, 모든 도로는 일방통행이라 가정하며, 두 도시간에 도로가 여러 개 있을 수 있다. 자기 자신에게 연결된 도로는 없다고 가정한다.

Output

각 줄에 해당 테스트케이스의 답을 출력한다. 단, 답이 $1,000,000,000$이상일 경우 $1,000,000,000$으로 나눈 나머지를 출력한다.

Sample Input

Sample Output

1
3 4 2
0 1
1 2
2 1
1 0
1

Source

2013 Ajou Programming Contest - 김동이 (mitslll, 아주대학교)