꽃을 밟지 마세요

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

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

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

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

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

첫째 줄에 섬의 수 $N$과 다리의 수 $M$이 띄어쓰기로 구분되어 주어진다. 이후 $M$개의 줄에 걸쳐 $M$개의 다리에 대한 정보가 주어진다. $i+1$번째 줄에 $$번째 다리가 연결하는 두 개의 섬의 번호가 공백으로 구분되어 주어진다.

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

• $2 \leq N \leq 200 \ 000$
• $N - 1 \leq M \leq 500 \ 000$