题目描述

买菜否开了一家店，号称「一切皆可买」，生意红火。

这天 crx 看到店里面有一个很长的置换 $A$，它的形式非常优美，如果把它表示成排列 $(a_1,a_2,\cdots,a_n)$，对于所有 $i$ 都满足 $a_i=i\bmod n+1$。crx 被深深地吸引了，但他买不起这个置换。好在仁慈的买菜否表示，只要 crx 能求出 $A$ 的特征值，就让 crx 低价买下这个置换。

买菜否把置换 $A$ 的特征值定义为置换 $A$ 能生成的所有不同置换的循环数之和。由于特征值可能很大，只需要求出它模 $10^9+7$ 的余数。

crx 知道，置换 $A$ 能生成的置换是若干个 $A$ 合成的置换，置换 $A$ 的循环数是将置换 $A$ 分解为循环的乘积后循环的个数，如果有多种分解方法则选择最小的循环个数。于是 crx 马上算了起来，过了半小时终于求出了答案。

但是买菜否说：「刚才我等你算答案等得太无聊了，就交换了置换中的两个数，现在你要算新的置换的特征值。」crx 只好重新算了起来，但是他算了没多久就发现买菜否又无聊地交换了置换中的两个数。crx 明白自己计算的速度根本赶不上买菜否交换的速度，他只能记录下买菜否的 $q$ 次操作，请你来求出每次操作后置换的特征值。

输入格式

输入的第一行包含两个整数 $n, q$，分别表示置换的长度和操作次数。

接下来 $q$ 行，第 $i+1$ 行包含两个整数 $x,y$，表示第 $i$ 次交换了数 $x$ 和数 $y$。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次操作后置换的特征值。

4 2
4 3
1 3

8
8

样例说明

第一次交换后，置换变为 $(2,4,3,1)$。它能生成的置换有 $(2,4,3,1),(4,1,3,2)$ 和 $(1,2,3,4)$。

$(2,4,3,1)$ 可以分解为循环 $(1,2,4)$ 和 $(3)$，循环数为 $2$。$(4,1,3,2)$ 可以分解为循环 $(1,4,2)$ 和 $(3)$，循环数为 $2$。

$(1,2,3,4)$ 可以分解为循环 $(1),(2),(3)$ 和 $(4)$，循环数为 $4$。它们的循环数之和为 $8$。

数据范围与提示

对于 $100\%$ 的数据，有 $1\le n\le 10^8$，$1\le q\le 10^5$，$x\ne y$，$1\le x,y\le n$。

尚无数据，请不要提交！求此题数据。

题目来源

2014 年国家集训队十五人互测