P5188 [COCI 2009/2010 #4] PALACINKE

**译自 [COCI 2010.02](http://hsin.hr/coci/archive/2009_2010/) T6「[PALACINKE](http://hsin.hr/coci/archive/2009_2010/contest4_tasks.pdf)」** 安娜有几个同学过来吃可丽饼，然而安娜忘了这事。当安娜发现时，留给她烤可丽饼的时间只剩下 $T$ 分钟了。她马上跑出去采购四样原材料：面粉 `B`，鸡蛋 `J`，牛奶 `M` 和果酱 `P`。 安娜周边有 $N$ 个路口，编号为 $1\ldots N$，还有 $M$ 条单向道路连接它们。已知每条路上的商店会卖哪些材料，保证每条路上的商店至少会卖（上述四种材料中）的一种。  安娜穿过一条道路时，如果她进入了这条路上的商店买东西，则她通过这条路耗时 $2$ 分钟，否则耗时 $1$ 分钟。即使她买完了所有原材料仍可以进店买东西。 安娜需要从 $1$ 开始，最终回到 $1$。 安娜需要在 $T$ 分钟内采购到四种原材料。请问她有多少种「采购方式」，答案对 $5557$ 取模。采购方式包含了她经过的结点的次序，以及她在每条路上买不买材料，但不计她在哪个商店买了什么。例如，当 $T=7$ 时，在上图中有 $5$ 种采购方式： 

无

无

$1\le N\le 25,$ $1\le M\le 500,$ $1\le T\le 10^9$. 保证没有两条单向道路相同（但可能有两条连接的结点相同，而方向相反的道路）。