시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 8 5 3 100.000%

문제

상근이는 도시를 오고가며 짐을 실고 내리는 트럭 운전사이다. 상근이의 트럭은 매우 커서, 짐을 무제한으로 담을 수 있다. 상근이는 대학시절 배운 프로그래밍을 이용해서 자동으로 짐을 실고 내릴 수 있는 기능을 트럭에 추가했다. 유난히도 스택을 좋아하는 상근이는 스택을 이 기능에 이용했다. 따라서, 마지막으로 실은 짐만 내릴 수 있다.

상근이는 짐을 26가지 종류로 구분했다. 이러한 짐은 알파벳으로 나타낼 수 있다. (대소문자는 구분하지 않는다)

도시의 도로는 모두 일방통행이고, 길이는 모두 1 킬로미터이다. 또, 도로는 모두 세 종류로 나눌 수 있다. 이 도로는 1번 도로, 2번 도로, 3번 도로라고 한다.

1번 도로를 지날 때는 그 도로에 해당하는 짐을 하나 실어야 하고, 2번 도로는 짐을 하나 내려야 한다. 3번 도로는 짐을 실거나 내리지 않고 지나가야 한다.

도시는 N개, 도로는 E개가 있다 상근이는 1번 도시에서 출발해서 N번 도시에 도착해야 한다. N번 도시에 도착했을 때, 트럭은 비어있어도 되고, 안 비어있어도 된다.

상근이가 N번 도시로 도착하는 방법의 수를 계산하는 프로그램을 작성하시오. 단, 상근이는 최대 K 킬로미터만 이동할 수 있다.

입력

첫째 줄에 도시의 수 N, 도로의 수 E, 이동할 수 있는 최대 거리 K가 주어진다. (2 ≤ N ≤ 50, 1 ≤ E ≤ 2450, 1 ≤ K ≤ 50)

다음 E개 줄에는 도로의 정보가 주어진다. 각 도로의 종류에 따라 다른 형식으로 주어진다.

1번 도로: "x y C" x에서 y로 향하는 도로이다. 이 도로를 지날 때, C(대문자)에 해당하는 짐을 실어야 한다.

2번 도로: "x y c" x에서 y로 향하는 도로이다. 이 도로를 지날 때, c(소문자)에 해당하는 짐을 내려야 한다.

3번 도로: "x y" x에서 y로 향하는 도로이며, 그 어

두 도시를 연결하는 도로의 수가 두 개 이상인 경우는 없다. (단, 방향이 다를 수는 있다) 또, x와 y가 같은 경우도 없다.

출력

첫째 줄에 상근이가 1번 도시에서 출발해서 N번 도시로 도착하는 방법의 수를 출력한다. 수가 매우 커질 수 있기 때문에 10007로 나눈 나머지를 출력해야 한다.

예제 입력

7 9 5
1 2 A
2 3 B
2 5
5 3 C
3 4 b
3 6 c
3 7
4 7 a
6 7 a

예제 출력

4

힌트