Time Limit: 5 sec / Memory Limit: 512 MB
Problem Statement
You have a permutation p of N integers. Initially pi=i holds for 1≤i≤N. For each j (1≤j≤N), let's denote p0j=j and pkj=pk−1pj for any k≥1. The period of p is defined as the minimum positive integer k which satisfies pkj=j for every j (1≤j≤N).
You are given Q queries. The i-th query is characterized by two distinct indices xi and yi. For each query, swap pxi and pyi and then calculate the period of updated p modulo 109+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 x1 y1 ⋮ xQ yQ
The first line consists of two integers N and Q (2≤N≤105,1≤Q≤105). The (i+1)-th line consists of two integers xi and yi (1≤xi,yi≤N,xi≠yi).
Output
Print the answer in one line for each query.
Sample Input 1Copy
5 4 2 5 2 4 1 3 1 2
Output for Sample Input 1Copy
2 3 6 5
p changes as follows: [1,2,3,4,5]→[1,5,3,4,2]→[1,4,3,5,2]→[3,4,1,5,2]→[4,3,1,5,2].
Sample Input 2Copy
2 2 1 2 1 2
Output for Sample Input 2Copy
2 1
p changes as follows: [1,2]→[2,1]→[1,2].
Sample Input 3Copy
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 3Copy
2 3 6 4 6 7 12 7 8 9