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

内存限制:512 MiB 时间限制:3500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: KingSann

题目描述

给定 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}