3437. 卡车运输

单点时限: 5.0 sec

内存限制: 256 MB

卡车司机运输货物,货物装在集装箱中,集装箱有 26 种不同类型,每种类型的集装箱用一个英文字母表示。卡车容量非常大,能装下任意多的集装箱。

城市里有三种类型道路,司机开过第一种类型道路,则必须将指定类型的集装箱装上车;开过第二种类型道路,则必须将指定类型的集装箱卸下车,否则不能通行,但是司机在卸载时只能卸载最后一个装上车的集装箱;开过第三种类型道路,则不装载也不卸载任何集装箱。

城市有 个结点, 条有向道路。卡车司机从 号结点出发,出发时卡车是空的,最后停在 号结点,此时卡车上可以有集装箱也可以没有。司机可以重复经过每条道路和每个结点,但他经过的道路总条数不能超过 ,请问有多少种合法的路线可供选择?

输入格式

第一行:三个整数 ,

接下来 行,每行首先有两个整数,表示这条道路的起点和终点,如果这条道路是第一种类型的,用一个大写英文字母表示,如果是第二种类型的,用小写英文字母表示,如果是第三种类型的,则没有任何字母。

没有重边和自环。

  • 对于 的数据,满足
  • 对于 的数据,满足

输出格式

输出一个整数,表示合法的路线方案数,由于答案可能比较大,输出模 的余数。

样例

Input
2 1 10
1 2 a
Output
0
Input
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
Output
4

提示

可能会重复经过同一个结点。

四种路线方案:

1->2->3->7
1->2->3->4->7
1->2->5->3->6->7
1->2->5->3->7

8 人解决,9 人已尝试。

13 份提交通过,共有 29 份提交。

5.7 EMB 奖励。

创建: 2 年,1 月前.

修改: 2 年,1 月前.

最后提交: 1 年,12 月前.

来源: COCI 2011

题目标签
DP