Migrated from Lutece 2783 比游戏还刺激

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

MichaelZona 和 laduiw 玩了一下午卡牌，在某一时刻，他突然觉得卡牌也没那么有意思。他想到了一个更刺激的事情！比游戏还刺激！

正值五一假期，MichaelZona 决定拉着 laduiw 去清水河人民公园探险。清水河人民公园有一片有趣的湖泊叫南湖。南湖上有 $n$ 个石墩和 $m$ 个石桥。石墩从 $0$ 到 $n-1$ 编号，石桥连接了这些石墩。你可能觉得这是只一个普通的人工湖，但是为了追求刺激，MichaelZona 在南湖里投入了 $k$ 条扬子鳄。不过不用担心，每条扬子鳄都有一个固定的活动路线，并且活动周期为 $2$ 或 $3$ 或 $4$，比如如果一条扬子鳄的活动路线为 $2-3-4$ ，那么它的活动周期为 $3$，在第 $0$ ~ $4$ 时刻它出现的位置就分别为 $2-3-4-2-3$.

现在 MichaelZona 让 laduiw 从一个起点 $start$ 出发，经历 $T$ 个时间后到达终点 $finish$，每个点（石墩）都可以重复经过。不过 MichaelZona 并不想让 laduiw 与扬子鳄正好在同一时刻出现在同一个石墩，因为这样可能会发生很坏的事情。所以他想知道 laduiw 有多少种活动路线。

可以保证，MichaelZona 并不会让扬子鳄在第 $0$ 时刻出现在 $start$ 上。

Input

输入第一行为五个整数，分别为 $n,m,start,finish,T.$

接着输入 $m$ 行，每行两个整数 $u,v$，表示从石墩 $u$ 到石墩 $v$ 有一个石桥。

第 $m+2$ 行为一个整数，表示 $k$。

接着输入 $k$ 行，表示每条扬子鳄的行动规律。每行第一个数 $per$ 表示活动周期，后面跟着 $per$ 个数，表示活动路线。

Output

输出为 $1$ 行，表示方案数。这个数可能很大，所以请你对 $10000$ 取模。

Samples

6 8 1 5 3
0 2
2 1
1 0
0 5
5 1
1 4
4 3
3 5
1
3 0 5 1

2

Constraints

$1 \leq n \leq 50$

$1 \leq T \leq 2000000000$

$1 \leq k \leq 20$

Resources

2022 UESTC ICPC Training for Dynamic Programming