算数天书与祖龙神殿国庆版

描述

算数天书推演万物，其中的每一卷都分为青龙篇、白虎篇、朱雀篇、玄武篇，满足如下推演规则：

• 对于算数天书每一卷的青龙篇，将其中的每一个 + 都分别替换为 *，就能得到这一卷的白虎篇。

• 对于算数天书每一卷的白虎篇，将其中的每一个 - 都分别替换为 /，就能得到这一卷的朱雀篇。

• 对于算数天书每一卷的朱雀篇，将其中的每一个 * 都分别替换为 +-，就能得到这一卷的玄武篇。

• 对于算数天书每一卷的玄武篇，将其中的每一个 / 都分别替换为 +，就能得到下一卷的青龙篇。

算数天书的第 $1$ 卷的青龙篇、白虎篇、朱雀篇、玄武篇分别是 +、*、*、+- 。

祖龙神殿充满机缘，其中的每一个传送阵都会通往一个祖龙秘境。对于任意正整数 $p$，想要灵力值为 $p$ 祖龙秘境中的祖龙传承，在这个秘境中向祖龙供奉的灵石的数量必须等于算数天书第 $p + 1$ 卷青龙篇前 $p - 1$ 个字符中中的 + 的数量。

注意，由于空间法术会受到天道的限制，对于任意正整数 $q$，祖龙神殿的第 $q$ 个传送阵通往的祖龙秘境的灵力值为 $r^{q} \bmod 2^{32}$ 。

输入

一个空格隔开的二个不大于 $10^{8}$ 的正整数 $r, n$ 。

输出

一个自然数，表示获得祖龙神殿的前 $n$ 个传送阵通往的祖龙秘境的全部祖龙传承所需的灵石的总数量。

输入样例 1

31 1

输出样例 1

19

输入样例 2

13 31

输出样例 2

31944950506

提示

当 $r = 31$ 时，祖龙神殿的第 $1$ 个传送阵通往灵力值为 $31$ 的祖龙秘境，想要获得灵力值为 $31$ 的祖龙秘境中的祖龙传承，就必须向祖龙供奉恰好 $19$ 块灵石。

想要获得灵力值为 $1$ 的祖龙秘境中的祖龙传承，就必须向祖龙供奉恰好 $0$ 块灵石。

想要获得灵力值为 $2$ 的祖龙秘境中的祖龙传承，就必须向祖龙供奉恰好 $1$ 块灵石。

想要获得灵力值为 $3$ 的祖龙秘境中的祖龙传承，就必须向祖龙供奉恰好 $1$ 块灵石。

想要获得灵力值为 $4$ 的祖龙秘境中的祖龙传承，就必须向祖龙供奉恰好 $2$ 块灵石。

想要获得灵力值为 $5$ 的祖龙秘境中的祖龙传承，就必须向祖龙供奉恰好 $3$ 块灵石。

建议

真的可以不使用浮点数哦！

想想为什么 $\displaystyle \left\lfloor \frac{3}{5} \times 31 \right\rfloor \neq 19 = \left\lfloor \frac{8}{13} \times 31 \right\rfloor = \left\lfloor \frac{21}{34} \times 31 \right\rfloor$ 吧！