题目描述

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

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

输入格式

第一行两个整数 $ n $ 和 $ a_1 $，指操作的次数和第一次操作插入的数。
接下来插入的数按如下方法生成：$ ai = (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) $ 异或得到的值。

样例

input

10 1

output

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 $。