问题描述

你有一个包含 $N$ 个整数的排列 $p$。初始情况下，对于 $1 \le i \le N$，有 $p_i = i$。对于每个 $j$（$1 \le j \le N$），记 $p^0_j = j$，$p^k_j = p^{k-1}_{p_j}$ 对于任意 $k \ge 1$。$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)$-th 行包含两个整数 $x_i$ 和 $y_i$ （$1 \le x_i, y_i \le N, x_i \ne y_i$）。

输出

对于每个查询，输出一行答案。

样例输入 1

5 4
2 5
2 4
1 3
1 2

样例输出 1

2
3
6
5

$p$ 的变化如下：$\[1,2,3,4,5\] \to \[1,5,3,4,2\] \to \[1,4,3,5,2\] \to \[3,4,1,5,2\] \to \[4,3,1,5,2\]$。

样例输入 2

2 2
1 2
1 2

样例输出 2

2
1

$p$ 的变化如下：\[1,2\] \to \[2,1\] \to \[1,2\]。

样例输入 3

10 10
5 6
5 9
8 2
1 6
8 1
7 1
2 6
8 1
7 4
8 10

样例输出 3

2
3
6
4
6
7
12
7
8
9