Description

默尔索想知道这样一个问题：

给定一个有向图，节点编号从 $1$ 到 $n$（允许重边）。定义"长度为 $t$ 的路径"为恰好经过 $t$ 条边的路径。给定起点 $s$、终点 $e$，以及区间 [$L$, $R$]，请计算从 $s$ 出发到达 $e$ 路径长度在区间 [$L$, $R$]（包含端点）内的路径数之和，对 $M$ 取模。

若输入中多次出现相同的 $u$ $v$，视为多条平行边；每条输入边都作为一条独立边计数。

现在请你告诉他答案。

Format

Input

第一行包含七个整数：$n,m,s,e,L,R,M$

含义分别为:

$n:$节点数、$m:$边数、$s:$起点、$e:$终点、$L:$区间左端、$R:$区间右端、$M:$模。

其中：

$1 ≤ n ≤ 50$

$0 ≤ m ≤ n*(n-1)$（允许无边或重边）

$1 ≤ s, e ≤ n$

$1 ≤ L ≤ R ≤ 10^{18}$

$1 ≤ M ≤ 10^9+7$（$M$ 不必为素数）

接下来 $m$ 行，每行两个整数 $u$ $v$，表示一条有向边 $u$ -> $v$（允许重复的边，重复边各自计数）。

所有输入数以空格或换行分隔。

Output

输出一个整数：从 $s$ 到 $e$ 的路径长度在 [$L$, $R$] 的路径总数对 $M$ 取模后的结果。

Samples

5 6 1 5 2 2 520
1 2
1 3
3 4
3 5
2 4
4 5

1

Limitation

1s, 1024KiB for each test case.