Sum of gcd of Tuples (Hard)

题号：NC229748
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给 $\ n,k$ ，求：

$\sum_{a_1=1}^k \sum_{a_2=1}^k...\sum_{a_n=1}^k {gcd(a_1,a_2...a_n)}\ mod\ 10^9+7$

第一行包含两个整数。

输出一行表示答案。

示例1

复制

3 2

复制

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

示例2

复制

3 200

复制

10813692

示例3

复制

100000 100000

复制

742202979

原题链接：https://atcoder.jp/contests/abc162/tasks/abc162_e