题目描述

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)$ 异或得到的值。

（注：根据样例和题面描述，应该是所有 $\text{ans}_i$ 异或，包括 $\text{ans}_1$，但输出描述中写的是 $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$。