Blue and Red of Our Faculty!

题意翻译

每回合有两名选手比赛。一个蓝色，另一个红色。 蓝色会给他走的每一条路涂上蓝色，红色会把他走的路涂成红色。两个玩家都从1号检查站开始。最初，所有路线都是灰色的。 每个阶段，从当前的检查点，蓝色和红色选择不同的灰色路线，并同时移动到路线另一端的检查点。 当蓝色或红色不再移动时游戏结束。也就是说，他们没有两条截然不同的灰色路线可以选择继续前进。 求每一轮的路线数。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

8

说明

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.