Problem:


Score : 500 points

Problem Statement

Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).

There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.

Since this sum can be enormous, print the value modulo (10^9+7).

Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

Constraints

2 \leq N \leq 10^5

1 \leq K \leq 10^5

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).

Sample Input 1

3 2

Sample Output 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

Thus, the answer is 9.

Sample Input 2

3 200

Sample Output 2

10813692

Sample Input 3

100000 100000

Sample Output 3

742202979

Be sure to print the sum modulo (10^9+7).



Sample input:
3 2


Sample output:
9

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)
    def __int__(self):
        return self.x

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __mod__(self, other):
        return (
            ModInt(
                other.x
            ) if isinstance(other, ModInt) else
            other
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
    
    def __iadd__(self,other):
        self.x += other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self

    def __isub__(self,other):
        self.x += ModInt(MOD - other.x) if isinstance(other, ModInt) else ModInt(MOD - other)
        return self

    def __imul__(self, other):
        self.x *= other.x if isinstance(other, ModInt) else other
        self.x %= MOD
        return self
    
    def factorical(self,n):
        tmp = ModInt(1)
        for i in range(n):
            tmp *= (i+1)
        return tmp
    
    #m:int MOD
    def modinv(self,a,m=MOD):
        b = m
        u = 1
        v = 0
        while(b):
            t = a//b
            a -= t * b
            a,b = b,a
            u -= t * v
            u,v = v,u
        return ModInt(u)

    def comb(self,n,r):
        n = int(n)
        r = int(r)
        if r > n or n < 0 or r < 0:
            return 0
        m = n+1
        nterms = min(r, n-r)
        numerator = ModInt(1)
        denominator = ModInt(1)
        for j in range(1, nterms + 1):
            numerator *= m - j
            denominator *= j
        return numerator * self.modinv(denominator.x)


if __name__ == "__main__":
    N, K = map(int,input().split())

    ans = ModInt(0)
    gcd_equal_i = [0]*(K+1) #gcd(A) == i なるAの作り方がgcd_equal_i[i]個

    for D in range(K, 0, -1):
        num_of_mul = K // D
        tmp = num_of_mul**3

        i = 2
        while D*i <= K:
            tmp -= gcd_equal_i[D*i]
            i += 1
        
        gcd_equal_i[D] = tmp


    for i in range(K+1):
        ans += i*gcd_equal_i[i]

    print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
INF=10**9+7
D=[0]*(k+1)
ans=0
for d in range(k,0,-1):
    x=(k//d)**n
    
    i=2 
    while d*i<=k:
        x-=D[d*i]
        i+=1
    D[d]=x
    ans+=(D[d]*d)%INF
print(ans)

Submission status: Wrong Answer

Solution code:
import math
t = input()
t = t.split()
n = int(t[0])
k = int(t[1])
nn = [2]*n
ans = k**n - (k-1)**n
while True:
  g = math.gcd(nn[0], nn[1])
  for i in range(2,n):
    g = math.gcd(g, nn[i])
  ans += g
  br = True
  for i in range(n):
    if nn[i] == k:
      nn[i] = 2
    else:
      nn[i] += 1
      br = False
      break
  if br:
    break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def read():
    N, K = list(map(int, input().strip().split()))
    return N, K


def prime_sieve(n):
    """
    n以下の素数を昇順に列挙する
    エラトステネスの篩 計算量O(Nlog(log(N)))
    """
    is_prime = [True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return [i for i in range(2, n+1) if is_prime[i]]


def prime_factorization(it):
    """
    数値の素因数分解をリストで返すイテレータ
    エラトステネスの篩を応用する 計算量O(A+Nlog(log(N)))
    """
    n = max(it)
    factor = [1 for i in range(n+1)]
    factor[0] = 0
    factor[1] = 1
    for i in range(2, n+1):
        if factor[i] == 1:
            for j in range(i, n+1, i):
                factor[j] = i
    for a in it:
        if a < 1:
            raise ValueError('Number must be larger than 0')
        if a == 1:
            yield list()
        else:
            prime_factors = list()
            while a != factor[a]:
                prime_factors.append(factor[a])
                a //= factor[a]
            prime_factors.append(factor[a])
            yield list(sorted(prime_factors))


def nCk_mod_preprocess(n, p=10**9+7):
    f = [0 for i in range(n+1)]  # n!
    invf = [0 for i in range(n+1)]  # (n!)^-1
    f[0] = 1
    f[1] = 1
    invf[0] = 1
    invf[1] = 1
    for i in range(2, n+1):
        f[i] = f[i-1] * i % p
    invf[n] = pow(f[n], p-2, p)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % p
    return f, invf


def nCk_mod(n, k, f, invf, p=10**9+7):
    assert n < len(f)
    if n < k or n < 0 or k < 0:
        return 0
    else:
        return (f[n] * invf[k] % p) * invf[n-k] % p


def solve(N, K, MOD=10**9+7):
    primes = prime_sieve(max(N, K))
    # 最大公約数がkの倍数になる数列の総数
    c_mul = [0 for i in range(K+1)]
    for k in range(2, K+1):
        c_mul[k] = pow(K//k, N, MOD)
    
    c_fac = [0 for i in range(K+1)]
    for k in range(2, K+1):
        c_fac[k] = c_mul[k]
        for j in primes:
            if j * k > K:
                break
            c_fac[k] -= c_mul[j*k]
            c_fac[k] %= MOD
    c_fac[1] = (pow(K, N, MOD) - sum(c_fac[2:])) % MOD
    ans = 0
    for k in range(1, K+1):
        ans += k * c_fac[k]
        ans %= MOD
    return ans

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
ans=0
lst=[0]*(k+1)
for i in range(k):
    tori=k//(k-i)
    lst[k-i]=pow(tori,n,mod)
    for j in range(1,tori):
        lst[k-i]-=lst[(k-i)*(j+1)]
# print(lst)
for i in range(k):
    ans+=lst[i+1]*(i+1)
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, K = read_values()
    C = [0] * (K + 1)

    for k in range(K, 0, -1):
        M = K // k
        C[k] = pow(M, N, mod)
        for r in range(2 * k, K, k):
            C[k] -= C[r]
            C[k] %= mod
    print(sum(i * k for i, k in enumerate(C)) % mod)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split()))
l = [0 for i in range(k)]
ans = 0
M = 10**9 + 7

def dev(n):
    dl = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            dl.append(i)
            if i != n // i:
                dl.append(n//i)
    dl.sort()
    return dl

for i in range(k, 0, -1):
    a=k//i
    b=a**n
    l[i-1] += b
    d=dev(i)
    for m in d:
        if m != i:
            l[m-1] -= l[i-1]
    print(i, l)

for i in range(1, k+1):
    ans+=i*l[i-1]

print(ans%M)

Submission status: Wrong Answer

Solution code:
def is_prime(num):
    if num == 1:
        raise ValueError("error!")
    d = 2
    while d * d <= num:
        if num % d == 0:
            return False
        d += 1
    return True
    
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

n_power_table = [-1] * (k+1)
for i in range(k):
    n_power_table[i] = pow(i, n, mod)

# 素数リストを作っておく
prime_list = []
for i in range(2, k+1):
    if is_prime(i):
        prime_list.append(i)

prime_2_list = []
prime_3_list = []
prime_4_list = []
prime_5_list = []

ll = len(prime_list)
for i, p1 in enumerate(prime_list):
    for j in range(i+1, ll):
        p2 = prime_list[j]
        if p1*p2 > k:
            break
        prime_2_list.append(p1*p2)
        for v in range(j+1, ll):
            p3 = prime_list[v]
            if p1*p2*p3 > k:
                break
            prime_3_list.append(p1*p2*p3)
            # print(p1, p2, p3)
            for w in range(v+1, ll):#enumerate(prime_list[v+1:]):
                p4 = prime_list[w]
                if p1*p2*p3*p4 > k:
                    break
                prime_4_list.append(p1*p2*p3*p4)
                for x in range(w+1, ll):#, p5 in enumerate(prime_list[w+1:]):
                    p5 = prime_list[x]
                    if p1*p2*p3*p4*p5 > k:
                        break
                    prime_5_list.append(p1*p2*p3*p4*p5)

prime_2_list.sort()
prime_3_list.sort()
prime_4_list.sort()
prime_5_list.sort()

# prime_3_list = []
# for i, p1 in enumerate(prime_list):
#     for j, p1_ in enumerate(prime_2_list):
#         if p1*p1_ > k:
#             break
#         prime_3_list.append(p1*p1_)

# list(set(prime_3_list)).sort()

# print(prime_3_list)

ans = 0
temp = 0

for g in range(1, k+1):
    # kosuu は、gcd = gとなる組み合わせの個数
    p = k // g
    
    kosuu = pow(p, n, mod)

    for prime in prime_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]
    
    for prime in prime_2_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]
    
    for prime in prime_3_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_4_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    for prime in prime_5_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    kosuu %= mod
    ans += g * kosuu
    # print(g, kosuu)
    temp += kosuu

print(ans% mod)
# print(temp)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
s = 10**9 + 7
t = K // 2

T = [1]*K

for i in range(t):
    i = t - i -1
    T[i] = (K // (i+1))**N % s
    j = 2
    while (i+1)*j < K+1:
        T[i] = (T[i]- T[(i+1)*j-1]) % s
        j += 1

ans = 0
for i in range(K):
    ans += (i+1)*T[i] % s

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())

def func(n):
    r = n
    for i in range(2, n + 1):
        if i ** 2 > n:
            break

        if n % i == 0:
            r -= r // i
            while n % i == 0:
                n //= i
        
    if n > 1:
        r -= r // n
    return r


MOD = 10 ** 9 + 7
ans = 0
for i in range(1, K + 1):
    ans += func(i) * pow(K // i, N, MOD)
print(ans)

Submission status: Wrong Answer

Solution code:
# E.py
mod = 10 ** 9 + 7
n, k = map(int,input().split())

import math
M = [sum([math.gcd(i,j) for i in range(1,j)]) for j in range(1,k+1)]

x = (1 << n) % mod
x -= 2
res = 1
for i in range(1, k):
    res += (M[i] * x)%mod + (i+1)
    res %= mod
print(res)

Submission status: Wrong Answer

Solution code:
def is_prime(num):
    if num == 1:
        raise ValueError("error!")
    d = 2
    while d * d <= num:
        if num % d == 0:
            return False
        d += 1
    return True
    
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

n_power_table = [-1] * (k+1)
for i in range(k):
    n_power_table[i] = pow(i, n, mod)

# 素数リストを作っておく
prime_list = []
for i in range(2, k+1):
    if is_prime(i):
        prime_list.append(i)

prime_2_list = []
prime_3_list = []
prime_4_list = []
prime_5_list = []

ll = len(prime_list)
for i, p1 in enumerate(prime_list):
    for j in range(i+1, ll):
        p2 = prime_list[j]
        if p1*p2 > k:
            break
        prime_2_list.append(p1*p2)
        for v in range(j+1, ll):
            p3 = prime_list[v]
            if p1*p2*p3 > k:
                break
            prime_3_list.append(p1*p2*p3)
            # print(p1, p2, p3)
            for w in range(v+1, ll):#enumerate(prime_list[v+1:]):
                p4 = prime_list[w]
                if p1*p2*p3*p4 > k:
                    break
                prime_4_list.append(p1*p2*p3*p4)
                for x in range(w+1, ll):#, p5 in enumerate(prime_list[w+1:]):
                    p5 = prime_list[x]
                    if p1*p2*p3*p4*p5 > k:
                        break
                    prime_5_list.append(p1*p2*p3*p4*p5)

prime_2_list.sort()
prime_3_list.sort()
prime_4_list.sort()
prime_5_list.sort()


# prime_3_list = []
# for i, p1 in enumerate(prime_list):
#     for j, p1_ in enumerate(prime_2_list):
#         if p1*p1_ > k:
#             break
#         prime_3_list.append(p1*p1_)

# list(set(prime_3_list)).sort()

# print(prime_3_list)

ans = 0
temp = 0

for g in range(1, k+1):
    # kosuu は、gcd = gとなる組み合わせの個数
    p = k // g
    
    kosuu = pow(p, n, mod)

    for prime in prime_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]
    
    for prime in prime_2_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]
    
    for prime in prime_3_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_4_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    for prime in prime_5_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    kosuu %= mod
    ans += g * kosuu
    # print(g, kosuu)
    temp += kosuu

