Ana 有一些同学要来她家吃煎饼（在克罗地亚语中被称为 palačinke）。他们将在 $T$ 分钟内到达，而 Ana 刚刚发现制作煎饼所需的四种原料（面粉、牛奶、鸡蛋和果酱）她一样也没有。于是她跳进车里，在社区里开车转悠以购买原料。
她的社区包含 $N$ 个交叉路口（编号为 $1$ 到 $N$）和 $M$ 条连接它们的单向道路。Ana 从 $1$ 号交叉路口出发。每条道路上都恰好有一家商店，出售部分（甚至可能是全部）原料。
如果 Ana 不在商店停留，她通过任意一条道路需要 $1$ 分钟；如果她在商店停留，则需要 $2$ 分钟。她需要买齐所有原料，并及时开车回到 $1$ 号交叉路口。她喜欢对比商店的价格，因此即使她已经集齐了所有原料，她也可能会进入商店。
考虑以下包含 $5$ 个交叉路口和 $7$ 条道路的例子。
Ana 可以通过 $5$ 种不同的方式完成原料采购，如下表所示。
| 第 1 分钟 | 第 2 分钟 | 第 3 分钟 | 第 4 分钟 | 第 5 分钟 | 第 6 分钟 | 第 7 分钟 |
|---|---|---|---|---|---|---|
| $1 \to 3$ | $3 \to \text{shop} \to 4$ | $4 \to \text{shop} \to 1$ | ||||
| $1 \to \text{shop} \to 2$ | $2 \to \text{shop} \to 4$ | $4 \to \text{shop} \to 1$ | ||||
| $1 \to \text{shop} \to 3$ | $3 \to \text{shop} \to 4$ | $4 \to \text{shop} \to 1$ | ||||
| $1 \to \text{shop} \to 3$ | $3 \to \text{shop} \to 4$ | $4 \to 5$ | $5 \to \text{shop} \to 1$ | |||
| $1 \to 3$ | $3 \to \text{shop} \to 4$ | $4 \to \text{shop} \to 5$ | $5 \to \text{shop} \to 1$ |
编写一个程序，计算 Ana 在 $T$ 分钟或更短时间内买齐原料并返回家中的不同方式的数量。由于这个数量可能非常大，请输出它模 $5557$ 的余数。
输入格式
第一行包含两个整数 $N$ 和 $M$（$1 \le N \le 25$，$1 \le M \le 500$），分别表示交叉路口和道路的数量。
接下来的 $M$ 行，每行包含两个不同的整数 $u$ 和 $v$ 以及一个字符串 $s$，它们之间用恰好一个空格分隔。它们描述了一条连接交叉路口 $u$ 和 $v$ 的单向道路，以及位于该道路上的商店所出售的原料 $s$。
字符串 $s$ 将包含 $1$ 到 $4$ 个大写字母。字符 'B' 代表面粉，'J' 代表鸡蛋，'M' 代表牛奶，'P' 代表果酱。
任意两个交叉路口之间最多只有两条直接相连的道路，且仅当它们方向相反时。
最后一行包含一个整数 $T$（$1 \le T \le 1\,000\,000\,000$），表示 Ana 的朋友们到达前的时间（以分钟为单位）。
输出格式
输出的第一行也是唯一一行应当包含 Ana 购买原料的不同方式的数量，模 $5557$。
样例
输入样例 1
3 3 1 2 BMJ 2 3 MJP 3 1 JPB 5
输出样例 1
3
输入样例 2
3 4 1 2 B 2 1 P 1 3 J 3 1 M 8
输出样例 2
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
输出样例 3
5