CF1425B.Blue and Red of Our Faculty!

It's our faculty's 34th anniversary! To celebrate this great event, the Faculty of Computer Science, University of Indonesia (Fasilkom), held CPC - Coloring Pavements Competition. The gist of CPC is two players color the predetermined routes of Fasilkom in Blue and Red. There are $N$ Checkpoints and $M$ undirected predetermined routes. Routes $i$ connects checkpoint $U_i$ and $V_i$, for $(1 \le i \le M)$. It is guaranteed that any pair of checkpoints are connected by using one or more routes.

The rules of CPC is as follows:

• Two players play in each round. One player plays as blue, the other plays as red. For simplicity, let's call these players $Blue$ and $Red$.
• $Blue$ will color every route in he walks on blue, $Red$ will color the route he walks on red. Both players start at checkpoint number $1$. Initially, all routes are gray.
• Each phase, from their current checkpoint, $Blue$ and $Red$ select a different gray route and moves to the checkpoint on the other end of the route simultaneously.
• The game ends when $Blue$ or $Red$ can no longer move. That is, there is no two distinct gray routes they can choose to continue moving.

Chaneka is interested in participating. However, she does not want to waste much energy. So, She is only interested in the number of final configurations of the routes after each round. Turns out, counting this is also exhausting, so Chaneka asks you to figure this out!

Two final configurations are considered different if there is a route $U$ in a different color in the two configurations.

这是我们学院成立34周年纪念日！为庆祝这一盛事，印度尼西亚大学计算机科学学院（Fasilkom）举办了“CPC——路面涂色竞赛”（Coloring Pavements Competition）。CPC 的核心规则是：两名选手轮流将 Fasilkom 校园内预先设定的路径分别涂成蓝色与红色。共有 $N$ 个检查点（Checkpoints）和 $M$ 条无向的预设路径。第 $i$ 条路径连接检查点 $U_i$ 和 $V_i$（其中 $1 \le i \le M$）。保证任意两个检查点之间均存在一条或多条路径相连（即图连通）。

CPC 的具体规则如下：

• 每轮由两名玩家参与：一名扮演蓝色方，另一名扮演红色方。为叙述简便，我们称他们为 $Blue$ 和 $Red$。
• $Blue$ 将其走过的每条路径涂成蓝色，$Red$ 将其走过的每条路径涂成红色。双方均从编号为 $1$ 的检查点出发；初始时，所有路径均为灰色。
• 在每一阶段中，双方从当前所处的检查点出发，各自选择一条不同的灰色路径，并同时沿该路径移动至该路径另一端的检查点。
• 游戏在 $Blue$ 或 $Red$ 无法继续行动时结束。即：不存在两条互不相同的灰色路径可供双方同时选择以继续移动。

Chaneka 对参赛很感兴趣，但她不愿耗费过多精力。因此，她只关心每轮游戏结束后路径颜色配置的总数。然而，手动计数同样十分费力，于是 Chaneka 请求你来解决这个问题！

若两种最终配置中存在某条路径 $U$ 的颜色不同，则认为这两种配置互不相同。

The first line contains two integers $N$ and $M$. $N$ $(2 \le N \le 2 \cdot 10^3)$ denotes the number of checkpoints, $M$ $(1 \le M \le 2 \cdot N)$ denotes the number of routes. It is guaranteed that every checkpoint except checkpoint $1$ has exactly two routes connecting it.

The next $M$ lines each contains two integers $U_i$ and $V_i$ $(1 \le U_i, V_i \le N, U_i \ne V_i)$, which denotes the checkpoint that route $i$ connects.

It is guaranteed that for every pair of checkpoints, there exists a path connecting them directly or indirectly using the routes.

第一行包含两个整数 $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$ 条路径所连接的两个检查点。

保证任意两个检查点之间均存在一条（直接或间接）路径通过这些路径相连。

Output a single integer which denotes the number of final configurations after each round of CPC modulo $10^9 + 7$

输出一个整数，表示每轮 CPC 后的最终配置数量对 $10^9 + 7$ 取模的结果。

Every possible final configuration for the example is listed below:

The blue-colored numbers give the series of moves $Blue$ took, and the red-colored numbers give the series of moves $Red$ took.

以下列出了该示例中所有可能的最终局面：

蓝色数字表示 $Blue$ 所执行的操作序列，红色数字表示 $Red$ 所执行的操作序列。