Ana 有一些同学要来她家吃煎饼（在克罗地亚语中被称为 palačinke）。他们将在 $T$ 分钟内到达，而 Ana 刚刚发现制作煎饼所需的四种原料（面粉、牛奶、鸡蛋和果酱）她一样也没有。于是她跳进车里，在社区里开车转悠以购买原料。

她的社区包含 $N$ 个交叉路口（编号为 $1$ 到 $N$）和 $M$ 条连接它们的单向道路。Ana 从 $1$ 号交叉路口出发。每条道路上都恰好有一家商店，出售部分（甚至可能是全部）原料。

如果 Ana 不在商店停留，她通过任意一条道路需要 $1$ 分钟；如果她在商店停留，则需要 $2$ 分钟。她需要买齐所有原料，并及时开车回到 $1$ 号交叉路口。她喜欢对比商店的价格，因此即使她已经集齐了所有原料，她也可能会进入商店。

考虑以下包含 $5$ 个交叉路口和 $7$ 条道路的例子。

Ana 可以通过 $5$ 种不同的方式完成原料采购，如下表所示。

编写一个程序，计算 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