print(ans% mod)
# print(temp)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
  
from functools import reduce
# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
ans = ModInt(0)
for i in range(1,3):
  x = i * ((ModInt(k//i))**n - (ModInt(k//i-1))**n)
  ans += x
import numpy as np
primes = np.array([2])
for i in range(3,k+1,2):
  if all (i % primes != 0):
    x = i * ((ModInt(k//i))**n - (ModInt(k//i-1))**n)
    ans += x
    primes = np.append(i, primes)
if k > 1:
  print(ans)
else:
  i = 1
  x = i * ((ModInt(k//i))**n - (ModInt(k//i-1))**n)
  print(x)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
mod = 10 ** 9 + 7

s = 0
tmp = 1
for _ in range(N):
    tmp *= K
    tmp %= mod
s = tmp
for i in range(2, K+1):
    baisuu = K % i
    tmp = 1
    for _ in range(N):
        tmp *= baisuu
        tmp %= mod
    s += tmp * (i - 1)

print(s)

Submission status: Wrong Answer

Solution code:
import math
N, K = map(int,input().split())
a = 0
for i in range(1, K):
    p = (K-i+1)**N - (K-i)**N
    q = (math.floor(K/i))**N - ((math.floor(K/i))-1)**N
    a += (i-1)*q + p
print(a%1000000007)

Submission status: Wrong Answer

Solution code:
import math

N,K = map(int, input().split())

def func(num,gcd):
    g = math.gcd(num,gcd)
    sum = g
    for i in range(num+1,K+1):
        sum += (math.gcd(i,g)) * (K**N - 2)
    return sum

sum = 0

for i in range(1,K+1):
    sum += func(i,i)

print(sum%(10**9+7))

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
             
    return divisors

n, k = map(int, input().split())
mod = 1000000007
l = [1 for i in range(k+1)]
for i in range(k):
  for j in range(len(make_divisors(k-i))):
    l[make_divisors(k-i)[j]] += n*l[k-i]
ans = 0
for i in range(k+1):
  ans += l[i]*i
  ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,k=map(int,input().split())
mod=10**9+7
ans=pow(k,n,mod)
for i in range(2,k+1):
  m=pow(k//i-k//(i*2),n,mod)
  ans=(ans+m)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
cnt = [0]*(k+7)
ans = 0
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

for i in range(1,k+1):
    for x in make_divisors(i):
        
        cnt[x]+=1
        
for x in range(1,k+1):
    if x == 1:
        ans += pow(cnt[x],n,mod)-sum(cnt[1:])
        
        continue
        
    ans += x*pow(cnt[x],n,mod)
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = [int(i) for i in input().split()]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

mod = 10**9 + 7
total = k**n % mod

for i in range(2, k+1):
    divisors = make_divisors(i)
    t = sum(divisors[:-1])
    a = k // i
    total += a**n * (i-t)

print(total)

Submission status: Wrong Answer

Solution code:
def f(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr 




n,k=map(int,input().split())
mod=10**9+7
ans=pow(k,n,mod)
for i in range(2,k+1):
  a=0
  C=f(i)
  for j in range(len(C)):
    a=a+i//C[j][0]
  ans=(ans+pow((k//i),n,mod)*(i-a))%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
S = K
mod = 10 ** 9 + 7
ans = 0
import numpy as np
g = []
for i in range(K + 1):
    g.append(np.power(i, N) % mod)

for i in range(1, S + 1):
    c = S // i
    a = g[K] - g[K - 1]
    ans += i * (g[c] - g[c - 1])
    ans += a - (g[c] - g[c - 1])
    K -= 1

print(ans % mod)

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
mod = 10**9 + 7


def pow_mod(x, n, mod):
    if n > 1:
        return pow_mod(pow(x,2) % mod, n//2, mod) * pow(x, n%2) % mod
    else:
        return x


pow_n = [-1] * (k+1)
for i in range(1,k+1):
    if pow_n[k//i] == -1:
        pow_n[k//i] = pow_mod(k//i, n, mod)

ans = 0
c = [0] * (k+1)
for i in range(k, 0, -1):
    count = pow_n[k//i]
    for j in range(2, k//i+1):
        if j > k//i:
            break
        count -= c[i]
        count %= mod
    c[i] = count
    ans += count * i
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
def is_prime(num):
    if num == 1:
        raise ValueError("error!")
    d = 2
    while d * d <= num:
        if num % d == 0:
            return False
        d += 1
    return True
    
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

n_power_table = [-1] * (k+1)
for i in range(k):
    n_power_table[i] = pow(i, n, mod)

# 素数リストを作っておく
prime_list = []
for i in range(2, k+1):
    if is_prime(i):
        prime_list.append(i)

prime_2_list = []
prime_3_list = []
prime_4_list = []
prime_5_list = []

ll = len(prime_list)
for i, p1 in enumerate(prime_list):
    for j in range(i+1, ll):
        p2 = prime_list[j]
        if p1*p2 > k:
            break
        prime_2_list.append(p1*p2)
        for v in range(j+1, ll):
            p3 = prime_list[v]
            if p1*p2*p3 > k:
                break
            prime_3_list.append(p1*p2*p3)
            # print(p1, p2, p3)
            for w in range(v+1, ll):#enumerate(prime_list[v+1:]):
                p4 = prime_list[w]
                if p1*p2*p3*p4 > k:
                    break
                prime_4_list.append(p1*p2*p3*p4)
                for x in range(w+1, ll):#, p5 in enumerate(prime_list[w+1:]):
                    p5 = prime_list[x]
                    if p1*p2*p3*p4*p5 > k:
                        break
                    prime_5_list.append(p1*p2*p3*p4*p5)

prime_2_list.sort()
prime_3_list.sort()
prime_4_list.sort()
prime_5_list.sort()


# prime_3_list = []
# for i, p1 in enumerate(prime_list):
#     for j, p1_ in enumerate(prime_2_list):
#         if p1*p1_ > k:
#             break
#         prime_3_list.append(p1*p1_)

# list(set(prime_3_list)).sort()

# print(prime_3_list)

ans = 0
temp = 0

for g in range(1, k+1):
    # kosuu は、gcd = gとなる組み合わせの個数
    p = k // g
    
    kosuu = pow(p, n, mod)

    for prime in prime_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]
    
    for prime in prime_2_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]
    
    for prime in prime_3_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_4_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    for prime in prime_5_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    kosuu %= mod
    ans += g * kosuu
    # print(g, kosuu)
    temp += kosuu

print(ans)
# print(temp)

Submission status: Wrong Answer

Solution code:
N,K=map(int, input().split())
import math
cnt=(K**N)%(10**9+7)

print(cnt)
for i in range(2,K+1):
  a=K//i
  cnt+=((a**N-2)*(i-1))%(10**9+7)
print(cnt)

Submission status: Wrong Answer

Solution code:
import math
N,K = map(int,input().split())
mod = 10**9+7

D = []
for i in range(1,math.floor(math.sqrt(K))+1):
  if K % i == 0:
    D.append(i)
    if i != K//i:
      D.append(K//i)
      
def g(n):
  P = []
  q = n
  for i in range(2,math.floor(math.sqrt(n))+1):
    if q % i == 0:
      P.append(i)
      while q % i == 0:
        q = q//i
  b = n
  for i in P:
    b = int(b*(i-1)//i)
  return b
      
    

def f(n,d):
  if n == 1:
    return 1
  else:
    a = 0
    for i in D:
      if i // d != 0:
        continue
      elif i == d:
        a += f(n-1,d)*K//d % mod
      else:
        a += f(n-1,i)*g(K//i) % mod
    return a
    
ans = 0
for d in D:
  ans += f(N,d)*d % mod
  
print(ans)

Submission status: Wrong Answer

Solution code:
n,k = map(int, input().split())
cnt = 0
for i in range(k+1):
    cnt += (i+1)*((k//(i+1))**(k-i))
print (cnt//(10**9+7))

Submission status: Wrong Answer

Solution code:
import math

N,K=map(int,input().split())
P=10**9+7

L=[0]*N
for i in range(N):
    L[i]=pow(K//(i+1),N-1,P)

def culc(x):
    f=K//i
    r=K-f
    if r==1:
        return (f*(N-1))%P
    else:
        y=pow(r,N-1)-1
        return ((f*y)//(r-1))%P

for j in range(1,N):
    L[0]+=culc(j+1)

ans=0
for k in range(N):
    ans+=((k+1)*L[k])%P

print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int,input().split())
s = 10**9 + 7
t = K // 2

T = [1]*K

for i in range(t):
    i = t - i
    T[i] = (K // i)**N % s
    j = 2
    while t*j < K:
        T[i] = (T[i]- T[i*j]) % s
        j += 1

ans = 0
for i in range(K):
    ans += (i+1)*T[i] % s

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    n, k = map(int, input().split())
    ans = k ** (n - 1)

    for i in range(2, k + 1):
        a = k // i
        b = (k - i) - a + 1
        c = i * a ** n + 1 * (b + 1) ** n
        ans += c
        ans = ans % (10 ** 9 + 7)
        # print('i:{} a:{} b:{} c:{}'.format(i, a, b, c))

    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# E.py
mod = 10 ** 9 + 7
n, k = map(int,input().split())

import math
M = [sum([math.gcd(i,j) for i in range(1,j)]) for j in range(1,k+1)]

x = (2 << n-1) % mod
x -= 2
res = 1
for i in range(1, k):
    res += (M[i] * x)%mod
    res %= mod
print(res)

Submission status: Wrong Answer

Solution code:
if __name__ == '__main__':
    MOD = 10 ** 9 + 7
    N, K = map(int, input().split())

    ans = 0
    for i in range(1, K + 1):
        ans += ((K // i) ** N) % MOD

    print(ans % MOD)

Submission status: Wrong Answer

Solution code:
def is_prime(num):
    if num == 1:
        raise ValueError("error!")
    d = 2
    while d * d <= num:
        if num % d == 0:
            return False
        d += 1
    return True
    
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

n_power_table = [-1] * (k+1)
for i in range(k):
    n_power_table[i] = pow(i, n, mod)

# 素数リストを作っておく
prime_list = []
for i in range(2, k+1):
    if is_prime(i):
        prime_list.append(i)

prime_2_list = []
prime_3_list = []
prime_4_list = []
prime_5_list = []

ll = len(prime_list)
for i, p1 in enumerate(prime_list):
    for j in range(i+1, ll):
        p2 = prime_list[j]
        if p1*p2 > k:
            break
        prime_2_list.append(p1*p2)
        for v in range(j+1, ll):
            p3 = prime_list[v]
            if p1*p2*p3 > k:
                break
            prime_3_list.append(p1*p2*p3)
            # print(p1, p2, p3)
            for w in range(v+1, ll):#enumerate(prime_list[v+1:]):
                p4 = prime_list[w]
                if p1*p2*p3*p4 > k:
                    break
                prime_4_list.append(p1*p2*p3*p4)
                for x in range(w+1, ll):#, p5 in enumerate(prime_list[w+1:]):
                    p5 = prime_list[x]
                    if p1*p2*p3*p4*p5 > k:
                        break
                    prime_5_list.append(p1*p2*p3*p4*p5)

prime_2_list.sort()
prime_3_list.sort()
prime_4_list.sort()
prime_5_list.sort()


# prime_3_list = []
# for i, p1 in enumerate(prime_list):
#     for j, p1_ in enumerate(prime_2_list):
#         if p1*p1_ > k:
#             break
#         prime_3_list.append(p1*p1_)

# list(set(prime_3_list)).sort()

# print(prime_3_list)

ans = 0
temp = 0

for g in range(1, k+1):
    # kosuu は、gcd = gとなる組み合わせの個数
    p = k // g
    
    kosuu = p ** n

    for prime in prime_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]
    
    for prime in prime_2_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]
    
    for prime in prime_3_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_4_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    for prime in prime_5_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    kosuu %= mod
    ans += g * kosuu
    # print(g, kosuu)
    temp += kosuu

print(ans)
# print(temp)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
mod = 10**9+7
ans = 0
for i in range(2, k+1):
    tmp = pow(k//i, n, mod) - pow(k//i-1, n, mod)
    tmp %= mod
    ans += tmp*(i-1)
ans += pow(k, n, mod)
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import math

N,K = map(int, input().split())

def func(num,gcd):
    g = math.gcd(num,gcd)
    sum = g
    for i in range(num+1,K+1):
        sum += (math.gcd(i,g)) * (K**N - 2)
        sum = sum%(10**9+7)
    return sum

sum = 0

for i in range(1,K+1):
    sum += func(i,i)
    sum = sum%(10**9+7)
print(sum)

Submission status: Wrong Answer

Solution code:
import math
m=10**9+7
n,k=map(int,input().split())
b=[[0]*(k+1) for i in range(k+1)]
for i in range(1,k+1):
  for j in range(1,k+1):
    b[i][math.gcd(i,j)]+=1

a=[1]*(k+1)
a[0]=0
def gc(a,b):
  c=[0]*(k+1)
  for i in range(1,k+1):
    for j in range(1,i+1):
      c[j]+=a[i]*b[i][j]
  for i in range(1,k+1):
    c[i]%=m
  return c
for i in range(n-1):
  a=gc(a,b)
ans=0
for i in range(1,k+1):
  ans+=(i*a[i])%m
print(ans)