Hello codeforces community. can you help me problem on the dp.
task in russian

Consider an oriented graph G having n vertices numbered by positive integers from 1 to n. In the graph G, there may be several arcs between the same pair of vertices, as well as arcs leading from the vertex to it. Each arc of the graph is marked by some letter of the Latin alphabet. Each path in graph G can be put in correspondence with a string consisting of letters written on successively paths that pass through this path. This is the pathname of the path. We call the string S the path line of the graph G if there exists a path in it whose path label is S.

Your task is to calculate the remainder of dividing by 1 000 000 the number of waypoints of graph G consisting of exactly L symbols.

**Input**

The first line of the input data contains integers n, m, L (1 ≤ n ≤ 10, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 100) equal to the number of vertices and edges of the graph G, and also the length of the path lines that need to look for. The next m rows define the arcs of the graph G. Each of these lines contains two natural numbers a, b (1 ≤ a, b ≤ n) and a small Latin letter c, which means the presence of an arc from the vertex a to the vertex b marked with the symbol c. Elements of each line are separated from each other by spaces.

**Output**

The only output line must contain one number equal to the remainder of dividing the number of path lines of length L in column G by 1 000 000.

**Test**