#2068. 简单的最大公约数

简单的最大公约数

题目描述

给定 n,mn,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) $$

答案对 2642^{64} 取模。

输入格式

一行两个整数 n,mn,m

输出格式

一行一个整数表示答案。

10 10
10009889889

数据范围与提示

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