Problem Description

Translated from COCI 2010.02 T6 "PALACINKE"

Ana has several classmates coming over for crepes, but she forgot about it. By the time she realized, she only had $T$ minutes left to bake the crepes. She immediately rushed out to buy four ingredients: flour B, eggs J, milk M, and jam P.

Ana's neighborhood consists of $N$ intersections numbered from $1$ to $N$, and there are $M$ one-way roads connecting them. Each road has stores that sell certain ingredients, and it is guaranteed that each road's stores sell at least one of the four mentioned ingredients.

When Ana traverses a road, if she enters the store on that road to buy something, it takes her $2$ minutes to pass, otherwise it takes $1$ minute. Even if she has already bought all the ingredients, she can still enter stores to buy more.

Ana needs to start from intersection $1$ and eventually return to $1$.

Ana must gather all four ingredients within $T$ minutes. How many different ways can she do this, modulo $5557$? The ways include the order of nodes she passes through and whether she buys ingredients on each road, but not which specific store she buys from. For example, when $T=7$, there are $5$ ways in the diagram above:

Input Format

The first line contains $N$ and $M$.
The next $M$ lines each contain two integers $u$ and $v$, and a string $s$ consisting only of characters BJMP, indicating a one-way road from $u$ to $v$ and the ingredients sold at the store on that road. It is guaranteed that no two roads are identical (but there may be two roads connecting the same nodes in opposite directions).
The $(N+2)$-th line contains $T$.

Output Format

A single line with the answer, representing the number of ways Ana can gather the ingredients, modulo $5557$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

3

Sample Input #2

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

Sample Output #2

2

Sample Input #3

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

Sample Output #3

5

Notes

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

见题面 Input 部分

见题面 Output 部分