순열의 주기

$N$개의 정수로 이루어진 순열 $p$가 있다. 처음에는 $1 \le i \le N$에 대해 $p_i = i$이다. 각 $j \ (1 \le j \le N)$에 대해 $p^0_j = j$, 그리고 $k \ge 1$인 임의의 $k$에 대해 $p^k_j = p^{k-1}_{p_j}$로 정의하자. $p$의 주기는 모든 $j \ (1 \le j \le N)$에 대해 $p^k_j = j$를 만족하는 최소 양의 정수 $k$이다.

$Q$개의 질의가 주어진다. $i$번째 질의는 서로 다른 두 인덱스 $x_i$와 $y_i$로 주어진다. 각 질의마다 $p_{x_i}$와 $p_{y_i}$를 교환한 뒤 갱신된 $p$의 주기를 $10^9 + 7$로 나눈 나머지를 순서대로 계산한다.

$p$의 주기는 항상 존재함을 증명할 수 있다.

입력은 다음과 같은 형식의 단일 테스트 케이스로 이루어진다.

$N \ Q$
$x_1 \ y_1$
$\vdots$
$x_Q \ y_Q$

첫째 줄에는 두 정수 $N$과 $Q$가 주어진다 ($2 \le N \le 10^5, 1 \le Q \le 10^5$). $(i+1)$번째 줄에는 두 정수 $x_i$와 $y_i$가 주어진다 ($1 \le x_i, y_i \le N, x_i \ne y_i$).

각 질의마다 답을 한 줄에 하나씩 출력한다.