题目背景

热爱自然，热爱生命。

---

题目描述

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

即，求

$$S = \sum_{k=0}^{n-1} k^m \quad \text{对} \quad 2^{64} \ \text{取模的值} $$

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

---

输入格式

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

---

输出格式

输出一行一个整数，即

$$\sum_{0 \le k < n} k^m \bmod 2^{64}$$

---

样例

样例 1

输入：
5 3
输出：
33

解释：$0^5 + 1^5 + 2^5 = 0 + 1 + 32 = 33$

样例 2

输入：
10 5
输出：
1108650

解释：$0^{10} + 1^{10} + 2^{10} + 3^{10} + 4^{10} = 0 + 1 + 1024 + 59049 + 1048576 = 1108650$

样例 3

输入：
114 514
输出：
17546076543575202049

样例 4

输入：
1919 810
输出：
13042575244352582345

样例 5

输入：
114514 1919810
输出：
167479551601740961

---

数据范围与提示

对于所有数据：

• $0 \le m \le 10^7$
• $1 \le n \le 10^{18}$

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

本题各测试点等分。以下是测试点分布（部分）：

测试点编号	$m$ 范围	$n$ 范围	测试点编号	$m$ 范围	$n$ 范围
1~2	$=0$	$\le 10^{18}$	37~38	$\le 16$	$=10^8$
3~4	$=1$		39~40	$\le 32$
5~6	$=2$		41~42	$\le 64$
7~8	$=3$		43~44	$\le 10^4$
9~10	$=4$		45~46	$\le 10^5$
11~12	$=5$		47~48	$\le 16$	$=10^9$
13~14	$=9$		49~50	$\le 32$
15~16	$=16$		51~52	$\le 64$
17~18	$=25$		53~54	$\le 16$	$=5\times 10^9$
19~20	$=64$		55~56	$\le 32$
21~22	$=100$		57~58	$\le 64$
23~24	$=1024$		59~60	$\le 3000$
25~26	$=4096$		61~62	$\le 10^7$
27~28	$=10^4$		63~64	$\le 10^6$
29~30	$=10^5$	$\le 10^8$	65~66	$\le 10^4$	$\le 5\times 10^6$
31~32		$\le 10^9$	67~68	$\le 10^7$
33~34		$\le 10^{10}$	69~70	$\le 10$	$\le 10^8$
35~36		$\le 10^{18}$	71~72		$\le 10^9$

---

时空限制

• 时间限制：$\rm 200ms$
• 空间限制：$\rm 256MB$

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

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