20531번 - 인간관계

S인터넷고등학교에는 $N$명의 학생이 있다. 이들 사이에 몇몇은 서로 친구 관계를 맺고 있다. 친구 관계는 다음 세 가지 조건을 만족한다.

1. 모든 학생은 자기 자신의 친구이다.
2. 학생 $x$가 학생 $y$의 친구이면, 학생 $y$도 학생 $x$의 친구이다.
3. 학생 $x$와 학생 $y$가 친구이고, 학생 $y$와 학생 $z$가 친구이면, 학생 $x$와 학생 $z$도 친구이다.

S인터넷고등학교의 김준원 선생님은 학생들의 친구 관계에 대해 알고 싶다. 다행히, 일부 학생 간의 친구 관계에 대한 정보는 이미 주어져있다. 김준원 선생님을 위해 전체 학생들의 친구 관계로 가능한 경우의 수를 구해보자.

두 친구 관계가 다름은 하나의 친구 관계에서는 친구지만, 다른 친구 관계에서는 친구가 아닌 두 학생이 존재함을 의미한다.

입력이 특수한 방식으로 주어지니, 입력과 출력 부분의 설명을 자세히 읽는 것을 권장한다.

학생의 수 $N$과 정수 $M$이 사이에 공백을 두고 주어진다.

이후 $M$개의 줄 중 $i (1 \le i \le M)$번째 줄에는 두 정수 $x_i, y_i $가 주어진다.

$M$개의 줄에 걸쳐 총 $M$개의 문제에 대한 답을 출력한다.

$i(1 \le i \le M)$번째 줄에는 $(x_1, y_1), (x_2, y_2), \cdots, (x_i, y_i)$의 (총 $i$개의 쌍의) 학생이 친구 관계에 있음을 알 때, 전체 친구 관계로 가능한 경우의 수를 $10^9+7$로 나눈 나머지를 출력한다.

• $1 \le N \le 5\,000$
• $1 \le M \le 100\,000$
• $1 \le x_i, y_i \le N$