题目描述

JOHNKRAM 在冬令营的时候被 wys 的卡常题坑了。他表示非常不爽，于是决定也出一道卡常题来祸害人。

有一个多重集，初始时为空。JOHNKRAM 进行了 $n$ 次操作，每次操作往多重集内插入一个整数。第 $i(1 \leq i \leq n)$ 次操作完之后他会问你这个多重集内第 $\frac{n + 1}{2}$ 小的数是多少。为了防止你的工作量过大，你只需要把每次询问的答案异或起来得到的值告诉他即可。

输入格式

第一行两个整数 $n$ 和 $a_1$，指操作的次数和第一次操作插入的数。
接下来插入的数按如下方法生成：$ a_i = (1714636915 \times a_{i - 1} + 1681692777) \times (846930886 \times \text{ans}_{i - 1} + 1804289383) \bmod 1000000007 $。其中 $\text{ans}_{i - 1}$ 指第 $i - 1$ 次询问的答案。

输出格式

输出一个整数，表示所有 $\text{ans}_i (1 < i < n)$ 异或得到的值。

10 1

943960841

数据范围与提示

对于 $30\%$ 的数据，$n \leq 3 \times 19 ^ 3$；
对于 $50\%$ 的数据，$n \leq 1 \times 10 ^ 6$；
对于 $100\%$ 的数据，$ 1 \leq n \leq 3 \times 10 ^ 7, 1 \leq a_1 < 1000000007 $。