PinkRabbit 是一位人赢。

福州市可以抽象成一个 $n$ 个点 $m$ 条边的，不包含重边与自环的无向图，PinkRabbit 住在 $1$ 号点，而他的妹子住在 $2$ 号点。

某一天，PinkKitten 施放了一个大魔法，让这个无向图上所有的边都变成了单向边。现在 PinkRabbit 关心的是他是否能够和他的妹子见面。

具体地，PinkRabbit 能和他的妹子见面，当且仅当存在一个点 $u$，满足新图上从 $1$ 号点出发能够到达 $u$，从 $2$ 号点出发也能到达 $u$。

现在你需要计算出，在把所有 $m$ 条边进行定向的所有 $2^m$ 种方案中，有多少种方案能让 PinkRabbit 和他的妹子见面。你只需输出其对 $10^9 + 7$ 取模后的结果。

输入格式

第一行三个正整数，分别为 $n$、$m$、$id$。$n$ 和 $m$ 为图的点数和边数，$id$ 为子任务编号。

接下来有 $m$ 行，每行两个正整数 $x$ 和 $y$，描述一条边。

输出格式

输出一个整数表示答案。

样例

样例输入 1

3 2 1
1 3
2 3

样例输出 1

3

说明 1

这个样例的 $id = 1$，满足子任务 $1$ 的 $m \le 20$ 限制。

合法的方案有 $3$ 种：

(1) $1 \to 3, 2 \to 3$

(2) $1 \to 3, 3 \to 2$

(3) $3 \to 1, 2 \to 3$

样例输入 2

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

样例输出 2

30

样例输入 3

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

样例输出 3

55

数据范围与提示

本题采取子任务捆绑测试。

子任务 $1$ ($30$ 分)：$m \le 20$；

子任务 $2$ ($15$ 分)：$1$ 和 $2$ 之间有唯一的一条简单路径；

子任务 $3$ ($20$ 分)：$n \le 10$；

子任务 $4$ ($35$ 分)：无特殊限制。

对于所有的数据，$1 \le n \le 15$，$1 \le m \le \frac{n(n-1)}{2}$，$1 \le x < y \le n$。