Ana 举办一个在家同学聚会，当同学们还有 T 分钟就要到时，他发现自己还少准备了四样东西。(flour, milk, eggs and jam). 于是他驾车到附近准备购买这些东西。附近有 N 个地点 被标记成 1 to N, 以及 M 条单向道路。 Ana 从地点1出发。路上他可以直接到下一地点（要1分钟），或购买了东西后到下一地点（要2分钟）当然路上有可能买不完所有的东西。当然他可以在到下一地点的路上买。以下是一个关于 5个点7条路的例子。

Ana有5种不同的方法，如下表。

编程计算他在不超过T分钟买完东西并回到地点1的方案总数，由于答案较大，输出对5557求余后的结果。
输入：
第一行两个整数 N 和 M ($1 \le N \le 25, 1 \le M \le 500$), 表示点数和道路条数。.
以下 M 行 每行包涵两个整数u 和 v 和 1个字符串s,用1个空格分开。表示地点 u 到 v有一条单向路,且路上可买的东西是 s.
字符串 s 的长度为1到4且由大写字母构成。字符 'B' 表示flour,字符'J'表示eggs, 字符'M' 表示milk 以及字符 'P'表示 jam.
两点间最多有两条直接相连的有向路且，它们方向不相同。
最后一个整数T ($1 \le T \le 1 000 000 000$), 表示他同学还有T分才到达。
输出：
一个整数表示方法总数对 5557的余数.

SAMPLE TESTS
Input:
3 3
1 2 BMJ
2 3 MJP
3 1 JPB
5
Output:
3

Input:
3 4
1 2 B
2 1 P
1 3 J
3 1 M
8
Output:
2
Input:
5 7
1 2 B
2 4 M
1 3 J
3 4 MB
4 1 JP
4 5 J
5 1 P
7
Output:
5