[AdditionalFile6491.zip](file://AdditionalFile6491.zip?type=additional_file)

#6491. 「XXOI 2018」简单的最大公约数

标签: 传统 | 时间限制: 3500 ms | 内存限制: 512 MiB |

题目描述

给定 $n,m$，求：

$$\sum_{i_1=1}^{m}\sum_{i_2=1}^{m} \dots \sum_{i_n=1}^{m}\gcd(i_1,i_2,i_3, \dots i_n)$$

答案对 $2^{64}$ 取模。

输入格式

一行两个整数 $n,m$。

输出格式

一行一个整数表示答案。

样例

输入

10 10

输出

10009889889

数据范围与提示

$1 \le n, m \le 10^{11}$