题目背景

热爱自然，热爱生命。

题目描述

求 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}$。

样例 1

输入

5 3

输出

33

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

样例 2

输入

10 5

输出

1108650

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

样例 3

输入

114 514

输出

17546076543575202049

样例 4

输入

1919 810

输出

13042575244352582345

样例 5

输入

114514 1919810

输出

167479551601740961

数据范围与提示

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

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

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

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