给定 n,d,计算
ans=∑0≤x,y,z<n(x⊕y⊕z)dmod
输入格式
两个整数 n, d。
输出格式
输出整数 \mathrm{ans}。
样例数据
样例输入
10 3
样例输出
718116
子任务
对于子任务 1(10\%):0 < n \leq 300,d \leq 3。
对于子任务 2(10\%):0 < n \leq 5\,000,d \leq 3。
对于子任务 3(20\%):0 < n \leq 10^5,d \leq 3。
对于子任务 4(20\%):0 < n \leq 2^{30},d \leq 3。
对于子任务 5(20\%):0 < n \leq 2^{30},d \leq 10。
对于子任务 6(20\%):0 < n \leq 2^{30},d \leq 10^5。