地牢路径之谜

题目描述

当 Sally Face 和一行人发现了波隆那香肠的真实成分后，情况空前严峻险恶，可他们却又不能去相信腐败不堪的警局，惩罚杀人凶手的任务落到了这几个高中生的肩上。这时，Ashley 发现了隐藏的输送管道，却不小心摔入了深不见底的管道。Sally Face 的超自然本能指引着一行人发现了爱迪生大楼隐秘的地牢……

在破败尘封的地牢大门前，赫然刻着那代表邪恶力量的符号，Sally Face 走向角落里一本封面是一只鸟的古代书籍：

「地牢面对凡人的呼唤，会投以邪恶的灵魂，只有正确回答了所有询问：从某个圆点 $S_i$ 开始到某个圆点 $T_i$ 结束，路径长度 $\leq k$ 的不同路径的 路径长度的 $r_i$ 次方和 为多少，无法全部回答的人将永远被诅咒……」

Sally Face 看了看地牢大铁门前的地砖，上面的圆点和边构成了一张错综复杂的图，他发现每一条边的长度都为 1，且任意两点 $u,v$（由于地牢的时空扭曲，存在 $u,v$ 使得 $u=v$）间可能存在多条边，而右边是密密麻麻的古老的文字。

「Todd，你试一试能不能解开这个谜团……」

输入格式

第一行五个正整数 $n, m, r, k, q$。
其中：

• $n$ 为地砖上的圆点数，
• $m$ 为连接圆点的边的数量，
• $q$ 为询问的个数，
• $r$ 为询问中 $r_i$ 的最大值，
• $k$ 为题目描述中路径长度的上限。

接下来 $m$ 行，每行两个正整数 $u, v$，表示圆点 $u, v$ 间存在一条边。

之后 $q$ 行，每行三个正整数 $S_i, T_i, r_i\ (1 \leq i \leq q)$，含义与题目描述一致。

输出格式

对于每个询问，输出一行一个数字，表示该询问的答案（路径长度 $\leq k$ 的不同路径的路径长度的 $r_i$ 次方和）。
由于答案可能很大，只需输出对 $1004535809$ 取模后的结果。

样例输入

4 3 3 4 2
1 2
3 2
2 4
3 4 2
1 2 3

样例输出

52
82

样例解释

询问 1：从 3 到 4，$r_i=2$

• 长度为 2 的路径：1 条（$3 \rightarrow 2 \rightarrow 4$），贡献 $1 \times 2^2 = 4$
• 长度为 4 的路径：3 条（$3 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 4$、$3 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4$、$3 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 4$），贡献 $3 \times 4^2 = 48$
• 总答案：$4 + 48 = 52$

询问 2：从 1 到 2，$r_i=3$

• 长度为 1 的路径：1 条（$1 \rightarrow 2$），贡献 $1 \times 1^3 = 1$
• 长度为 3 的路径：3 条（$1 \rightarrow 2 \rightarrow 3 \rightarrow 2$、$1 \rightarrow 2 \rightarrow 1 \rightarrow 2$、$1 \rightarrow 2 \rightarrow 4 \rightarrow 2$），贡献 $3 \times 3^3 = 81$
• 总答案：$1 + 81 = 82$

数据范围

对于 100% 的数据，满足：

• $n = 5$
• $1 \leq m \leq 10^4$
• $0 \leq r_i \leq 1000$
• $1 \leq k \leq 10^9$
• $1 \leq q \leq 25000$
• 数据保证随机

提示

由于地牢的时空扭曲是常人无法理解的，所以不存在一条长度为 0 的路径 $(u \rightarrow v)$（其中 $u=v$）。