题目背景

热爱自然，热爱生命。

题目描述

求 unsigned long long 自然溢出情境下的的自然幂和。

即，求 $\sum_{k=0}^{n-1}k^m$ 对 $2^{64}$ 取模的值。

注意，我们认为 $0^0=1$。

输入格式

输入一行两个整数，$m,n$，中间用单个空格隔开。

输出格式

输出一行一个整数，即 $\sum\limits_{0\le k<n}k^m\bmod2^{64}$。

样例输入输出

由于数目过多，请见附加文件 sample.zip 中的 nature*.in/ans。

基本按照下方测试点分布的方式造数据，共 $50$ 组。

强烈建议把所有样例都测一遍，避免细节处写挂。

这里再额外提供几组手搓样例。

5 3

33

$0^5+1^5+2^5=33$。

10 5

1108650

$0^{10}+1^{10}+2^{10}+3^{10}+4^{10}=1108650$。

114 514

17546076543575202049

1919 810

13042575244352582345

114514 1919810

167479551601740961

数据范围与提示

对于所有数据，$0\le m\le10^7$，$1\le n\le10^{18}$。

为了方便选手得分，我们给出了大量部分分，会正解的选手可以忽略。

本题各测试点等分。以下是测试点分布。

测试点编号	$m$	$n$	测试点编号	$m$	$n$	测试点编号	$m$	$n$
$1\sim2$	$=0$	$\le10^{18}$	$37\sim38$	$\le16$	$=10^8$	$69\sim70$	$\le10$	$\le10^8$
$3\sim4$	$=1$		$39\sim40$	$\le32$		$71\sim72$		$\le10^9$
$5\sim6$	$=2$		$41\sim42$	$\le64$		$73\sim74$		$\le10^{10}$
$7\sim8$	$=3$		$43\sim44$	$\le10^4$		$75\sim76$		$\le10^{18}$
$9\sim10$	$=4$		$45\sim46$	$\le10^5$		$77\sim78$	$\le10^3$	$\le10^8$
$11\sim12$	$=5$		$47\sim48$	$\le16$	$=10^9$	$79\sim80$		$\le10^9$
$13\sim14$	$=9$		$49\sim50$	$\le32$		$81\sim82$		$\le10^{10}$
$15\sim16$	$=16$		$51\sim52$	$\le64$		$83\sim84$		$\le10^{18}$
$17\sim18$	$=25$		$53\sim54$	$\le16$	$=5\times10^9$	$85\sim86$	$\le10^6$	$\le10^8$
$19\sim20$	$=64$		$55\sim56$	$\le32$		$87\sim88$		$\le10^9$
$21\sim22$	$=100$		$57\sim58$	$\le64$		$89\sim90$		$\le10^{10}$
$23\sim24$	$=1024$		$59\sim60$	$\le3000$	$\le3000$	$91\sim92$		$\le10^{18}$
$25\sim26$	$=4096$		$61\sim62$	$\le10^7$		$93\sim94$	$\le10^7$	$\le10^8$
$27\sim28$	$=10^4$		$63\sim64$		$\le10^6$	$95\sim96$		$\le10^9$
$29\sim30$	$=10^5$	$\le10^8$	$65\sim66$	$\le10^4$	$\le5\times10^6$	$97\sim98$		$\le10^{10}$
$31\sim32$		$\le10^9$	$67\sim68$	$\le10^7$		$99\sim100$		$\le10^{18}$
$33\sim34$		$\le10^{10}$
$35\sim36$		$\le10^{18}$

请注意本题特殊的时空限制：时限 $\rm200ms$，空限 $\rm256MB$。

因为数据范围较小，所以无法排除部分高复杂度做法通过。

题解等资料可以在附加文件中找到。