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

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

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

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

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

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

现在，你已经知道了 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)\bmod 2^{32}$。

样例一

input

3 1

output

1484747852

explanation

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

样例二

input

5 2

output

16835609

样例三

input

100 3

output

2637589059

限制与约定

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

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

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

下载

样例数据下载