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**

4 4 1001 2 a

2 3 b

3 4 a

4 1 b

ans : 2

First of all, instead of constructing the actual graph, lets create a matrix

next_nodes[A][B], storing for each nodeA, using the edges with symbolB, which nodes are possible to reach (mask).Now, let

DP[len][mask]be the number of path lines, of lengthlen, that can be formed using a path that starts in any of the nodes marked inmask.Initialy, DP[0][i] = 1, for 0 < i < 2^n. Then, DP[i][j] will be calculated this way:

For each lowercase letter

c, computenext_mask, that represents the nodes reachable from maskj, using edges with that letter. In other words,next_maskis equal to thebitwise orof allnext_nodes[node][c], ifnodeis part of maskj. Finally, ifnext_mask!= 0, add DP[i-1][next_mask] to DP[i][j].Answer will be at DP[L][2^n-1].

How to write code ?

How to submit?

How to see your result?

I do not submit

How to breathe?

I don't know

task