#P18863. [HONI 2009/2010 #4] PALACINKE

[HONI 2009/2010 #4] PALACINKE

题目描述

安娜住在路口 11。还有 TT 分钟朋友就要到了,她要开车买齐面粉、鸡蛋、牛奶和果酱,再回到家。

街区有 NN 个路口和 MM 条单向道路。每条道路上有一家商店,出售四种食材中的若干种。经过一条道路时,如果不进店,耗时 11 分钟。如果进店,则耗时 22 分钟,并取得该店出售的所有种类的食材。即使已经买齐四种食材,也可以继续进店。

求从路口 11 出发,在不超过 TT 分钟内回到路口 11 且买齐四种食材的不同路线数。经过哪些道路以及每次是否进店共同决定一条路线。

输入格式

第一行两个整数 N,MN,M,满足 1≤N≤251\le N\le25、1≤M≤5001\le M\le500。

接下来 MM 行,每行两个不同的整数 u,vu,v 和非空字符串 ss,表示一条从 uu 到 vv 的道路。ss 中的字母 B、J、M、P 分别表示面粉、鸡蛋、牛奶和果酱。同一对路口之间至多有两条道路,若有两条,道路方向相反。

最后一行一个整数 TT,满足 1≤T≤1091\le T\le10^9。

输出格式

输出路线数对 55575557 取模后的结果。

样例

样例 1

输入

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

输出

3

样例 2

输入

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

输出

2

样例 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

输出

5