[6. 화물 운반]

문제)

정우는 트럭을 통해 화물을 운반하는 트럭 운전사다. 그가 하는 일은 도로들을 통해 도시 사이를 이동하면서 화물을 싣고, 내리는 역할을 한다.
그가 운전하는 트럭은 매우 커 수용할 수 있는 화물 개수의 제한은 없다. 하지만 그의 트럭은 입구와 출구가 동일해 자료구조의 스택과 같이 FILO (First-in-last-out) 규칙을 따른다.
즉, 짐을 내릴 때는 가장 최근에 넣은 짐부터 뺄 수 있다.
정우는 서로 다른 26가지 종류의 짐만 취급한다.
도시들은 길이 1km의 단방향 도로로 구성되어 있고, 그 도로들은 3가지 종류로 구분된다.

• Type 1 : 운반을 요구하는 도로다. 정우가 이 도로를 지날 때마다 반드시 도로가 요구하는 짐을 트럭에 넣어야한다.
• Type 2 : 운반 받기를 요구하는 도로다. 정우가 이 도로를 지날 때마다 반드시 도로가 요구하는 짐을 건네줘야한다. (만약 그 짐을 바로 줄 수 없다면, 이 도로를 지날 수 없다.)
• Type 3 : 그냥 평범한 도로다. 정우가 이 도로를 지날 때 아무것도 안하며, 지나갈 때 아무런 제약 조건이 없다.

정우는 Type 2,3 도로들을 지날 때 아무런 짐도 트럭에 넣을 수 없다. 오로지 Type 1 도로를 지날 때만 짐을 트럭에 넣을 수 있다.
정우가 맡은 구역은 M개의 도로들과 N개의 도시들로 이루어져있다. 도시들은 1번부터 N번까지 연속적이게 번호가 매겨져있고, 정우는 1번 도시에서 운반을 시작하고 운반을 다 마쳤을 때는 N번 도시에 도착해있어야한다.
정우가 N번 도시에 도착했을 때 트럭이 비어있어야 할 필요는 없다.

정우가 최대 K km 만 이동할 수 있을 때, 1번 도시에서 시작해 N번 도시로 가는 가능한 경우의 수를 구하자.

입력 형식)

첫 줄에 자연수 N, E, K가 주어진다. (2 ≤ N ≤ 50, 1 ≤ E ≤ 2450, 1 ≤ K ≤ 50)
N은 정우가 맡은 구역의 도시 수이고, E는 도로 수, K는 정우가 최대 이동할 수 있는 거리를 의미한다.
다음 M개의 줄 동안 도로의 정보가 주어진다.

• Type 1 - "x y C", x에서 y로 향하는 단방향 도로가 있고, C는 알파벳 대문자이며, C에 해당하는 짐을 트럭에 넣어야한다.
• Type 2 - "x y c", x에서 y로 향하는 단방향 도로가 있고, c는 알파벳 소문자이며, c에 해당하는 짐을 트럭에서 내려야한다.
• Type 3 - "x y", x에서 y로 향하는 평범한 단방향 도로가 있다.

위의 x, y에 대해서 항상 1 ≤ x, y ≤ N, x ≠ y가 성립하며, 어떤 두 도로도 동시에 같은 출발지와 도착지를 같지 않는다.

출력 형식)

정우가 최대 K km 만 이동할 수 있을 때, 1번 도시에서 시작해 N번 도시로 가는 가능한 경우의 수를 출력한다.
경우의 수가 매우 커질 수 있다. 그러므로 총 경우의 수를 10,007로 나눈 나머지를 출력한다.

입력 예제 1)

2 1 10
1 2 a

출력 예제 1)

0

입력 예제 2)

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

출력 예제 2)

4

예제 설명)

1번 예제의 경우, Type 2도로가 내릴 짐이 있는 경우에만 지날 수 있기 때문에 불가능하다.
2번 예제의 경우 다음과 같이 4가지 경우가 가능하다.
1 → 2 → 3 → 4 → 7
1 → 2 → 3 → 7
1 → 2 → 5 → 3 → 6 → 7
1 → 2 → 5 → 3 → 7

출처:koi4u 2011 8 월 모의고사