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: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#define FPEN freopen("in.txt", "r", stdin);
#define TEST(...)                                                              \
    { printf("! "), printf(__VA_ARGS__); }
#else
#define TEST(...)
#define FPEN
#endif
const int maxn = 200009;
typedef long long i64;
typedef pair<i64, i64> pi64;
typedef pair<int, int> pi;
const i64 MOD = 1e9 + 7;
class {
  public:
    i64 cnt[maxn], pwN[maxn], n, k;
    i64 pw(i64 a, i64 b) {
        i64 res = 1;
        while (b) {
            if (b & 1)
                res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    void solve() {
        cin >> n >> k;
        for (int i = 1; i <= k; ++i)
            pwN[i] = pw(i, n);
        for (int i = 1; i <= k; ++i)
            cnt[i] = i;
        i64 ans = 0;
        for (int i = 1; i <= k; ++i) {
            (ans += pwN[k / i] * cnt[i] % MOD) %= MOD;
            i64 count = cnt[i];
            for (int j = i; j <= k; j += i)
                cnt[j] -= count;
        }
        cout << ans << '\n';
    }
} NSPACE;
int main() {
    FPEN;
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    NSPACE.solve();
}

Submission status: Runtime Error

Solution code:
N,K=list(map(int,input().split()))
l=[0]*(K+1)
ans=0
mod=10**9+7

for x in range(K,0,-1):
    l[x]=pow((K//x),N,mod)
    for y in range(2*x,K+1,x):
        l[x]-=l[y]
        l[x]=pow(l[i],1,mod)
    ans+=l[x]*x
    ans=pow(ans,1,mod)
print(ans)

Submission status: Runtime Error

Solution code:
import math
import numpy as np
n,k=map(int,input().split())
ans=0
sheet=np.array([1]*k)
mat=np.zeros((k,k),dtype=float)
for i in range(1,k+1):
    for j in range(1,k+1):
        p=math.gcd(i,j)
        mat[i-1][p-1]+=1.0
eig=np.linalg.eig(mat)
diag=np.diag(eig[0])
s=sheet.dot(eig[1].dot((diag)**(n-1)).dot(np.linalg.inv(eig[1])))
for i in range(k):
    ans+=(i+1)*s[i]%(10**9+7)
print(int(ans)%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
import numpy as np
n,k=map(int,input().split())
ans=0
sheet=np.array([1]*k)
mat=np.zeros((k,k),dtype=float)
for i in range(1,k+1):
    for j in range(1,k+1):
        p=math.gcd(i,j)
        mat[i-1][p-1]+=1.0
s=sheet.dot(np.linalg.matrix_power(mat,n-1))
for i in range(k):
    ans+=(i+1)*s[i]%(10**9+7)
print(int(ans)%(10**9+7))

Submission status: Runtime Error

Solution code:
import math
n,k=map(int,input().split())
mod=pow(10,9)+7
ans=0
l=[0]*(k+1)

for i in reversed(range(1,k+1)):
    l[i]=pow(math.floor(k/i),n)%mod
    a=2*i
    while a<=k:
        l[i]-=l[a]
        a+=i
    ans+=l[i]*i%mod

for i in range(n+1):
    print(i,l[i])

print(ans)

Submission status: Runtime Error

Solution code:
mod=10**9+7
N,K=map(int,input().split())
gcd=[0]*(K+1)
ans=0
multipleNumber=0
for i in reversed(range(1,K+1)):
    multipleNumber=K//i
    totalNumber=multipleNumber**N%mod
    minus=range(2*i,K+1,i)
    for j in minus:
        totalNumber-=gcd[j]
        totalNumber%=mod
    gcd[i]=totalNumber
    ans+=i*gcd[i]
print(ans%a)

Submission status: Runtime Error

Solution code:
import math
a=10**9+7
N,K=map(int,input().split())
gcd=[0]*(K+1)
ans=0
multipleNumber
for i in reversed(range(1,K+1)):
    multipleNumber=math.floor(K/i)
    totalNumber=multipleNumber**N
    if 2*i<=K:
        minus=range(2*i,K+1,i)
        for j in minus:
            totalNumber-=gcd[j]
    gcd[i]=totalNumber
for i in range(1,len(gcd)):
    ans+=i*gcd[i]
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int, input().split()))
inf=10**10

if N%2==0:
    dp=[[[0]*2 for __ in range(2)] for _ in range(N)]
    dp[0][0][0]=A[0]
    dp[0][0][1]=-inf
    dp[0][1][0]=-inf
    dp[0][1][1]=0
    dp[1][0][0]=-inf
    dp[1][0][1]=-inf
    dp[1][1][0]=A[1]
    dp[1][1][1]=-inf
    for i in range(2, N):
        dp[i][0][0]=dp[i-2][0][0]+A[i]
        dp[i][0][1]=-inf
        dp[i][1][0]=max(dp[i-1][1][1], dp[i-2][1][0])+A[i]
        dp[i][1][1]=dp[i-2][0][0]
    print(max(dp[-1][1]))
else:
    dp=[[[0]*2 for __ in range(3)] for _ in range(N)]
    dp[0][0][0]=A[0]
    dp[0][0][1]=-inf
    dp[0][1][0]=-inf
    dp[0][1][1]=0
    dp[0][2][0]=-inf
    dp[0][2][1]=-inf
    dp[1][0][0]=-inf
    dp[1][0][1]=-inf
    dp[1][1][0]=A[1]
    dp[1][1][1]=-inf
    dp[1][2][0]=-inf
    dp[1][2][1]=0
    for i in range(2, N):
        dp[i][0][0]=dp[i-2][0][0]+A[i]
        dp[i][0][1]=-inf
        dp[i][1][0]=max(dp[i-1][1][1], dp[i-2][1][0])+A[i]
        dp[i][1][1]=dp[i-2][0][0]
        dp[i][2][0]=max(dp[i-1][2][1], dp[i-2][2][0])+A[i]
        dp[i][2][1]=max(dp[i-1][1][1], dp[i-2][1][0])
    print(max(dp[-1][2]))

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x
MOD = int(10e9 + 7)

n, k = map(int, input().split())
mem = {}
def dp(at, cur):
    if at == n:
        return cur
    if (at,cur) in mem:
        return mem[(at,cur)]
    sm = 0
    for i in range(1, k+1):
        sm += dp(at+1,gcd(cur, i))
    mem[(at,cur)] = sm % MOD
    return sm % MOD

sm = 0
for i in range(1, k+1):
    sm += dp(1, i)
print(sm % MOD)

Submission status: Runtime Error

Solution code:
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [0] * (k + 1)

for i in range(0, k + 1):
    d[i] = pow(k // i, n, MOD)

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
# YouTube解説
MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k, n, MOD) for i in range(1, k+1)]

for i in range(k, 0, -1):  # 大きいほうから
    for j in range(i * 2, k + 1, i):  # iの倍数
        # d[6] = d'[6] - d[12] - d[18] ...
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
l=[0]*(k+1)
for i in range(k):
    num=(k-i)
    if k//num==1:
        l[num]=1
    else:
        ret=(k//num,n,10**9+7)
        for j in range(2,k//num+1):
            ret-=l[num*j]
            ret%=(10**9+7)
        l[num]=(ret)%(10**9+7)
ans=0
for i in range(k+1):
    ans+=(l[i]*i)%(10**9+7)
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
mod = 10e9 + 7
ans = 0
cnt_arr = [0]*(K+1)
for i in range(K,0,-1):
  cnt = (K//i)**N%mod
  j = 2
  while i*j<=K:
    cnt -= cnt_arr[i*j]
    j+=1
  cnt_arr[i]=cnt
  ans += i*cnt

print(int(ans%mod))

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
mod = 10**9 + 7
s = [0 for i in range(k+1)]
ret = 0

for i in range(k, 0, -1):
    p = int(k/i)
    f = pow(p, n, mod)
    for j in range(2, k+1):
        if i*j <= k:
            c -= s[i*j]
        else:
            break
    
    s[i] = c%mod

    ret = (ret + (c%mod)*i)%mod

print(ret)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
mod = 10**9 + 7
s = [0 for i in range(k+1)]
ret = 0

for i in range(k, 0, -1):
    p = int(k/i)
    f = pow(p, n, mod)
    for j in range(2, k+1):
        if i*j <= k+1:
            c -= s[i*j]
        else:
            break
    
    s[i] = c%mod

    ret = (ret + (c%mod)*i)%mod

print(ret)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7

n, k = map(int, input().split())
otv = 0
D = [0] * (n + 1)
for i in range(1, n + 1):
    D[i] = pow(k // i, n, mod)

for i in range(k // 2, 0, -1):
    for j in range(i * 2, k + 1, i):
        D[i] -= D[j]

for i in range(1, n + 1):
    otv = (otv + D[i] * i) % mod

print(otv)

Submission status: Runtime Error

Solution code:
import math
from collections import Counter

K = int(input())

memo = {frozenset((i, j)): math.gcd(i, j) 
        for i in range(1, K+1) for j in range(i, K+1)}

counter = Counter([memo[frozenset((i, j))] 
                   for i in range(1, K+1) for j in range(1, K+1)])

total = 0
for i in range(1, K+1):
  for value, count in counter.items():
    total += memo[frozenset((i, value))] * count
    
print(total%(10**9 + 7)

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
dp = [0]*100010
MOD = 1000000007
for g in reversed(range(k)):
    reg=0
    if(floor(k//g) >= 2):
        for i in range(2,floor(k//g)+1)
            reg += dp[i*g] %MOD
        
    dp[g] = floor(k//g)**n%MOD - reg % MOD
    
sum = 0
for i in range(1,k+1):
    sum += i * dp[i]%MOD
print("{}".format(sum))

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
gcd = [0 for i in range(k+1)]
s = []
for i in range(k,0,-1):
    gcd[i] = (k//i)**n
    j=2
    while j*i <= k:
        gcd[i] -= gcd[i*j]
        j += 1
    s.append(i*gcd[i])
print(int(sum(s)%(1e9+7)))

Submission status: Runtime Error

Solution code:
n, k = map(int,input().split())
gcd = [0 for i in range(k+1)]
s = []
for i in range(k,0,-1):
    gcd[i] = ((k//i)**n)
    j=2
    while j*i <= k:
        gcd[i] -= gcd[i*j]
        j += 1
    s.append(i*gcd[i])
print(int(sum(s)%(1e9+7)))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from sys import stdin
import itertools

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
def main():
  N = int(stdin.readline())
  K = int(stdin.readline())
  
  ans = 0
  
  for xs in itertools.combinations_with_replacement(range(1, K+1), N):
    
    if len(set(xs)) == 1:
      ans += gcd(*xs)
    elif len(set(xs)) == 2:
      ans += 3*gcd(*xs)
    else:
      ans += 6*gcd(*xs)
      
  print(ans % (10**9 + 7))

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
from sys import stdin
import itertools

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
def main():
  N = int(stdin.readline())
  K = int(stdin.readline())
  
  ans = 0
  
  for xs in itertools.combinations_with_replacement(range(1, K+1), N):
    print(xs)
    print(gcd(*xs))
    if len(set(xs)) == 1:
      ans += gcd(*xs)
    elif len(set(xs)) == 2:
      ans += 3*gcd(*xs)
    else:
      ans += 6*gcd(*xs)
      
  print(ans % (10**9 + 7))

if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
import math
import itertools
from functools import reduce


n = int(input())
k = int(input())

ans = 0
for x in itertools.product(list(range(1, k+1)), repeat=n):
    ans += reduce(math.gcd, x)
ans %= (10**9+7)                                             
print(ans)

Submission status: Runtime Error

Solution code:
/*
         ██╗ ██████╗ ██╗███╗   ██╗    ██╗   ██╗███████╗
         ██║██╔═══██╗██║████╗  ██║    ██║   ██║██╔════╝
         ██║██║   ██║██║██╔██╗ ██║    ██║   ██║███████╗
    ██   ██║██║   ██║██║██║╚██╗██║    ██║   ██║╚════██║
    ╚█████╔╝╚██████╔╝██║██║ ╚████║    ╚██████╔╝███████║
     ╚════╝  ╚═════╝ ╚═╝╚═╝  ╚═══╝     ╚═════╝ ╚══════╝
*/
//password:+BdCHpO8dQvpo5fnV3/u
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
const int mod=1e9+7;
ll v[maxn],phi[maxn],prime[maxn];
ll m=0;
inline void euler(int n=400000){
memset(v,0,sizeof(v));
  m=0;
    for(int i=2;i<=n;i++){
        if(!v[i]) v[i]=i,prime[++m]=i,phi[i]=i-1;
        for(int j=1;j<=m;j++) {
            if(prime[j]>v[i]||prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
            phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        }
    }
}
ll n,k;
inline ll mpow(ll a,ll b){
    ll ans=1%mod;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main() {
    phi[1]=1;
    euler();
    scanf("%lld %lld",&n,&k);
    ll ans=0,res=0;
    for(int i=1;i<=k;i++){
        res=mpow(k/i,n);
        // cout<<res<<" "<<phi[i]<<"\n";
        res=(res*phi[i])%mod;
        ans=(ans+res)%mod;
    }
    printf("%lld",ans);
    return 0;
}

Submission status: Runtime Error

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


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

Submission status: Runtime Error

Solution code:
n = int(input())
arr = list(map(int,input().split()))



if n % 2 == 0:
    tp = sum(arr[::2])
    print(max(sum(arr)-tp,tp))
elif n == 3:
    print(arr[0]+arr[2])
else:
    hoge = -(10**12)
    buf = [[hoge for i in range(3)] for j in range(n)]
    buf[0][0] = arr[0]
    buf[1][1] = arr[1]
    buf[2][2] = arr[2]
    buf[2][0] = arr[0]+arr[2]

    for i in range(3,n):
        buf[i][0] = buf[i-2][0] + arr[i]
        buf[i][1] = max(buf[i-3][0] + arr[i],buf[i-2][1]+arr[i])
        if i >= 4:
            buf[i][2] = max([buf[i-3][1] + arr[i],buf[i-4][0] + arr[i],buf[i-2][2]+arr[i]])
        else:
            buf[i][2] = max([buf[i-3][1] + arr[i],buf[i-2][2]+arr[i]])


    print(max(buf[-1][2],buf[-2][1],buf[-3][0]))

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define endl "\n"
#define deb(x) cerr << #x << ":" << x << "\n"

ll n,k,mod=1e9+7,ans=0;

ll fastMod(ll a,ll b){
    ll res=1;
    while(b>0){
        if(b&1)res=(res*a)%mod;
        b/=2;
        a=(a*a)%mod;
    }
    return res;
}

void solve(){    
    cin>>n>>k;
    vector<ll> v(k+1);
    for(int i=k;i>0;i--){
        v[i]=fastMod(k/i,n);
        for(int j=2*i;j<=k;j+=i){
            v[i]=(v[i]-v[j]+mod)%mod;
        }
    }
    for(int i=1;i<=k;i++){
        ll val=(v[i]*i)%mod;
        ans=(ans+val)%mod;
    }
    cout<<ans%mod;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
import math

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

L=[0]*K
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,K):
    L[0]+=culc(j+1)

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

print(ans)

Submission status: Runtime Error

Solution code:
import math
import numpy as np

n, k = map(int, input().split())

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = (math.floor(k/t)**n)%moddo
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

print(ans)

Submission status: Runtime Error

Solution code:
n = input()
k = int(input())
dp = [[[0 for i in range(len(n)+1)] for i in range(2)] for i in range(len(n)+1)]
dp[0][0][0] = 1
for a in range(len(n)):
  for b in range(2):
    for c in range(len(n)):
      for i in range(10):
        if b ==1:
          if i != 0:
            dp[a+1][1][c+1] += dp[a][1][c]
          else:
            dp[a+1][1][c] += dp[a][1][c]
        else:
          if int(n[a]) > i and i ==0:
            dp[a+1][1][c] += dp[a][0][c]
          if int(n[a]) > i and i != 0:
            dp[a+1][1][c+1] += dp[a][0][c]
          if int(n[a]) == i and i ==0:
            dp[a+1][0][c] += dp[a][0][c]
          if int(n[a]) == i and i !=0:
            dp[a+1][0][c+1] += dp[a][0][c]
if len(n) == 1:
	print(int(n))  
else:
  print(dp[-1][0][k] + dp[-1][1][k])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
dp = [[0, 0, 0] for _ in range(N+3)]

for i, x in enumerate(a, start=3):
    dp[i][2] = max(dp[i-2][0], x+dp[i-2][2], x+dp[i-3][1])
    dp[i][1] = max(x+dp[i-2][1], x+dp[i-3][0])
    dp[i][0] = x + dp[i-2][0]

if N & 1 == 0:
    print(max(
        dp[N+2][0],
        dp[N+2][1],
        dp[N+1][0]
    ))
else:
    print(max(
        dp[N+2][1],
        dp[N+2][2],
        dp[N+1][0],
        dp[N+1][1]
    ))

Submission status: Runtime Error

Solution code:
from math import *
g=[[0]*202 for _ in range(202)]
for i in range(1,201):
    for j in range(1,201):
        g[i][j]=gcd(i,j)
n=int(input())
a=0
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            a+=g[g[i][j]][k]
print(a)

Submission status: Runtime Error

Solution code:
import itertools
import math

n = int(input())
k = int(input())
l = []
for i in range(1,k**n+1):
    l.append(i)
    
    
a = list(itertools.combinations(l, 3))
ans = 0
for i in range(len(a)):
    b = math.gcd( math.gcd(a[i][0],a[i][1]), a[i][2])
    ans += b
c = list(itertools.combinations(l, 2))

for i in range(len(c)):
    d = math.gcd(c[i][0], c[i][1])
    ans += d
ans = ans * 6 % (10**9 + 7)
e = sum(l)
print(ans+e)

Submission status: Runtime Error

Solution code:
[N,K] = [int(x) for x in input().split()]
l = [0 for i in range(K)]
for i in range(1,K+1):
    l[i] = int(K/i)**N
    for j in range(1,int(K/i)+1):
        l[i] -= l[i*j]
ans = 0
for i in range(1,K+1):
    ans += l[i]*i
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
dp=[0]*(k+1)
mod=int(1e9+7)
for i in range(k,0,-1):
    sm=0
    for j in range(2*i,k+1,i):
        sm=(sm+dp[j])%mod
    dp[i]=pow(k//i,n,mod)-sm

ans=0
for i in range(1,n+1):
    ans+=(dp[i]%mod*i%mod)%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <mutex>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <thread>
#include <vector>
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define SQR(x) (x) * (x)
#define itn int

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);
int bpm(int x, int y) {
  if (x == 0)
    return 0;
  else if (y == 0) {
    return 1;
  }
  int ans = 1;
  x %= MOD;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  for (int i = 0; i < digit; i++) {
    if (((y >> i) & 1) == 1) {
      ans *= x;
      ans %= MOD;
    }
    x = SQR(x);
    x %= MOD;
  }
  return ans;
};
int LIST[100000 + 10]{};
signed main() {
  int N, K;
  cin >> N >> K;
  for (int i = 100000; i >= 1; i--) {
    LIST[i] = bpm(K / i, N) * i;
    for (int j = 2; i * j <= K; j++) {
      LIST[i] -= LIST[i * j] / (i * j) * i;
    }
  }
  int ans = accumulate(ALL(LIST), 0LL) % MOD;
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
def factorization(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

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = (pow(k // i, n, M)
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    
# print(sum((i)*nums[i]%M for i in range(len(nums)))%M)
print((np.arange(k+1) * nums).sum()%M)

Submission status: Runtime Error

Solution code:
M = 1000000007


def main(N=None, K=None):
    if not N or not K:
        N = int(input())
        K = int(input())
    ans = 0
    gcds = {}
    for X in range(K, 0, -1):
        gcds[X] = int(pow(K//X, N, M))
        n = 1
        while True:
            n += 1
            if n*X > K:
                break
            gcds[X] -= gcds[n*X]
        ans += gcds[X]*X
    ans %= M
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 9
    # assert main(3, 200) == 10813692
    # assert main(100000, 100000) == 742202979
    main()

Submission status: Runtime Error

Solution code:
MOD = 1000000007

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(len(gcd_equal_i)):
        ans += (i*gcd_equal_i[i]) % MOD


    print(ans)

Submission status: Runtime Error

Solution code:
import math
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans+=math.gcd(i,math.gcd(j,k)) 
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

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

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

sum += func(1,1,1) + 1

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

Submission status: Runtime Error

Solution code:
import math

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

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

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

sum += func(1,1,1) + 1

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

Submission status: Runtime Error

Solution code:
import math
import itertools
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n, a = map(int, input().split())
list_a = [i for i in range(1, a + 1)]
res = 0
kumi = list(itertools.combinations_with_replacement(list_a, n))
for i in kumi:
    ans = gcd_list(i)
    if i[0] == i[1] and i[0] == i[2]:
        res += ans
    elif i[0] != i[1] and i[0] != i[2] and i[2] != i[1]:
        res += ans*6
    elif i[0] == i[1] or i[0] == i[2] or i[1] == i[2]:
        res += ans*3

print(int(res%(10**9 + 7)))

Submission status: Runtime Error

Solution code:
# Python3 code to demonstrate working of 
# All possible N combination tuples 
# Using product() 
from itertools import product 
from fractions import gcd
from functools import reduce

def find_gcd(list):
    x = reduce(gcd, list)
    return x
# initialize N 
N = int(input())
sum=0
# All possible N combination tuples 
# Using product() 
res = list(product(range(1, N + 1), repeat = 3)) 

for i in res:
    sum=sum+find_gcd(list(i))

# printing result 
print(sum)

Submission status: Runtime Error

Solution code:
import itertools
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

n, k = map(int, input().split())
dp = {}
for i in range(1,n+1):
    lis = list(itertools.combinations(list(i for i in range(k)), i))
    for j in lis:
        dp[str(j)] = gcd(j)
l = list(itertools.combinations_with_replacement(list(i for i in range(k)), n))
ans = 0
for key in l:
    ans += dp[str(set(key))]
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
l = [0 for _ in range(k)]
for i in range(1, k):
    j = pow(k//i, n, 10**9+7)
    while i < k:
        i += i
        j -= l[i-1]
    l[i-1] = j
ans = sum(l) % (10**9+7)

Submission status: Runtime Error

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

def yakusuu(n):
    a = []
    for i in range(1, int(n ** 0.5)):
        if n % i == 0:
            a.append(i, n // i)
    return sum(a)

ans = 0
for i in range(1, k + 1):
    temp = 1
    for j in range(n):
        temp *= (k // i)
        temp %= mod
    ans += (i * 2 - yakusuu(i)) * temp
print(ans)

Submission status: Runtime Error

Solution code:
import math
import sys
import itertools

n, k = map(int, input().split())

k_list = []
for i in range(k):
    k_list.append(i)

k_pairs = list(itertools.combinations(k_list,n))

sum = 0
mod = (10**9) + 7


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    
    return a

def gcd2(a, c):
    while c != 0:
        a, c = c, a % c
        
    return a


for i in range(1, len(k_pairs) +1):
    for j in range(1, len(k_pairs) +1):
        for k in range(1, len(k_pairs) +1):
            sum += gcd2(gcd(i, j), k)
            
print(sum % mod)

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a0, a1, a2, b0, b1, b2 = A[0], 0, 0, A[1], 0, 0
    for a in A[2:]:
        a0, a1, a2, b0, b1, b2 = (
                b0,
                max(b1, a0),
                max(b2, a1),
                a0 + a,
                a1 + a,
                a2 + a)

    if N & 1:
        return max(b2, a1)
    else:
        return max(a0, b1)


print(main())

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
l = [0 for _ range(k)]
for i in range(1, k):
    j = pow(k//i, n, 10**9+7)
    while i < k:
        i += i
        j -= l[i-1]
    l[i-1] = j
ans = sum(l) % (10**9+7)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)

#define INF 2e9
#define ALL(v) v.begin(), v.end()

int k;
int memo[200+1][200+1];
ll N=1000000000+7;

int gcd(int x,int y){
    if(y==0){
        return x;
    }
    return gcd(y,x%y);
}

int main(){
    cin>>k;
    int ans=0;
    for(int a=1;a<=k;a++){
        for(int b=1;b<=k;b++){
            for(int c=1;c<=k;c++){
                ans+=gcd(gcd(a,b),c)%N;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
import math
import itertools
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n, a = map(int, input().split())
list_a = [i for i in range(1, a + 1)]
res = 0
# kumi = list(itertools.product(list_a, repeat=3))
kumi = list(itertools.combinations_with_replacement(list_a, n))
for i in kumi:
    ans = gcd_list(i)
    if i[0] == i[1] and i[0] == i[2]:
        res += ans
    elif i[0] != i[1] and i[0] != i[2] and i[2] != i[1]:
        res += ans*6
    elif i[0] == i[1] or i[0] == i[2] or i[1] == i[2]:
        res += ans*3

print(res/(10**9 + 7))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import math

sys.setrecursionlimit(10 ** 6)

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

input_line = input()
inputs = input_line.split(' ')
N, K = [int(s) for s in inputs]

ans = 0
for i in range(1,K+1):
    b = 0
    for j in range(i+1,K+1):
        if j%i==0:
            b += 1
    for j in range(i,K+1):
        ans += (b**(N-1))*permutations_count(N, j)
    ans = ans % (1000000000+7)

print(ans)

Submission status: Runtime Error

Solution code:
import math
import itertools
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n, a = map(int, input().split())
list_a = [i for i in range(1, a + 1)]
res = 0
# kumi = list(itertools.product(list_a, repeat=3))
kumi = list(itertools.combinations_with_replacement(list_a, n))
for i in kumi:
    ans = gcd_list(i)
    if i[0] == i[1] and i[0] == i[2]:
        res += ans
    elif i[0] != i[1] and i[0] != i[2] and i[2] != i[1]:
        res += ans*6
    elif i[0] == i[1] or i[0] == i[2] or i[1] == i[2]:
        res += ans*3

print(res)

Submission status: Runtime Error

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(K+1):
    baisuu = K % i
    tmp = 1
    for _ in range(N):
        tmp *= baisuu
        tmp %= mod
    s += tmp * (i - 1)

print(s)

Submission status: Runtime Error

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: Runtime Error

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(K+1):
    baisuu = K % i
    tmp = 1
    for _ in range(N)
        tmp *= baisuu
        tmp %= mod
    s += tmp * (i - 1)

print(s)

Submission status: Runtime Error

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: Runtime Error

Solution code:
from functools import lru_cache

@lru_cache(maxsize = None)

def fibo(N,K):
    if K == 1:
        return 1
    else:
        return ( K + fibo(N,K-1) + 2**N-2) % 1000000007
      
N,K=map(int,input().split())

print(fibo(N,K))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
 
def aaa(*numbers):
    return reduce(math.gcd, numbers)
 
def bbb(n,k):
    lst = []
    global num
    for i in range(1,n+1):
        bbb(i,k)
        lst.append(aaa(num))
        if num[i] > k:
            num[i].pop(0)
    
n,k=(int(x) for x in input().split())
list = []
num = []
for i in range(1,n+1):
    num.append(i)
    
bbb(n,k)
print(sum(list))

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import itertools
import collections
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)[0]

n, k = map(int, input().split(' '))

ls = list(range(1, k+1))
ans = 0
n_fact = math.factorial(n)
for v in itertools.combinations_with_replacement(ls, n):
  gcd_val = gcd(v)
  c = list(dict(collections.Counter(v)).values())
  c = [math.factorial(x) for x in c]
  count = int(n_fact / reduce(lambda a, b: a*b, c))
  ans += gcd_val * count
  
print(ans%(10**9+7))