为了打倒邪恶管理员 Skip 蚤，跳蚤国王决定“以其人之道还治其人之身”。

跳蚤国王事先在 Skip 蚤的电脑中留下了后门。跳蚤国王计划通过后门攻破管理员 skip 蚤。

一个后门可以用一个非空序列$A$表示，攻破这个后门需要花费的时间为 $S(A)$。

对于长度为 $n$ 的序列 $A=\{A_0,A_1,\cdots ,A_{n-1}\}$，定义 ${\mathrm{s}\mathrm{c}\mathrm{r}}_{k,c}(A)$ 为将下标模 $k$ 等于 $c$ 的位置抽出组成的序列，保证 $c\le k-1\le n-1$，即 ${\mathrm{s}\mathrm{c}\mathrm{r}}_{k,c}(A)=\{A_c,A_{k+c},A_{2k+c},\cdots \}$。

对于任意一个序列 $A$ 定义权值函数 $S(A)$：

$$S(A)=\{\begin{array}{lr}{A}_0,& \text{for }|A|=1,\\ \sum _{d=2}^{|A|}\sum _{c=0}^{d-1}S({\mathrm{scr}}_{d,c}(A)),& \text{otherwise.}\end{array}$$

现在，你已经知道了 Skip 蚤的电脑的后门，和表示它的长为 $n$ 的序列 $A$。

求出攻破它花费的时间 $S(A)$ 的值，答案对 $2^{32}$ 取模。

由于本题中 $n$ 较大，为避免文件操作占用过多时间，序列 $A$ 将由随机数生成器生成。本题的标准解法不依赖该随机性。

输入格式

一行，两个整数，分别为 $n,seed$。

随机数生成器的 C++ 代码如下 ：

namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned read()
    {
        b=((z1<<6)^z1)>>13;
        z1=((z1&4294967294U)<<18)^b;
        b=((z2<<2)^z2)>>27;
        z2=((z2&4294967288U)<<2)^b;
        b=((z3<<13)^z3)>>21;
        z3=((z3&4294967280U)<<7)^b;
        b=((z4<<3)^z4)>>12;
        z4=((z4&4294967168U)<<13)^b;
        return (z1^z2^z3^z4);
    }
    void srand(int x)
    {
        z1=x;
        z2=(~x)^0x233333333U;
        z3=x^0x1234598766U;
        z4=(~x)+51;
    }
}
using namespace GenHelper;

您要首先调用一次 srand(seed) ，然后连续调用 $n$ 次 read() ，第 $i$ 次的返回值即为 $A_{i-1}$。在 $0\sim 2^{32-1}$ 的范围内。

输出格式

输出一行一个整数，表示 $S(A)mod{2}^{32}$。

样例一

input

3 1

output

1484747852

explanation

生成的序列为 $\{535855898,2903825961,3745143011\}$

样例二

input

5 2

output

16835609

样例三

input

100 3

output

2637589059

限制与约定

对于所有数据， $1\le n\le 2\times {10}^6,1\le seed\le {10}^8$。

时间限制 : $1\mathtt{\text{s}}$。

空间限制 : $256\mathtt{\text{MB}}$。

下载

样例数据下载