MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 16px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

Problem Statement

You have a permutation $p$ of $N$ integers. Initially $p\_i = i$ holds for $1 \\le i \\le N$. For each $j \\ (1 \\le j \\le N)$, let's denote $p^0\_j = j$ and $p^k\_j = p^{k-1}\_{p\_j}$ for any $k \\ge 1$. The period of $p$ is defined as the minimum positive integer $k$ which satisfies $p^k\_j = j$ for every $j \\ (1 \\le j \\le N)$.

You are given $Q$ queries. The $i$-th query is characterized by two distinct indices $x\_i$ and $y\_i$. For each query, swap $p\_{x\_i}$ and $p\_{y\_i}$ and then calculate the period of updated $p$ modulo $10^9 + 7$ in the given order.

It can be proved that the period of $p$ always exists.

Input

The input consists of a single test case of the following format.

$N \\ Q$ $x\_1 \\ y\_1$ $\\vdots$ $x\_Q \\ y\_Q$

The first line consists of two integers $N$ and $Q$ ($2 \\le N \\le 10^5, 1 \\le Q \\le 10^5$). The $(i+1)$-th line consists of two integers $x\_i$ and $y\_i$ ($1 \\le x\_i, y\_i \\le N, x\_i \\ne y\_i$).

Output

Print the answer in one line for each query.

Sample Input 1

5 4
2 5
2 4
1 3
1 2

Output for Sample Input 1

2
3
6
5

$p$ changes as follows: $\[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\]$.

Sample Input 2

2 2
1 2
1 2

Output for Sample Input 2

2
1

$p$ changes as follows: \[1,2\] \\to \[2,1\] \\to \[1,2\].

Sample Input 3

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

Output for Sample Input 3

2
3
6
4
6
7
12
7
8
9