Stack Truck Driver

A truck driver moves between cities while loading and unloading cargo. The truck can hold any number of items, but its automatic loading device works like a stack. Therefore, only the most recently loaded item can be unloaded first.

There are 26 kinds of cargo, represented by letters. The same letter denotes the same cargo type regardless of case.

Every road is one-way and has length 1km. Passing through a road performs one of three actions.

• A road marked with uppercase C: load one item of type C.
• A road marked with lowercase c: unload one item of type c, but only when the item on top of the stack has that type.
• A road with no letter: pass without loading or unloading anything.

There are N cities and E roads. The driver starts at city 1 and wants to arrive at city N. The truck does not have to be empty when it arrives.

Given that the driver may travel at most Kkm, count the number of ways to arrive from city 1 to city N.

The first line contains the number of cities N, the number of roads E, and the maximum distance K. (2 <= N <= 50, 1 <= E <= 2450, 1 <= K <= 50)

Each of the next E lines describes one road. The format depends on the action performed by that road.

• x y C: a road from x to y. Passing through it loads the cargo type denoted by uppercase C.
• x y c: a road from x to y. Passing through it must unload the cargo type denoted by lowercase c.
• x y: a road from x to y that neither loads nor unloads cargo.

There is never more than one road connecting the same ordered pair of cities. The opposite direction may also have a road, and x is never equal to y.

Print the number of ways to start at city 1 and arrive at city N. Because the number can be very large, print it modulo 10007.