Problem Description

Translated from COCI 2010.02 Task 6 “PALACINKE”.

Anna has some classmates coming over to eat crêpes, but she forgot about it. When she realizes it, she only has $T$ minutes left to make crêpes. She immediately runs out to buy four ingredients: flour B, eggs J, milk M, and jam P.

Around Anna there are $N$ intersections, numbered $1\ldots N$, and $M$ directed roads connecting them. For each road, we know which ingredients are sold in the shop on that road. It is guaranteed that the shop on every road sells at least one of the four ingredients above.

When Anna travels along a road, if she enters the shop on that road to buy something, then it takes her $2$ minutes to pass that road; otherwise, it takes $1$ minute. Even after she has already bought all ingredients, she may still enter shops to buy things.

Anna must start from node $1$ and finally return to node $1$.

Anna needs to obtain all four ingredients within $T$ minutes. Compute how many “shopping plans” she has, modulo $5557$. A shopping plan includes the order of nodes she visits, and for each road whether she buys ingredients or not, but it does not consider what exactly she buys in which shop. For example, when $T=7$, in the figure above there are $5$ shopping plans:

Input Format

The first line: $N, M$.
The next $M$ lines: each line contains two integers $u, v$ and a string $s$ consisting only of characters BJMP. Here, $u, v$ describe a directed road, and $s$ indicates which ingredients are sold in the shop on that road. It is guaranteed that no two directed roads are identical (but there may be two roads connecting the same pair of nodes with opposite directions).
Line $N+2$: $T$.

Output Format

One line with one integer, the number of shopping plans Anna has.

3 3
1 2 BMJ
2 3 MJP
3 1 JPB
5

3

3 4
1 2 B
2 1 P
1 3 J
3 1 M
8

2

5 7
1 2 B
2 4 M
1 3 J
3 4 MB
4 1 JP
4 5 J
5 1 P
7

5

Hint

Constraints: $1\le N\le 25$, $1\le M\le 500$, $1\le T\le 10^9$.
It is guaranteed that no two directed roads are identical (but there may be two roads connecting the same pair of nodes with opposite directions).

Translated by ChatGPT 5