题目背景

译自 COI 2011 T4。

题目描述

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

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

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

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

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

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

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

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

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

输入格式

第一行输入包含三个整数 $N, E$ 和 $K$ $(2 \le N \le 50, 1 \le E \le 2450，1 \le K \le 50)$，分别表示城市数量、道路数量以及 Mirko 在到达目的地前最多可行驶的公里数。

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

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

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

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

上述描述中始终满足 $1 \le x, y \le N, x \ne y$，且 $\text C$ 和 $\text c$ 分别表示大写和小写英文字母。不存在两条不同道路以相同方向连接同一对城市。

输出格式

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

2 1 10 
1 2 a 

0

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 

4