该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

hyk 最近在玩一款游戏

这款游戏中，玩家们要扮演海盗在海上打捞发掘宝藏，每次出发需要凑足 $n$ 个玩家，以入队顺序编号分别为 $1 \sim n$

在找到宝藏以后，玩家们需要进行一轮 "内战" 来让自己获得更多的宝藏

"内战" 的规则是这样的：

所有人站成一圈，每回合所有玩家会同时向自己顺时针方向的下一个玩家进行一次攻击

对于两个编号为 $x,y$ 的玩家，如果这一回合游戏是 $x$ 向 $y$ 发动攻击，若 $x,y$ 的最大公约数不为 $1$，则认为此次攻击有效，那么 $y$ 将出局

例如有五个玩家 $x1,x2,x3,x4,x5$ 排成一圈

第一回合满足 $gcd(x2,x3) != 1$ 则 $x3$ 出局，剩余 $x1,x2,x4,x5$

第二回合满足 $gcd(x1,x5) != 1,gcd(x1,x2) != 1$ 则 $x1,x2$ 出局，剩余 $x4,x5$

第三回合发现 $gcd(x4,x5)==1$，则游戏结束

现在 hyk 想知道，如果已经知道 $n$ 个玩家一开始的站位，能有多少个玩家留到最后均分宝藏？

输入格式

第一行 $n,m,K$，其中 $n$ 是人数,$m,K$ 为生成初始站位的参数

这 $n$ 个人的初始站位由以下代码生成,生成的 $a[i]$ 即为第 $i$ 个人的编号

// 请注意生成函数中的所有类型必须为 int
int K;
int get_number(){
	K = K * 214013 + 2531011;
	return (abs(K)) % n + 1;
}

for (int i = 1; i <= n; ++i){
	a[i] = i;
}
for (int i = 1; i <= m; ++i){
	x = get_number(), y = get_number();
	swap(a[x], a[y]);
}

输出格式

输出一个整数，表示能留到最后的玩家个数

数据范围

对于 $50\%$ 的数据：$n\leq 1000$。

对于 $80\%$ 的数据：$n\leq 10^5$。

对于 $100\%$ 的数据：$1\leq n\leq 10^6,m\leq 10^6,K$ 在 $int$ 范围内。

样例输入1

6 0 0

样例输出1

6

样例输入2

100000 100000 99997

样例输出2

55942