#P18863. [HONI 2009/2010 #4] PALACINKE
[HONI 2009/2010 #4] PALACINKE
题目描述
安娜住在路口 。还有 分钟朋友就要到了,她要开车买齐面粉、鸡蛋、牛奶和果酱,再回到家。
街区有 个路口和 条单向道路。每条道路上有一家商店,出售四种食材中的若干种。经过一条道路时,如果不进店,耗时 分钟。如果进店,则耗时 分钟,并取得该店出售的所有种类的食材。即使已经买齐四种食材,也可以继续进店。
求从路口 出发,在不超过 分钟内回到路口 且买齐四种食材的不同路线数。经过哪些道路以及每次是否进店共同决定一条路线。
输入格式
第一行两个整数 ,满足 、。
接下来 行,每行两个不同的整数 和非空字符串 ,表示一条从 到 的道路。 中的字母 B、J、M、P 分别表示面粉、鸡蛋、牛奶和果酱。同一对路口之间至多有两条道路,若有两条,道路方向相反。
最后一行一个整数 ,满足 。
输出格式
输出路线数对 取模后的结果。
样例
样例 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