题目描述

在国家 Olympia 中有 $N$ 个居民点，编号为 $1$ 到 $N$。Olympia 建有若干条直接的、双向的道路，连接不同的居民点，并且满足以下规则：

• 每个居民点都有相同数量的直接相邻居民点；
• 对于任意两个不同且有直接道路相连的居民点，恰好存在 $A$ 个其他居民点，它们分别都与这两个居民点有直接道路相连；
• 对于任意两个不同且没有直接道路相连的居民点，恰好存在 $B$ 个其他居民点，它们分别都与这两个居民点有直接道路相连；
• 任意两个居民点之间不会有超过一条直接道路；
• 不存在从某个居民点出发又回到它自身的直接道路。

每条直接道路的长度都认为是 $1$。对于任意一对不同居民点，上述 $A$ 和 $B$ 的值都是相同的。

请编写程序 roads：给定两个居民点编号 $X,Y$ 和一个正整数 $L$，求从 $X$ 到 $Y$ 的长度恰好为 $L$ 的路径数量。

路径定义为一个顶点序列，序列中任意相邻两个顶点之间都有直接道路。路径中可以多次经过同一条直接道路，也可以多次经过同一个居民点。

输入格式

第一行输入两个正整数 $N,M$，分别表示居民点数量和直接道路数量。

接下来 $M$ 行，每行输入两个正整数 $j,k$，满足 $1 \le j,k \le N$，表示居民点 $j$ 与居民点 $k$ 之间有一条直接道路。

最后一行输入三个正整数 $X,Y,L$。

输出格式

输出一行一个整数，表示从居民点 $X$ 到居民点 $Y$ 的长度为 $L$ 的路径数量。

由于答案可能很大，请输出答案对 $1\,000\,000\,007$ 取模后的结果。

数据范围

• $1 \le N \le 100000$；
• $1 \le M \le 250000$；
• $1 \le X,Y \le N$；
• $1 \le L \le 10^9$。

样例

输入

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

输出

3

样例解释

有 $5$ 个居民点，每个居民点有 $2$ 个相邻居民点；任意两个直接相邻的居民点有 $0$ 个公共邻居；任意两个不直接相邻的居民点有 $1$ 个公共邻居。

从居民点 $1$ 到居民点 $2$，长度为 $3$ 的三条路径为：

• $1-2-1-2$；
• $1-2-3-2$；
• $1-5-1-2$。

评分方式

• 子任务 1（10 分）：$N \le 10,\ M \le 15,\ L \le 12$；
• 子任务 2（10 分）：$N \le 100,\ M \le \dfrac{N(N-1)}2,\ L \le 6000$；
• 子任务 3（20 分）：$N \le 100,\ M \le \dfrac{N(N-1)}2,\ L \le 10^9$；
• 子任务 4（30 分）：$N \le 2000,\ M \le 250000,\ L \le 10^9$；
• 子任务 5（30 分）：$N \le 100000,\ M \le 250000,\ L \le 10^9$。

某个子任务的分数只有在通过该子任务全部测试点时才能获得。