스택 트럭 운전사

한 운전사는 도시들을 이동하며 트럭에 짐을 싣거나 내린다. 트럭의 용량은 제한이 없지만, 자동 적재 장치는 스택처럼 동작한다. 따라서 가장 나중에 실은 짐만 먼저 내릴 수 있다.

짐은 알파벳 26종류로 나타낸다. 같은 알파벳은 대소문자와 관계없이 같은 종류다.

모든 도로는 일방통행이며 길이는 1km이다. 도로를 지날 때 수행되는 동작은 세 가지 중 하나다.

• 대문자 C가 붙은 도로: C 종류의 짐 하나를 싣는다.
• 소문자 c가 붙은 도로: 스택 맨 위의 짐이 c와 같은 종류일 때만 그 짐 하나를 내릴 수 있다.
• 알파벳이 없는 도로: 짐을 싣거나 내리지 않고 지나간다.

도시는 N개, 도로는 E개가 있다. 운전사는 1번 도시에서 출발해 N번 도시에 도착하려고 한다. 도착했을 때 트럭에 짐이 남아 있어도 된다.

최대 Kkm만 이동할 수 있을 때, 1번 도시에서 N번 도시로 도착하는 방법의 수를 구하시오.

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

다음 E개 줄에는 도로의 정보가 주어진다. 도로의 동작에 따라 형식이 다르다.

• x y C: x에서 y로 가는 도로이다. 이 도로를 지날 때 대문자 C에 해당하는 짐을 싣는다.
• x y c: x에서 y로 가는 도로이다. 이 도로를 지날 때 소문자 c에 해당하는 짐을 내려야 한다.
• x y: x에서 y로 가는 도로이며, 짐을 싣거나 내리지 않는다.

같은 방향으로 같은 두 도시를 잇는 도로는 두 개 이상 주어지지 않는다. 반대 방향의 도로는 따로 주어질 수 있으며, x와 y가 같은 경우는 없다.

1번 도시에서 출발해 N번 도시로 도착하는 방법의 수를 출력한다. 수가 매우 커질 수 있으므로 10007로 나눈 나머지를 출력한다.