今天是我们教师成立 34 周年!为了庆祝这一盛事,印度尼西亚大学计算机科学学院(Fasilkom)举办了 CPC - 路面着色比赛。 CPC 的要点是两名玩家将 Fasilkom 的预定路线涂成蓝色和红色。有$$$N$$$检查站和$$$M$$$无向预定路线。路线 $$$i$$$ 连接检查点 $$$U_i$$$ 和 $$$V_i$$$,$$$(1 \le i \le M)$$$。保证任意一对检查点都使用一条或多条路由连接。
CPC规则如下:
- 每轮有两名玩家参加。一名玩家扮演蓝色角色,另一名玩家扮演红色角色。为简单起见,我们将这些玩家称为 $$$Blue$$$ 和 $$$Red$$$。
- $$$Blue$$$ 将为他行走的每条路线着色为蓝色,$$$Red$$$ 将为他行走的路线着色为红色。两名玩家都从编号为 $$$1$$$ 的检查点开始。最初,所有路线都是灰色的。
- 每个阶段,从当前检查点开始,$$$Blue$$$ 和 $$$Red$$$ 选择不同的灰色路线,并同时移动到路线另一端的检查点。
- 当$$$Blue$$$或$$$Red$$$无法再移动时游戏结束。也就是说,他们没有两条不同的灰色路线可以选择继续移动。
Chaneka 有兴趣参与。不过,她不想浪费太多的精力。所以,她只对每轮之后路线的最终配置数量感兴趣。事实证明,计算这个也很累人,所以查内卡请你弄清楚这一点!
如果两个配置中存在不同颜色的路线 $$$U$$$,则认为两个最终配置不同。
输入
第一行包含两个整数 $$$N$$$ 和 $$$M$$$。 $$$N$$$ $$$(2 \le N \le 2 \cdot 10^3)$$$ 表示检查点数量,$$$M$$$ $$$(1 \le M \le 2 \cdot N)$$$ 表示路线数量。保证除了$$$1$$$检查点之外的每个检查点都恰好有两条路线连接它。
接下来的 $$$M$$$ 行每行包含两个整数 $$$U_i$$$ 和 $$$V_i$$$ $$$(1 \le U_i, V_i \le N, U_i \ne V_i)$$$,表示路由 $$$i$$$ 连接的检查点。
保证对于每对检查点,都存在一条使用路由直接或间接连接它们的路径。
输出
输出一个整数,表示每轮 CPC 模 $$$10^9 + 7$$$ 后的最终配置数
示例
输入 #1
5 6 1 2 2 3 3 4 4 1 1 5 5 1
输出 #1
8
注意
下面列出了该示例的每种可能的最终配置:
蓝色数字给出 $$$Blue$$$ 采取的一系列行动,红色数字给出 $$$Red$$$ 采取的一系列行动。