#214358. [COI 2011] 卡车 / KAMION

译自 COI 2011 T4。

Mirko 找到了一份卡车司机的工作。他的任务是在城市间的道路上行驶，同时进行货物的装货和卸货。Mirko 的卡车容量非常大，可以装载无限量的货物，但由于自动化装卸系统的限制，他只能卸下最后装上卡车的货物。总共有 种不同类型的货物，分别用英文字母表示。

城市之间通过单向道路连接，每条道路恰好长 公里，Mirko 在这些道路上需要进行货物的装货/卸货操作。具体来说，存在三种类型的道路，分别用数字 、、 标识，其规则如下：

1. 每当 Mirko 经过此类道路时，必须装载一个该道路指定的特定类型货物。

2. 每当 Mirko 经过此类道路时，必须从卡车上卸下一个该道路指定的特定类型货物。

3. Mirko 可以自由通过此类道路，无需任何操作。

除了在通过道路时必须执行的操作外，Mirko 不得进行任何其他装卸货操作。

Mirko 可以在总共 条道路上行驶，这些道路连接着 个城市。Mirko 初始位于编号为 的城市，他的目标是到达编号为 的城市。到达城市 时，卡车不需要为空。

请编写程序计算 Mirko 在最多行驶 公里的条件下，有多少种不同的方式可以完成这段旅程。

注意：解中可能包括多次经过城市 的路径，只要旅程最终在该城市结束即可。换句话说，所有城市和道路都可以被多次访问（但每次通过道路时都需要重新遵守对应的通行规则）。

第一行输入包含三个整数 和 ，分别表示城市数量、道路数量以及 Mirko 在到达目的地前最多可行驶的公里数。

接下来 行描述 Mirko 可以行驶的道路。由于存在三种不同类型的道路，它们在输入中的描述方式也不同。以下列表对应上述道路类型（按编号对应）：

1. 需要装载货物类型 的道路将以 x y C 的格式表示，其中 和 为自然数， 为任意一个大写英文字母。该格式表示存在从城市 到城市 的道路，且 Mirko 在通过时必须装载类型为 的货物。

2. 需要卸货类型 的道路将以 x y c 的格式表示，其中 和 为自然数， 为小写英文字母。该格式表示存在从城市 到城市 的道路，且 Mirko 在通过时必须卸下类型为 的货物。

3. 可自由通行的道路将以 x y 的格式表示，其中 和 为自然数。该格式表示存在从城市 到城市 的道路，Mirko 通过时无需任何操作。

上述描述中始终满足 ，且 和 分别表示大写和小写英文字母。不存在两条不同道路以相同方向连接同一对城市。

输出一行，包含从城市 到达城市 的合法路径数量。由于该数值可能很大，请输出其除以 的余数。

样例输入 1

2 1 10 
1 2 a 

样例输出 1

0

样例输入 2

7 9 5 
1 2 A 
2 3 B 
2 5 
5 3 C 
3 4 b 
3 6 c 
3 7 
4 7 a 
6 7 a 

样例输出 2

4