34959번 - 꽃을 밟지 마세요 서브태스크

문제

SSHS 제도(諸島)는 1ドル$부터 $N$까지 번호가 붙여진 $N$개 섬으로 이루어져 있으며, 각 섬에는 오직 그 섬에서만 피어나는 특별한 종의 꽃이 피어 있다. 사람들은 SSHS 제도에서만 피어나는 $N$가지의 특별한 꽃들을 얻기 위해 $N$개의 섬을 연결하는 $M$개의 다리를 건설했다. 그리고 다리를 통해 섬들을 이동하며 손으로 꽃을 재배해 왔다. 각 다리는 서로 다른 두 개의 섬을 양방향으로 연결하며, 어떤 두 섬 사이에는 최대 하나의 다리가 건설되어 있다.

SSHS 제도의 수석 과학자인 재원이는 꽃을 재배하는 과정을 자동화하기 위해, $N$가지 종류의 꽃을 모두 재배할 수 있는 최첨단 로봇을 만들었다. 로봇에게 $N$개의 섬을 방문할 순서를 순열 $(a_1,a_2,\cdots ,a_N)$으로 정해주기만 하면, 로봇은 정해준 순서대로 다리를 통해 섬들을 이동하며 꽃을 재배한다. 즉, 위 순열이 주어졌을 때 로봇이 $i$번째로 방문하는 섬은 $a_i$번 섬이다. 순열 $(a_1,a_2,\cdots ,a_N)$이 주어졌을 때, 로봇이 섬을 방문하는 방법은 아래와 같다.

• 로봇은 $a_1$번 섬에 있는 꽃을 재배한다. 이후 로봇은 $N-1$번의 이동을 통해 다른 섬으로 이동하여 나머지 꽃들을 재배한다.
• $i$번째 이동에서 로봇은 $a_{i}$번 섬에서 $a_{i+1}$번 섬을 잇는 단순 경로, 즉 같은 섬을 두 번 이상 지나지 않는 경로 중 하나를 임의로 선택하여 이동한다. 이후 $a_{i+1}$번째 섬에 있는 꽃을 재배한다.

그러나 이 로봇은 아직 프로토타입이라서 $a_i$번째 섬에서 $a_{i+1}$번째 섬으로 이동하면서 아직 꽃을 재배하지 않은 섬을 지나갈 경우 해당 섬에 있는 꽃을 밟게 된다.

재원이는 로봇이 꽃을 밟지 않도록 고치는 대신, 순열 $(a_1,a_2,\cdots ,a_N)$을 잘 정하기만 한다면 로봇이 어떻게 이동하더라도 꽃을 밟지 않고 이동할 수 있다는 것을 알아냈다. 이러한 순열 $(a_1,a_2,\cdots ,a_N)$의 개수를 구해보자.

입력

첫째 줄에 섬의 수 $N$과 다리의 수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐 $M$개 다리에 대한 정보가 주어진다. $i+1$번째 줄에 $i$번째 다리가 연결하는 두 개의 섬의 번호 $u_i, v_i$가 공백으로 구분되어 주어진다.

출력

첫째 줄에 로봇이 어떤 경로를 선택하더라도 꽃을 밟지 않고 이동할 수 있음이 보장되는 순열 $(a_1,a_2,\cdots ,a_N)$의 개수를 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

• 2ドル\leq N\leq 200\ 000$
• $N-1\leq M\leq 500\ 000$
• 1ドル \leq u_i,v_i \leq N,ドル $u_i \neq v_i$ (1ドル \leq i \leq N$)
• 주어지는 다리를 통해 모든 섬이 연결된다.
• 서로 다른 두 개의 섬을 잇는 다리는 최대 한 개이다.

서브태스크

노트