Mirko is a truck driver. His job is to travel between cities by roads, loading and unloading the cargo. His truck is so big that it can load an unlimited number of packages, but the automated loading system enables only the last loaded package to be unloaded. There exist $26$ different types of packages, each of which is denoted by a letter of the English alphabet.

The cities are connected by one-way roads of length $1$ kilometer. More precisely, there exist $3$ types of roads, conveniently denoted by $1$, $2$, and $3$:

• Type $1$ – each time Mirko drives down the road of this type, he must load exactly one package of the appropriate type for that road.
• Type $2$ – each time Mirko drives down the road of this type, he must unload exactly one package of the appropriate type for that road.
• Type $3$ – Mirko can drive down the road of this type without loading or unloading packages (no loading/unloading).

Mirko is required not to load/unload any cargo except when driving down the roads of type $2$ or $3$, as stated above.

Mirko can travel along $E$ roads connecting $N$ cities. He starts in city $1$ and his goal is to reach city $N$. When arriving in city $N$, Mirko's truck is not required to be empty.

Write a program which computes the number of different ways that Mirko can travel so that he traverses at most $K$ kilometers.

Input Specification

The first line of input contains positive integers $N$, $E$ and $K$ $(2\le N\le 50,1\le E\le 2450,1\le K\le 50)$, which denote the number of cities, the number of roads and the maximum number of kilometers that Mirko may traverse before reaching his destination.

The following $E$ lines contain the description of the roads along which Mirko can travel. Each type of road has its own format:

• Type $1$ – x y C, where $x$ and $y$ are positive integers which describe the direction of the road and $C$ is an uppercase letter of the English alphabet which denotes the type of package that Mirko must load onto the truck.
• Type $2$ – x y c, where $x$ and $y$ are positive integers which describe the direction of the road and $c$ is a lowercase letter of the English alphabet which denotes the type of package that Mirko must unload from the truck.
• Type $3$ – x y, where $x$ and $y$ are positive integers which describe the direction of the road.

In the above formats, the road is traversable when traveling from city $x$ to city $y$. Also, it will always be true that $1\le x,y\le N$, $x\ne y$, and no two roads will connect two cities in the same direction.

Output Specification

In a single line of output, print the number of different ways Mirko can arrive in city $N$, starting from city $1$, while respecting the aforementioned requirements. Since this number can be quite big, print the remainder of that number when divided by $10007$.

Sample Input 1

2 1 10
1 2 a

Sample Output 1

0

Sample Input 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

Sample Output 2

4