레이팅 미적용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 unlimited number of packages, but the automated loading system
enables only the last loaded package to be unloaded. There exists 26 different types of packages,
each of which is denoted by a letter of english alphabet.
The cities are connected by o\(ne-wa\)y roads of length 1 kilometer. More precisely, there exists 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
loadi\(ng/un\)loading)
Mirko is required not to lo\(ad/un\)load 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. His starts in the city denoted by number 1 and his
goal is to reach city denoted by number N. When arriving in the city numbered 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 DATA
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 have 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 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
an lowercase letter of 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 are traversible when traveling from the city denoted by x to the city
denoted by 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.
\(8^{th}\) round, May \(14^{th}\), 2011
OUTPUT DATA
In a single line of output, print the number of different ways Mirko can arrive in the city numbered N,
starting from the city numbered 1, while respecting the aforementioned requirements. Since this
number can be quite big, print the remainder of that number when divided by 10007.
EXAMPLE TEST DATA
2 1 10
1 2 a
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
2 1 10
1 2 a
0
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
4