#3185. [Coci2011]kamion

题目描述

一个有向图有n个点，m条有向边。边分为3类。A类边供应特定的物品，当你经
过一条A类边时，会得到相应的物品；B类边需求特定的物品，当且仅当你最近一次
得到的物品是此B类边所需时，你才能通过这条B类边并且失去这个物品；经过C类
边没有任何影响。你想知道，从点1出发经过不超过K条边到达点n的路径数量（模10007）。

输入格式

输出格式

样例

样例输入

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

数据范围与提示

n, K <= 50, m <= 2450.