XB 家附近有 N 个十字路口，共由 M 条单行道相连。XB 家住在编号为 1 的十字路口附近，所以他会从 1 出发。每条路上都恰好有一家店铺出售这 4 种原料中的 1 种或多种。
XB 喜欢货比三家，所以就算他已经买来了某家店铺出售的所有原料，他还是会走进这家店铺看看。如果 XB 没有进入一条路上的店铺的话，他只需要 1 分钟时间通过这条路，否则他需要多花 1 分钟时间逛店铺。
下面是 N=5，M=7，T=7 的情况：
那么 XB 在7分钟内的行走路线为以下 5 种：
XB 想知道，在他的朋友来之前，也就是 T 分钟的时间内，他有多少种不同的行走路线，满足从 1 出发，购买到所有 4种原料后再返回 1。
第一行包括 2 个正整数 N，M，表示十字路口的数量以及单行道的数量。
接下来 M 行包括两个不同的正整数 u 和 v，以及一个字符串 s，分别用空格隔开。表示有一条 u 到 v 的单行道，并且这条路上的店铺出售的原料为 s。s 会包含 1 到 4 个字符，'B' 代表面粉，'J' 代表鸡蛋，'M' 代表牛奶，'P' 代表奶油。不含重边和自环。
最后一行包括 1 个正整数 T，表示 XB 朋友在 T 分钟之后来。
## 样例 #1
### 样例输入 #1
```
3 3
1 2 BMJ
2 3 MJP
3 1 JPB
5
```
### 样例输出 #1
```
3
```
## 样例 #2
### 样例输入 #2
```
3 4
1 2 B
2 1 P
1 3 J
3 1 M
8
```
### 样例输出 #2
```
2
```
## 样例 #3
### 样例输入 #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
```