[Zjoi2005]Swamp 沼泽鳄鱼

潘塔纳尔沼泽地号称世界上最大的湿地，位于巴西中部马托格罗索州南部。每当雨季来临，这里碧波荡漾、生机盎然，吸引了许多游客。

为了增添游玩的乐趣，人们在池塘中央修建了若干座石墩和石桥。每座石桥连接两座石墩，任意两座石墩之间至多有一座石桥。然而，这个景点建成后一直没有对外开放，因为池塘中生活着许多危险的食人鱼。

豆豆先生酷爱冒险，得知这个消息后，立刻赶到池塘，准备成为第一个在桥上游览的人。经过仔细勘察，他发现食人鱼的运动路线具有周期性，周期只可能是 $2$ 、 $3$ 或 $4$ 个单位时间。每个单位时间内，食人鱼会从一座石墩游到另一座石墩。每当食人鱼到达一座石墩时，如果石墩上有人，它就会发动攻击；食人鱼未到达石墩时不会攻击人。

豆豆已经掌握了所有食人鱼的运动规律，现在需要设计自己的行动路线。每个单位时间内，他必须沿一座石桥从当前石墩走到另一座石墩，不能停留在原地。如果豆豆与某条食人鱼在同一时刻到达同一座石墩，豆豆就会遭到袭击。

豆豆选定了起点石墩 $\mathrm{Start}$ 和终点石墩 $\mathrm{End}$ 。他希望从 $\mathrm{Start}$ 出发，经过恰好 $K$ 个单位时间后到达 $\mathrm{End}$ 。所有石墩都可以被重复经过，包括 $\mathrm{Start}$ 和 $\mathrm{End}$ 。请计算不会遭到食人鱼攻击的合法路线数量。

输入格式

输入共包含 $M+2+\mathrm{NFish}$ 行。

第一行包含五个正整数 $N$ 、 $M$ 、 $\mathrm{Start}$ 、 $\mathrm{End}$ 和 $K$ ，分别表示石墩数量、石桥数量、起点石墩编号、终点石墩编号以及路线经过的单位时间数。石墩编号为 $0$ 到 $N-1$ 。

接下来的 $M$ 行，每行包含两个整数 $x$ 和 $y$ ，满足 $0\le x,y\le N-1$ ，表示一座连接石墩 $x$ 和石墩 $y$ 的石桥。

随后一行包含一个整数 $\mathrm{NFish}$ ，表示食人鱼的数量。

接下来的 $\mathrm{NFish}$ 行，每行描述一条食人鱼的运动规律。每行的第一个整数为 $T$ ，其中 $T$ 为 $2$ 、 $3$ 或 $4$ ，表示该食人鱼的运动周期。接下来包含 $T$ 个整数 $P_0,P_1,\ldots,P_{T-1}$ ，表示食人鱼在一个周期内依次到达的石墩：

当 $T=2$ 时，食人鱼按照 $P_0,P_1,P_0,P_1,\ldots$ 的顺序运动；
当 $T=3$ 时，食人鱼按照 $P_0,P_1,P_2,P_0,\ldots$ 的顺序运动；
当 $T=4$ 时，食人鱼按照 $P_0,P_1,P_2,P_3,P_0,\ldots$ 的顺序运动。

豆豆出发时，所有食人鱼都位于各自路线中的 $P_0$ ，且这些位置均不是 $\mathrm{Start}$ 。

输出格式

输出合法路线数量除以 $10^4$ 所得的余数。

样例输入

样例输出

数据范围

$1\le N\le 50$ ；
$1\le K\le 2\times 10^9$ ；
$1\le \mathrm{NFish}\le 20$ 。

来源与许可

本题为 ZJOI 2005 试题「Swamp 沼泽鳄鱼」，题面与测试数据整理自 BZOJ。

样例 1

输入