题目描述

小珅和小泽在玩一款战争游戏。但小珅没有着急立马去进攻，而是姑且先让小泽轻松一下，小珅准备先采取一种奇怪阵法来形成战斗力。

这套阵法有一个战斗力系数 $k$，最终战斗力和士兵数量息息相关：

如果士兵数量为 $1$ 则战斗力就是 $1$。

假设有 $n$ ($n > 1$) 名士兵

先需要把士兵平分成 $x$ 个小组。这里 $x$ 必须大于 $1$、必须是 $n$ 的因子（不然怎么叫平分）、且必须是所有满足前面条件的数中最小的一个。

因为是平分，此时每个小组的人数都是 $\frac{n}{x}$。最终战斗力就是所有小组用同样战斗力系数算出的战斗力之和再乘以 $k$ 再对 $10^9 + 7$ 取模后的结果。

由此，在不考虑整型溢出的情况下，可以用下面这个递归程序，算出 $n$ 名士兵，战斗力系数为 $k$ 时的最终战斗力（显然在战斗力超过 int 范围时计算会错误）。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1'000'000'000 + 7;
int f(int n, int k)
{
    if (n == 1)
        return 1;
    for (int x = 2; x <= n; x++) // x>1
        if (n % x == 0)       // x 是 n 的因子
        {
            int sum = 0;
            for (int i = 1; i <= x; i++)
                sum += f(n / x, k);
            return sum * k % MOD;
        }
}
int main(){
    int n,k;
    cin>>n>>k;
    cout<<f(n,k);
    return 0;
}

接下来需要计算的不只是某一个人数对应的战斗力。给定整数 $m,k$，请使用同一个战斗力系数 $k$，分别计算士兵数量为 $1,2,\ldots,m$ 时的战斗力，再将这 $m$ 个结果全部进行按位异或，输出最终的异或值。每个人数对应的战斗力都按上述规则对 $10^9+7$ 取模。

忽略运行时间和整数溢出时，可以把上面程序的主函数替换成下面的枚举程序，理解题目要求。正式解题还需要根据数据规模优化计算方法。

int main(){
    int m,k,ans=0;
    cin>>m>>k;
    for(int i=1;i<=m;i++) ans^=f(i,k);
    cout<<ans;
    return 0;
}

输入格式

两个整数，$m, k$。

输出格式

一个整数，即答案。

输入输出样例

输入 #1

1 33

输出 #1

1

输入 #2

5 2

输出 #2

25

说明/提示

19999717 1

1

9284 82

408701663

9728 22

483220759

数据范围

对于 $100\%$ 的数据，$1 \le m \le 2 \times 10^7$，$1 \le k \le 100$。

子任务 $1$（$10$ 分）：保证 $k = 1$。

子任务 $2$（$20$ 分）：保证 $m \le 10^4$。

子任务 $3$（$30$ 分）：保证 $m \le 10^6$。

子任务 $4$（$40$ 分）：没有特殊限制。