Giải bài trực tuyến

Mirko là tài xế xe tải. Công việc hàng ngày của anh là chuyên chở hàng hoá ði các thành phố. Chiếc xe tải của anh có thể chở ðược một lượng khối hàng tuỳ ý, tuy nhiên, nó chỉ cho phép Mirko mỗi lần ðược dỡ ra khối hàng nằm trên cùng (có thể coi xe tải của Mirko như 1 stack). Có 26 loại hàng hoá khác nhau, chúng ðược kí hiệu bằng các chữ cái trong bảng kí tự alphabet.

Thành phố của Mirko gồm các con ðường 1 chiều, với ðộ dài mỗi con ðường là 1km. Ở thành phố này, MIrko chỉ di chuyển trên 3 loại ðường sau:
- Loại 1: mỗi lần Mirko lái xe qua con ðường này, anh ta phải chất thêm ðúng 1 khối hàng ứng với con ðường ðó
- Loại 2: mỗi lần Mirko lái xe qua con ðường này, anh ta phải dỡ xuống khối hàng trên cùng của xe, và phải ðúng với yêu cầu trên ðường này
- Loại 3: mỗi lần Mirko lái xe qua con ðường này, anh ta không cần chất thêm/dỡ ði bất kì khối hàng nào
Lưu ý, ngoài các thao tác trên, Mirko không ðược phép lấy thêm hàng ở bất kì chỗ nào khác, cũng như không ðược dỡ bỏ hàng ở dọc ðường.

Hàng ngày, Mirko sẽ xuất phát ở thành phố 1, di chuyển qua các con ðường, và kết thúc chuyến ði ở thành phố N. Ban ðầu, xe Mirko không chở hàng, và khi kết thúc, các khối hàng có thể vẫn còn ở trên xe của Mirko.

Yêu cầu: cho biết mạng lưới các con ðường trong thành phố, hãy viết chương trình ðếm số cách Mirko có thể lái xe tải trên chặng ðường không quá K km. Mirko có thể ði qua 1 thành phố nhiều lần, miễn sao thoả mãn ðược các yêu cầu ðã cho.

Input
- Dòng ðầu tiên của input gồm 3 số nguyên N,M,K (2 <= N <= 50, 0 < M < 2450, 0 < K <= 50)
- M dòng tiếp theo mô tả các con ðường trong thành phố. Mỗi dòng sẽ có dạng như sau:
+ Loại 1: "x y C", với 1 <= x,y <= N và C là 1 kí tự in hoa (từ 'A'..'Z') mô tả có 1 con ðường từ x ðến y, và Mirko cần chất thêm 1 khối hàng C lên xe
+ Loại 2: "x y c", với 1 <= x,y <= N và c là 1 kí tự in thường (từ 'a'..'z') mô tả có 1 con ðường từ x ðến y, và Mirko cần dỡ bỏ 1 khối hàng c ra khỏi xe
+ Loại 3: "x y", với 1 <= x,y <= N, mô tả có 1 con ðường từ x ðến y.
- Dữ liệu ðảm bảo với mỗi con ðường, x khác y, và không có 2 con ðường nào nối cùng 1 cặp thành phố theo chung 1 hướng

Output:
- Trên dòng duy nhất, in ra số cách Mirko có thể thực hiện ðược chuyến ði của mình, lấy modulo 10007

Example:
Input
2 1 10
1 2 a
Output
0

Input
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
Output
4