题目描述
JOHNKRAM 在冬令营的时候被 wys 的卡常题坑了。他表示非常不爽,于是决定也出一道卡常题来祸害人。
有一个多重集,初始时为空。JOHNKRAM 进行了 n 次操作,每次操作往多重集内插入一个整数。第 i(1≤i≤n) 次操作完之后他会问你这个多重集内第 2n+1 小的数是多少。为了防止你的工作量过大,你只需要把每次询问的答案异或起来得到的值告诉他即可。
输入格式
第一行两个整数 n 和 a1,指操作的次数和第一次操作插入的数。
接下来插入的数按如下方法生成:ai=(1714636915×ai−1+1681692777)×(846930886×ansi−1+1804289383)mod1000000007。其中 ansi−1 指第 i−1 次询问的答案。
输出格式
输出一个整数,表示所有 ansi(1<i<n) 异或得到的值。
样例
10 1
943960841
数据范围与提示
对于 30% 的数据,n≤3×193;
对于 50% 的数据,n≤1×106;
对于 100% 的数据,1≤n≤3×107,1≤a1<1000000007。