레이팅 미적용베시(Bessie)와 이웃 농장의 소 친구들은 마침내 농부들에 맞서는 동맹을 결성하기 위해 오솔길로 농장들을 연결하기 시작하기로 결정했다. N개 (1 <= N <= 100,000)의 농장 각각의 소들은 처음에 정확히 다른 한 농장으로 오솔길을 하나씩 지으라는 지시를 받았으므로, 오솔길은 총 N개가 될 예정이었다. 하지만 프로젝트가 몇 달이나 지난 지금, 실제로 지어진 오솔길은 M개 (1 <= M < N)뿐이다.
어느 농장이 이미 오솔길을 지었는지를 둘러싼 농장 간의 다툼이 이제 소 동맹을 갈라놓을 위기에 처했다. 긴장을 완화하기 위해, 베시는 지금까지 존재하는 M개의 오솔길이 지어졌을 수 있는 방법의 수를 계산하고 싶어 한다. 예를 들어 농장 3과 4를 연결하는 오솔길이 있다면, 농장 3이 그 오솔길을 지었을 가능성과 농장 4가 지었을 가능성이 있다. 오솔길을 지은 농장에 오솔길을 배정하는 서로 다른 방법의 수를 1,000,000,007로 나눈 나머지를 계산하여 베시를 도와주자. 두 배정에서 서로 다른 농장이 지은 오솔길이 적어도 하나 있으면, 두 배정은 서로 다른 것으로 간주한다.
첫째 줄: 공백으로 구분된 두 정수 N과 M
둘째 줄부터 1+M번째 줄까지: i+1번째 줄은 i번째 오솔길을 설명한다. 각 줄에 오솔길로 연결된 농장 쌍을 나타내는, 공백으로 구분된 두 정수 u_i와 v_i (1 <= u_i, v_i <= N, u_i != v_i)가 주어진다.
오솔길을 농장에 배정하는 방법의 수를 1,000,000,007로 나눈 나머지를 한 줄에 출력한다. 위 조건을 만족하는 배정이 없으면 0을 출력한다.
alliance.in · 출력을 쓸 파일 alliance.out5 4
1 2
3 2
4 5
4 56Input details: Note that there can be two trails between the same pair of farms.
Output details: There are 6 possible assignments.