Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
import collections

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

MOD = pow(10, 9)+7

def combi(n, k, MOD):
    numer = 1
    for i in range(n, n-k, -1):
        numer *= i
        numer %= MOD
    denom = 1
    for j in range(k, 0, -1):
        denom *= j
        denom %= MOD
    return (numer*(pow(denom, MOD-2, MOD)))%MOD

def main():
    K = int(input())
    S = input()[:-1]
    lenS = len(S)
    ans = 0
    for i in range(lenS, lenS+K+1):
        k = min(i-lenS, lenS-1)
        ans += combi(i-1, k, MOD)*pow(25, i-lenS, MOD)*pow(26, lenS+K-i, MOD)
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

N = 2100000
MAX_NUM = N + 1
MOD = pow(10, 9) + 7

fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]

fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1

for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def combinations(n,k):
    global fac, finv
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD

def main():
    K = int(input())
    S = input()[:-1]
    lenS = len(S)
    ans = 0
    for i in range(lenS, lenS+K+1):
        k = min(i-lenS, lenS-1)
        ans += (((combinations(i-1, k)*pow(25, i-lenS, MOD))%MOD)*pow(26, lenS+K-i, MOD))%MOD
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

def func(n):
    if n%2==0:
        return (-g1[n]*g2[n//2]*pow(inverse[2],n//2,mod))%mod
    else:
        return 0

import sys

sys.setrecursionlimit(10**5)

N=int(input())
edge=[[] for i in range(N)]
parent=[0]*N
deg=[1]*N
deg[0]=0
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


def prv(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            parent[nv]=v
            prv(nv,v)

prv(0,-1)

for i in range(N):
    new=[]
    for v in edge[i]:
        if v!=parent[i]:
            new.append(v)
    edge[i]=new


from collections import deque
ans = list(v for v in range(N) if deg[v]==0)
deq = deque(ans)
used = [0]*N

while deq:
    v = deq.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)


dp=[[] for i in range(N)]
sz=[0 for i in range(N)]

for v in ans[::-1]:
    sz[v]=1
    dp[v]=[0]*(sz[v]+1)
    dp[v][1]=1
    for nv in edge[v]:
        merged=[0]*(sz[v]+sz[nv]+1)
        for i in range(sz[v]+1):
            for j in range(sz[nv]+1):
                merged[i+j] +=dp[v][i]*dp[nv][j]
                merged[i+j]%=mod
        sz[v]+=sz[nv]
        dp[v] =merged
    dp[v][0]=(sum(func(k)*dp[v][k] for k in range(1,sz[v]+1)))%mod

print((-dp[0][0])%mod)

### FIXED CODE ###

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys

sys.setrecursionlimit(10**4)

N=int(input())
edge=[[] for i in range(N)]
parent=[0]*N
deg=[1]*N
deg[0]=0
for i in range(N-1):
    x,y=map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)


def prv(v,pv):
    for nv in edge[v]:
        if nv!=pv:
            parent[nv]=v
            prv(nv,v)

prv(0,-1)

for i in range(N):
    new=[]
    for v in edge[i]:
        if v!=parent[i]:
            new.append(v)
    edge[i]=new


from collections import deque
ans = list(v for v in range(N) if deg[v]==0)
deq = deque(ans)
used = [0]*N

while deq:
    v = deq.popleft()
    for t in edge[v]:
        deg[t] -= 1
        if deg[t]==0:
            deq.append(t)
            ans.append(t)


dp=[[] for i in range(N)]
sz=[0 for i in range(N)]

for v in ans[::-1]:
    sz[v]=1
    dp[v]=[0]*(sz[v]+1)
    dp[v][1]=1
    for nv in edge[v]:
        merged=[0]*(sz[v]+sz[nv]+1)
        for i in range(sz[v]+1):
            for j in range(sz[nv]+1):
                merged[i+j]=(merged[i+j]+dp[v][i]*dp[nv][j])%mod
        sz[v]+=sz[nv]
        dp[v] =merged
    for k in range(1,sz[v]+1):
        dp[v][0]=(dp[v][0]-(g1[k]*g2[k//2])%mod*((k+1)%2)*dp[v][k])%mod

print((-dp[0][0]*pow(inverse[2],N//2,mod))%mod)
### BUGGY CODE ###

N, *A = map(int, open(0).read().split())
xo = [0]
sm = [0]
for a in A:
    xo.append(xo[-1] ^ a)
    sm.append(sm[-1] + a)
xo.append(0)
sm.append(0)
ans = 0
for left in range(N):
    ok, ng = left, N
    while ok + 1 != ng:
        md = (ok + ng) // 2
        x = xo[md + 1] ^ xo[left]
        s = sm[md + 1] - sm[left]
        if x == s:
            ok = md
        else:
            ng = md
    ans += ok - left + 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = right = total = 0
for left in range(N):
    while right < N and total ^ A[right] == total + A[right]:
        total += A[right]
        right += 1
    ans += right - left
    if left == right:
        right += 1
    else:
        total -= A[left]
print(ans)
### BUGGY CODE ###

import numpy as np

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

unq=np.array(list(set(A)))
A=np.array(A)

ct=np.zeros(unq.size,dtype=int)

for i in range(unq.size):
	ct[i]=sum(unq[i]==A)

if unq.size > K:
	x=unq.size-K
	sort_ct=np.sort(ct)
	ans=sum(sort_ct[list(range(x))])
else :
	ans=0

print(ans)


### FIXED CODE ###

import collections
import numpy

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

A = collections.Counter(A)
C=A.most_common()

if len(C)> K:
	dels=len(C) - K
	delsList=numpy.array(C[-dels:])
	ans=sum(delsList)[1]
else :
	ans=0

print(ans)
### BUGGY CODE ###

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all_patern = 2 ** n - 1
minus_a = combination(n, a)
minus_b = combination(n, b)
print((all_patern % mod - minus_a - minus_b) % mod)

### FIXED CODE ###

def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod - 2, mod) % mod
    return res

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
all_patern = pow(2, n, mod) - 1
minus_a = combination(n, a)
minus_b = combination(n, b)
print((all_patern - minus_a - minus_b) % mod)
### BUGGY CODE ###

n = int(input())
bits = {}
count = 0
for i in range(n):
    x = int(input())
    if bits.get(0, 0) == 1:
        print("No")
        continue
    if bits.get(x, 0) == 1:
        y = x
        while bits.get(y, 0) == 1:
            y -= 1
        if y == 0 and count != x:
            print("No")
        else:
            bits[y] = 1
            count += 1
            for i in range(y+1, x+1):
                bits[i] = 0
                count -= 1
            print("Yes")
    else:
        bits[x] = 1
        count += 1
        print("Yes")

### FIXED CODE ###

n = int(input())
bits = set()
c1 = 0
count = 0
ans = []
for i in range(n):
    x = int(input())
    if x in bits:
        y = x
        while c1 < y and y in bits:
            y -= 1
        if y <= c1:
            y = 0
        if y == 0 and count != x:
            c1 = max(x, c1)
            ans.append("No")
        else:
            bits.add(y)
            ans.append("Yes")
            count += 1
            if y == 0:
                if i <= n-2:
                    ans.append("No\n"*(n-2-i) + "No")
                break
            for i in range(y+1, x+1):
                bits.remove(i)
                count -= 1
    else:
        bits.add(x)
        count += 1
        ans.append("Yes")
print("\n".join(ans))
### BUGGY CODE ###

from collections import deque

n = int(input())
a = deque(map(int, input().split()))
b = deque()

for _ in range(n):
    b.append(a.popleft())
    b.reverse()

print(*b)


### FIXED CODE ###

n = int(input())
a = input().split()

a_odd = a[0::2]
a_even = a[1::2]

if n % 2 == 1:
    print(" ".join(a_odd[::-1] + a_even))
else:
    print(" ".join(a_even[::-1] + a_odd))
### BUGGY CODE ###

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


a = Y//10000
b = Y//5000
c = Y//1000

flag = False

for i in range(a+1):
    if flag == True:
        break
    for j in range(b+1-2*i):
        if flag == True:
            break
        for k in range(c+1-10*i-5*j):
            if i+j+k == N:
                if i*10000+j*5000+k*1000 == Y:
                    flag = True
                    s = i
                    t = j
                    u = k

if flag == True:
    print(s,t,u)
else:
    print(-1,-1,-1)

### FIXED CODE ###

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


a = Y//10000
b = Y//5000

flag = False

for i in range(a+1):
    if flag == True:
        break
    for j in range(b+1):
        if N-i-j<0:
            break
        if i*10000+j*5000+(N-i-j)*1000 == Y:
            flag = True
            s = i
            t = j
            u = N-i-j
            break

if flag == True:
    print(s,t,u)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()

while True:
    v = a[0]
    tmp.add(v)
    a = [item for item in a if item%v!=0]
    if not a:
        break

# tmp = [a[0]]
# for i in range(1, n):
#     num = a[i]
#     for i in range():
#         item = tmp[i]
#         if num%item==0:
#             break
#     else:
#         tmp.append(num)
tmp = set(tmp) - s
print(len(tmp))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
ok = set()
p = set(list(range(1, 10**6+1)))
ck = list(c.keys())
ck.sort()
for num in ck:
    if num in p:
        ok.add(num)
    i = 2
    while num*i<=10**6:
        if num*i in p:
            p.remove(num*i)
        i += 1
tmp = ok
tmp = set(tmp) - s
print(len(tmp))
### BUGGY CODE ###

from collections import deque
def bfs():
    d = [[float("inf") for i in range(W)] for j in range(H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    que = deque([])

    for i in range(W):
        for j in range(H):
            if S[j][i] == "#":
                d[j][i] = 0
                que.append((i,j))

    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0<=nx<W and 0<=ny<H and S[ny][nx] != "#" and d[ny][nx] == float("inf"):
                que.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]] + 1
    ans = 0
    for i in range(W):
        for j in range(H):
            if S[j][i] !="#":
                ans = max(ans,d[j][i])
    return ans

H,W = map(int,input().split())
S = [list(input()) for i in range(H)]

print(bfs())


### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
grid = []
dq = deque([])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
d = [[-1 for i in range(w)] for j in range(h)]
for i in range(h):
    maze = list(input())
    for j in range(w):
        if maze[j] == "#":
            dq.append((j,i))
            d[i][j] = 0
    grid.append(maze)
while dq:
    x,y = dq.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx <= w-1 and 0 <= ny <= h-1 and grid[ny][nx] != "#" and d[ny][nx] == -1:
            dq.append((nx,ny))
            d[ny][nx] = d[y][x] + 1
            ans = max(ans,d[ny][nx])
print(ans)
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=t3(m)

heapify(A)
BC.sort(key=lambda x:x[1])

for b,c in BC:
    for _ in range(b):
        a=heappop(A)
        if a>=c:
            heappush(A,a)
            break;
        else:
            heappush(A,c)

print(sum(A))

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
# from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
from heapq import heapify,heappush,heappop
n,m=n1()
A=n1()
BC=t3(m)

heapify(A)
BC.sort(key=lambda x:-x[1])

D=[]
for b,c in BC:
    D.extend([c]*b)
    if len(D)>=n:
        break
D=D[:n]


for d in D:
    a=heappop(A)
    if a>=d:
        heappush(A,a)
        break;
    else:
        heappush(A,d)

print(sum(A))
### BUGGY CODE ###

S = str(input())
Q = int(input())

for q in range(Q):
    query = list(map(str, input().split()))
    tmp = []
    if int(query[0]) == 1:
        S = S[::-1]
    else:
        if int(query[1]) == 1:
            tmp.append(query[2])
            tmp.append(S)
            S = ''.join(tmp)
        else:
            tmp.append(S)
            tmp.append(query[2])
            S = ''.join(tmp)

print(S)

### FIXED CODE ###

from collections import deque

S = str(input())
Q = int(input())

d = deque(list(S))

rev = False

for q in range(Q):
    query = list(map(str, input().split()))
    if int(query[0]) == 1:
        if rev:
            rev = False
        else:
            rev = True
    else:
        if int(query[1]) == 1:
            if not rev:
                d.appendleft(query[2])
            else:
                d.append(query[2])
        else:
            if not rev:
                d.append(query[2])
            else:
                d.appendleft(query[2])

if rev:
    print(''.join(d)[::-1])
else:
    print(''.join(d))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n,k,q = map(int, input().split())
l = []
for i in range(n):
    l.append(k)
    
for i in range(q):
    a = int(input())
    l = list(map(lambda x: x - 1, l))
    l[a-1] += 1

for i in l:
    if i <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

# -*- coding: utf-8 -*-

n,k,q = map(int, input().split())
l = []
for i in range(n):
    l.append(0)

for i in range(q):
    a = int(input())
    l[a-1] += 1


for i in l:
    if i + k - q <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n = int(input())
s = [int(input()) for _ in range(n)]

ans = 0

for i in range(2**n):
    tmp = 0
    for j in range(n):
        if (i>>j) & 1:
            tmp += s[j]
    if tmp%10:
        ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

n = int(input())
s = [int(input()) for _ in range(n)]

s.sort()
ans = sum(s)
flag = True
if not ans%10:
    flag = False
    for i in s:
        if i%10:
            ans -= i
            flag = True
            break

if not flag:
    ans = 0

print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
dp = [[0]*13 for i in range(n+5)]
dp[0][0] = 1
mod = 10**9+7
for i in range(n):
	    for j in range(13):
	    	    if s[i] != '?':
	    	    	    x = int(s[i])
	    	    	    ni = i+1
	    	    	    nj = (j*10+x)%13
	    	    	    dp[ni][nj] += dp[i][j]
	    	    	    dp[ni][nj]%= mod
	    	    	    continue
	    	    for d in range(10):
	    	    	    ni = i+1
	    	    	    nj = (j*10+d)%13
	    	    	    dp[ni][nj] += dp[i][j]
	    	    	    dp[ni][nj]%= mod
print(dp[n][5])

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for i in range(n+5)]#dp[i][j] :=先頭i文字を見たとき、その数字を13で割ったあまりがｊであるような場合の数
dp[0][0] = 1#先頭０文字は”０”　で、１３で割ったあまりは０だから　dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if s[i] == "?":
            for d in range(10):
                dp[i+1][(j*10+d)%13] += dp[i][j]
                dp[i+1][(j*10+d)%13] %= mod
                
        else:
            dp[i+1][(j*10+int(s[i]))%13] += dp[i][j]
            dp[i+1][(j*10+int(s[i]))%13] %= mod
ans = dp[n][5]
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
assert len(S) == N
count = 0
for i in range(0, len(S)-2):
  for j in range(i+1, len(S)-1):
    for k in range(j+1, len(S)):
      if S[i] == S[j]:
        continue
      if S[i] == S[k]:
        continue
      if S[j] == S[k]:
        continue
      if j - i == k - j:
        continue
      count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
assert len(S) == N
count = 0

# j-i = k-jを探す
for i in range(0, len(S)-2):
  for j in range(i+1, len(S)-1):
    k = j + (j - i)
    if k < len(S):
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        count += 1
numR = 0
numG = 0
numB = 0
for s in S:
  if s == 'R':
    numR += 1
  elif s == 'G':
    numG += 1
  else:
    numB += 1

print(numR * numG * numB - count)
### BUGGY CODE ###

#それぞれの時間に注目して最大のものを考える
#いもす法？
#チャンネル同じ場合を考慮し忘れていた
#チャンネル分けてチェックすればええやん
n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]#1~10**5+1
for i in range(n):
    s,t,_c=map(int,input().split())
    imos[s-1][_c-1]+=1
    imos[t][_c-1]-=1
for i in range(1,10**5+1):
    for j in range(c):
        imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
    for j in range(c):
        imosans[i]+=(imos[i][j]>=1)
print(max(imosans))

### FIXED CODE ###

#それぞれの時間に注目して最大のものを考える
#いもす法？
#チャンネル同じ場合を考慮し忘れていた
#チャンネル分けてチェックすればええやん
n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]#1~10**5+1
for i in range(n):
    s,t,_c=map(int,input().split())
    imos[s-1][_c-1]+=1
    imos[t][_c-1]-=1
for i in range(1,10**5+1):
    for j in range(c):
        imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
    for j in range(c):
        imosans[i]+=(imos[i][j]>=1)
print(max(imosans))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd

def lcm(x, y):
  return (x * y) // gcd(x, y)

def lcm_list(numbers):
  return reduce(lcm, numbers, 1)

MOD = 10 ** 9 + 7  
n = int(input())
A = list(map(int, input().split()))

l = lcm_list(A)
ans = sum([l // x for x in A]) % MOD

print(ans)


### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
  return (x * y) // gcd(x, y)

MOD = 10 ** 9 + 7  
n = int(input())
A = list(map(int, input().split()))

l = 1
for i in A:
  l = lcm(l, i)
l %= MOD

ans = 0
for i in A:
  ans += l * pow(i, MOD - 2, MOD)
  ans %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())
s = [str(input()) for _ in range(n)]
ans = 0
for i in range(n):
    s[i] = sorted(s[i])


for i in range(n):
    for j in range(i,):
        if s[i] == s[j]:
            ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
for i in range(n):
  s[i] = ''.join(sorted(s[i]))
t = {}
for i in range(n):
  if s[i] in t:
    t[s[i]] += 1
  else:
    t[s[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))
### BUGGY CODE ###

def main():
    K = int(input())

    su = 0
    # for a in range(1, K+1):
    #     for b in range(1, a+1):
    #         for c in range(1, b+1):
    #             tmp = dgcd(a, b, c)
    #             if a == b and b == c:
    #                 pass
    #             elif a == b or b == c or a == c:
    #                 tmp *= 3
    #             else:
    #                 tmp *= 6
    #             su += tmp
    # print(su)
    for a in range(1, K+1):
        for b in range(1, K+1):
            for c in range(1, K+1):
                tmp = dgcd(a, b, c)

                su += tmp
    print(su)


def dgcd(a, b, c):
    return gcd(gcd(a, b), c)


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


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    K = int(input())

    su = 0
    for a in range(1, K+1):
        for b in range(1, a+1):
            for c in range(1, b+1):
                tmp = dgcd(a, b, c)
                if a == b and b == c:
                    tmp *= 1
                elif a == b or b == c or a == c:
                    tmp *= 3
                else:
                    tmp *= 6

                su += tmp
    print(su)


def dgcd(a, b, c):
    return gcd(gcd(a, b), c)


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


if __name__ == '__main__':
    main()
### BUGGY CODE ###

s = input()
t = input()
N = len(s)
M = len(t)

dp = [[0]*(N+1) for i in range(M+1)]

for i in range(1,M+1):
  for j in range(1,N+1):
    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    if s[j-1] == t[i-1]:
      dp[i][j] += 1
L = dp[-1][-1]
i = M
j = N
ans = [""]*L
cur = L-1
while i>=0 and j>=0:
  if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
    ans[cur] = s[j-1]
    i -= 1
    j -= 1
    cur -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    j -= 1
print("".join(ans))

### FIXED CODE ###

s = input()
t = input()
N = len(s)
M = len(t)

dp = [[0]*(N+1) for i in range(M+1)]

for i in range(1,M+1):
  for j in range(1,N+1):
    if s[j-1] == t[i-1]:
      dp[i][j] = dp[i-1][j-1]+1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
L = dp[-1][-1]
i = M
j = N
ans = [""]*L
cur = L-1
while i>=0 and j>=0:
  if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
    ans[cur] = s[j-1]
    i -= 1
    j -= 1
    cur -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    j -= 1
print("".join(ans))
### BUGGY CODE ###

M = 10**9+7
N = int(input())
A = list(map(int,input().split()))

maxA = max(A)
K = len(str(bin(maxA)))-2
ans = 0
for k in range(K):
    N1 = 0
    for i in range(0,N):
        N1 += ( (A[i] >> k) & 1)
    N0 = N-N1
    ans += (((1<<k)%M) *N0 *N1) % M

ans %= M    
print(int(ans))

### FIXED CODE ###

M = 10**9+7
N = int(input())
A = list(map(int,input().split()))

ans = 0
for k in range(61):
    N1 = 0
    N1 = sum([1 for a in A if ( (a >> k) & 1)])
    ans += (((1<<k)) *(N-N1) *N1)
    ans %= M    

print(ans)