← 返回题目列表

AtCoder · abc162_e

E. 元组的 gcd 总和(硬)

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

考虑序列 \{A_1,...,A_N\} 长度 N 由之间的整数组成 1 和 K (含)。

有 K^N 这样的序列。求总和 \gcd(A_1, ..., A_N) 超过所有这些。

由于这个总和可能很大,所以打印该值模 (10^9+7).

这里 \gcd(A_1, ..., A_N) 表示最大公约数 A_1, ..., A_N.

约束

  • 2 \leq N \leq 10^5
  • 1 \leq K \leq 10^5
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K

输出

打印总和 \gcd(A_1, ..., A_N) 总体而言 K^N 序列,模 (10^9+7).


示例输入 1

3 2

示例输出 1

9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2) +\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2) =1+1+1+1+1+1+1+2=9

因此,答案是 9.


示例输入 2

3 200

示例输出 2

10813692

示例输入 3

100000 100000

示例输出 3

742202979

请务必打印模数之和 (10^9+7).