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

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for i in range(N):
   i += 1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      l = len(circle)
      score = circle[l-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)

### FIXED CODE ###

N, K = map(int,input().split())
p = list(map(int,input().split()))
c = list(map(int,input().split()))
K = K-1
ans = -10**9-1
for h in range(N):
   i = h+1
   start = i
   circle = [c[i-1]]
   i = p[i-1]
   while i != start:
      score = circle[-1] + c[i-1]
      circle.append(score)
      i = p[i-1]
   l=len(circle)
   for j in range(min(l, K+1)):
      if circle[l-1] > 0:
         score = circle[j] + ((K - j)//l)*circle[l-1]
      else:
         score = circle[j]
      ans = max(score, ans)      
print(ans)
### BUGGY CODE ###

#ACを検索して開始位置をインデックスにしておき、それを操作すれば多少はマシか
import numpy as np
N,Q=[int(_) for _ in input().split()]
S=list(input())
hani=[[int(a) for a in input().split()] for j in range(Q)]
ACindex=[S[i]=="A" and S[i+1]=="C" for i in range(N-1)]
for j in hani:
    print(sum(ACindex[j[0]-1:j[1]-1]))

### FIXED CODE ###

#ACを検索して開始位置をインデックスにしておき、それを操作すれば多少はマシか
import numpy as np
N,Q=[int(_) for _ in input().split()]
S=list(input())
hani=[[int(a) for a in input().split()] for j in range(Q)]
ACindex=[0]
cur=0
for i in range(N-1):
    cur+=S[i]=="A" and S[i+1]=="C"
    ACindex.append(cur)
ACindex.append(cur)
for j in hani:
    print(ACindex[j[1]-1]-ACindex[j[0]-1])
### BUGGY CODE ###

s = input()
q = int(input())

roll = False

for i in range(q) :
    inp = input()
    if inp[:1] == '1' :
        roll = not roll
        #print(roll)
    else :
        t, f, c = inp.split()
        #print(t, f, c)
        if (f == '1' and (not roll)) or (f == '2' and roll) :
            s = "{}{}".format(c, s)
        else :
            s = "{}{}".format(s, c)

if roll :
    s = s[::-1]

print(s)


### FIXED CODE ###

from collections import deque

s = input()
q = int(input())

roll = False
ans = deque([s])
preNum = 0

for i in range(q) :
    inp = input()
    if inp[:1] == '1' :
        roll = not roll
        #print(roll)
    else :
        t, f, c = inp.split()
        #print(ans)
        #print(t, f, c)
        if (f == '1' and (not roll)) or (f == '2' and roll) :
            ans.appendleft(c)
            preNum += 1
        else :
            ans.append(c)
#print(ans)
ans = list(ans)
if roll :
    ans[preNum] = ans[preNum][::-1]
    ans = ans[::-1]

#print(ans)
#print("".join(ans))
for s in ans :
    print(s, end='')
### BUGGY CODE ###

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
a,b=map(int,input().split())
g=gcd(a,b)
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=set()
  while n!=1:
    pp=table[n]
    p.add(pp)
    n//=pp
  return p

print(len(prime_fact(g,prime_table(g)))+1)

### FIXED CODE ###

def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
a,b=map(int,input().split())
g=gcd(a,b)

c=1
for i in range(2,10**6+1):
  if g%i==0:
    c+=1
    while g%i==0:
      g//=i
if g!=1:
  c+=1
print(c)
### BUGGY CODE ###

H = int(input())
n = 1
while True:
    n += 1
    H = H // 2
    if H == 1:
        break

print(2 ** n - 1)

### FIXED CODE ###

import  math
H = int(input())
k = int(math.log2(H))
print(2 ** (k + 1) - 1)
### BUGGY CODE ###

# coding: utf-8

x, y, z, k = [int(i) for i in input().split()]

a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

ab = [ai + bi for ai in a for bi in b]
ab.sort(reverse=True)
ab = ab[:k]

abc = [abi + ci for abi in ab for ci in c]
abc.sort(reverse = True)

for i in range(len(abc)):
  if i < k:
    print(abc[i])
  else:
    break

### FIXED CODE ###

# coding: utf-8

x, y, z, k = [int(i) for i in input().split()]

a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

ab = [ai + bi for ai in a for bi in b]
ab.sort(reverse=True)
ab = ab[:k]

abc = [abi + ci for abi in ab for ci in c]
abc.sort(reverse = True)

for i in range(len(abc)):
  if i < k:
    print(abc[i])
  else:
    break
### BUGGY CODE ###

A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s = [-inf] + s + [inf]
t = [-inf] + t + [inf]

def binsearch_l(seq, l, r, tar):
    if r - l < 2: return l
    #
    m = l + (r - l) // 2
    # print("##", l, r, (m, seq[m]), tar)
    if seq[m] <= tar:
        return binsearch_l(seq, m, r, tar)
    else:
        return binsearch_l(seq, l, m, tar)

ans_Q = []
i_last = j_last = 0
for idx, x_tmp in sorted(enumerate(x), key=lambda x: x[1]):
    i_l = binsearch_l(s, i_last, A + 1, x_tmp)
    j_l = binsearch_l(t, j_last, B + 1, x_tmp)
    #
    ans = inf
    for i, j in ((i_l, j_l), (i_l + 1, j_l), (i_l, j_l + 1), (i_l + 1, j_l + 1)):
        if i < 1 or A < i: continue
        if j < 1 or B < j: continue
        ans_tmp_s = abs(x_tmp - s[i]) + abs(s[i] - t[j])
        ans_tmp_t = abs(x_tmp - t[j]) + abs(s[i] - t[j])
        ans_tmp = min(ans_tmp_s, ans_tmp_t)
        # print("#", x_tmp, s[i], t[j], ans_tmp)
        if ans > ans_tmp:
            ans = ans_tmp
    #
    i_last, j_last = i_l, j_l
    ans_Q.append((idx, ans))

for idx, ansi in sorted(ans_Q, key=lambda x: x[0]):
    print(ansi)

### FIXED CODE ###

import sys, bisect
input = sys.stdin.readline
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s = [-inf] + s + [inf]
t = [-inf] + t + [inf]

ans_Q = [None] * Q
i_last = j_last = 0
for idx, x_tmp in sorted(enumerate(x), key=lambda x: x[1]):
    i_l = max(0, bisect.bisect_left(s, x_tmp, lo=i_last) - 1)
    j_l = max(0, bisect.bisect_left(t, x_tmp, lo=j_last) - 1)
    # print("#", x_tmp, (i_l, s[i_l]), (j_l, t[j_l]))
    #
    ans = inf
    for i, j in ((i_l, j_l), (i_l + 1, j_l), (i_l, j_l + 1), (i_l + 1, j_l + 1)):
        if i < 1 or A < i: continue
        if j < 1 or B < j: continue
        ans_tmp_s = abs(x_tmp - s[i]) + abs(s[i] - t[j])
        ans_tmp_t = abs(x_tmp - t[j]) + abs(s[i] - t[j])
        ans_tmp = min(ans_tmp_s, ans_tmp_t)
        # print("#", x_tmp, s[i], t[j], ans_tmp)
        if ans > ans_tmp:
            ans = ans_tmp
    #
    i_last, j_last = i_l, j_l
    ans_Q[idx] = ans

for ansi in ans_Q: print(ansi)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    dp = [True for _ in range(max(A)+1)]
    counts = [0 for _ in range(max(A)+1)]
    for a in A:
        if dp[a]:
            counts[a] += 1
            i = 2
            v = a * i
            while v <= max(A):
                dp[v] = False
                i += 1
                v = a * i
    cnt = 0
    for a in A:
        if dp[a] and counts[a] == 1:
            cnt += 1
    print(cnt)

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    import collections
    counter = collections.Counter(A)
    maxA = max(A)
    dp = [True for _ in range(max(A)+1)]
    for a in A:
        if counter[a] > 1:
            dp[a] = False
        for j in range(a+a, maxA+1, a):
            dp[j] = False
    #print(dp)
    print(sum(1 for a in A if dp[a]))

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

#!/usr/bin/env python3

while(True):
	try:
		a,b=map(int, input().split())
	except EOFError:
		break
	gcd=1
	for i in range(1, a):
		if(a%i==0 and b%i==0):
			gcd=i
	lcm=int(a*b/gcd)
	print("{0} {1}".format(gcd, lcm))

### FIXED CODE ###

#!/usr/bin/env python3

while(True):
	try:
		a,b=map(int, input().split())
	except EOFError:
		break

	#euclidian algorithm	
	r=a%b
	x,y=a,b
	while(r>0):
		x=y
		y=r
		r=x%y
	gcd=y
	lcm=int(a*b/gcd)
	print("{0} {1}".format(gcd, lcm))
### BUGGY CODE ###

n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]

for i in range(n):
  if i+1 < n:
    graph[i].append(i+1)
  if i-1 >=0:
    graph[i].append(i-1)
graph[x-1].append(y-1)
graph[y-1].append(x-1)

ans = [0] * (n-1)
from collections import deque
for i in range(n):
  dist = [-1] * n
  dist[i] = 0
  d = deque()
  d.append(i)
  while d:
    v = d.popleft()
    for j in graph[v]:
      if dist[j] != -1:
        continue
      dist[j] = dist[v] + 1
      ans[dist[j] - 1] += 1
      d.append(j)
for a in ans:
  print(a//2)



### FIXED CODE ###

n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]
 
for i in range(n):
  if i+1 < n:
    graph[i].append(i+1)
  if i-1 >=0:
    graph[i].append(i-1)
graph[x-1].append(y-1)
graph[y-1].append(x-1)
 
ans = [0] * (n-1)
from collections import deque
for i in range(n):
  dist = [-1] * n
  dist[i] = 0
  d = deque()
  d.append(i)
  while d:
    v = d.popleft()
    for j in graph[v]:
      if dist[j] != -1:
        continue
      dist[j] = dist[v] + 1
      ans[dist[j] - 1] += 1
      d.append(j)
for a in ans:
  print(a//2)
### BUGGY CODE ###

import functools
import operator

n = int(input())
number = map(int,input().split())
X = functools.partial(functools.reduce, operator.mul)

s=X(number)
if s>pow(10,18):
    print(-1)
else:
    print(s)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))

    if 0 in A:
        print(0)
        return

    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return
    print(prod)
main()
### BUGGY CODE ###

import math

def ncr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

a = int(input())
A = list(map(int, input().split()))  
d = {}
for k in A:
  if k in d:
    d[k] += 1
  else:
    d[k] = 1
 
res = 0
for k in d:
    if d[k] >= 2:
      res += ncr(d[k], 2)

for k in A:
  temp = res
  m = d[k]
  d[k] -= 1
  if m >= 2:
    temp -= ncr(m, 2)

  if d[k] >= 2:
    temp += ncr(d[k], 2)
  print(temp)
  d[k] += 1


### FIXED CODE ###

from operator import mul
from functools import reduce

def ncr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

a = int(input())
A = list(map(int, input().split()))  
d = {}
for k in A:
  if k in d:
    d[k] += 1
  else:
    d[k] = 1
 
res = 0
for k in d:
    if d[k] >= 2:
      res += ncr(d[k], 2)

for k in A:
  temp = res
  m = d[k]
  d[k] -= 1
  if m >= 2:
    temp -= ncr(m, 2)

  if d[k] >= 2:
    temp += ncr(d[k], 2)
  print(temp)
  d[k] += 1
### BUGGY CODE ###

from itertools import product


def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    costs = [
        [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    ]
    for s, g in product(range(n), repeat=2):
        if costs[s][g] == 0:
            continue
        if s - d >= 0:
            costs[s][g] = costs[s - d][g] - costs[s - d][s]
            continue
        before = 0 if g - d < 0 else costs[s][g - d]
        costs[s][g] = abs(index[g - d] // w - index[g] // w) + abs(index[g - d] % w -
                                                                   index[g] % w) + before
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))


### FIXED CODE ###

import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = [[int(i) for i in input().strip().split(" ")] for _ in range(h)]
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = [None for _ in range(h * w)]
cs = [None for _ in range(h * w)]
for _r, _a in enumerate(a):
    for _c, __a in enumerate(_a):
        rs[__a - 1] = _r
        cs[__a - 1] = _c
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])
### BUGGY CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(501)] for _ in range(501)] 
  for _ in range(M):
    l, r = map(int, input().split())
    DP[l][r] += 1

  for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
      ans += sum(DP[i][:q+1])
    print(ans)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(N+1)] for _ in range(N+1)] 
  for _ in range(M):
    l, r = map(int, input().split())
    DP[l][r] += 1

  cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
  for i in range(1, N+1):
    for j in range(1, N+1):
      cum[i][j] = DP[i][j] + cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1]

  for _ in range(Q):
    p, q = map(int, input().split())
    print(cum[q][q] - cum[p-1][q] - cum[q][p-1] + cum[p-1][p-1])


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

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

ans = -float('inf')
for i in range(N):
    score = -float('inf')
    cnt = 0
    k = 0
    while k < K:
        ni = P[i] - 1
        cnt += C[ni]
        score = max(cnt, score)
        i = ni
        k += 1
    ans = max(ans, score)
print(ans)


### FIXED CODE ###

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

ans = -float('inf')
for i in range(N):
    cnt = 0
    k = 0
    done = set()
    S = []
    while i not in done:
        done.add(i)
        ni = P[i] - 1
        if len(S):
            S.append(S[-1] + C[ni])
        else:
            S.append(C[ni])
        i = ni
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * ((K // len(S)) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)
### BUGGY CODE ###

L,R = map(int, input().split())
Smin=2019
Lo=L%2019
Ro=R-(L-Lo)
for x in range(L,R):
    for y in range(x+1,R+1):
        Sa=x*y
        S=Sa%2019
        if Smin>S:
            Smin=S
print(Smin)



### FIXED CODE ###

L,R = map(int, input().split())
Smin=2019
Lo=L%2019
Ro=R-(L-Lo)
if Ro>=2019:
    Smin=0
if Ro<2019:
    for x in range(Lo,Ro):
        for y in range(x+1,Ro+1):
            Sa=x*y
            S=Sa%2019
            if Smin>S:
                Smin=S
print(Smin)
### BUGGY CODE ###

K = int(input())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
sum=0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(gcd(i,j),k)

print(sum)
# print(gcd(2,6))


### FIXED CODE ###

K = int(input())
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)
sum=0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(gcd(i,j),k)

print(sum)
# print(gcd(2,6))
### BUGGY CODE ###

n, m = map(int, input().split())
answer = 0
ans = []
pen = []
penal = 0
p = [0]*m
x = [0]*m
for i in range(m):
    p[i], x[i] = map(str, input().split())
    if x[i] == "AC":
        ans.append(p[i])
    elif x[i] == "WA":
        for j in range(len(ans)):
            if p[i] == ans[j]:
                penal -= 1
                break
        penal += 1
        pen.append((p[i], x[i]))

ans = tuple(set(ans))

for i in range(len(pen)):
    if pen[i][0] not in ans:
        penal -= 1


print("{}".format(len(ans)) + " {}".format(penal))

### FIXED CODE ###

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

problem = [0] * n
count = [0] * n

penal = 0

for i in range(m):
    p, x = map(str, input().split())
    p = int(p) - 1
    if x == "AC":
        if problem[p] == 0:
            problem[p] = 1
    elif x == "WA":
        if problem[p] == 0:
            count[p] += 1

for i in range(n):
    if problem[i] == 0:
        count[i] = 0

print("{}".format(sum(problem)) + " {}".format(sum(count)))
### BUGGY CODE ###

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

Query = []
for _ in range(M):
    Query.append(list(map(int, input().split())))


Query.sort(key = lambda x : x[1])

count = 0
while len(Query) > 0:
    Query = list(filter(lambda x: x[0] >= Query[0][1], Query))
    count += 1

print(count)


### FIXED CODE ###

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

Query = []
for _ in range(M):
    Query.append(list(map(int, input().split())))


Query.sort(key = lambda x : x[1])

count = 1
last = Query[0][1]
for i in range(1, M):
    if Query[i][0] >= last:
        count += 1
        last = Query[i][1]
print(count)
### BUGGY CODE ###

N = int(input())
K = int(input())

ans = 0
for n in range(N+1):
    cnt_zero = str(n).count('0')
    if cnt_zero == len(str(n)) - K:
        ans += 1

print(ans)

### FIXED CODE ###

n = str(input())
k = int(input())
l = len(n)

def f(dig, under, num):
  if num > l - dig: return 0
  if num == 0: return 1
  if dig == l-1:
    if under: return int(n[dig])
    else: return 9
  if under:
    if n[dig] == '0':
      res = f(dig+1, True, num)
      #print(dig, under, num, res, 'aaa')
      return res
    else:
      res = f(dig+1, False, num)
      if int(n[dig]) > 1:
        res += (int(n[dig])-1) * f(dig+1, False, num-1)
      res += f(dig+1, True, num-1)
      #print(dig, under, num, res, 'bbb')
      return res
  else:
    res = f(dig+1, False, num)
    res += 9 * f(dig+1, False, num-1)
    #print(dig, under, num, res, 'ccc')
    return res

ans = f(0, True, k)
print(ans)
### BUGGY CODE ###

from bisect import bisect_left as bsl

def main():
    with open(0) as f:
        Q = int(f.readline())
        Query = [tuple(map(int, line.split())) for line in f.readlines()]
    
    p_table = makePtable(10**5)
    p_set = set(p_table)
    Like2017 = [p for p in p_table if (p+1)//2 in p_set]
    database = [bsl(Like2017, i) for i in range(1,10**5+1)]

    for l,r in Query:
        print(database[r] - database[l-1])

def makePtable(N):
    table = list(range(2,N+1))
    result = []
    while len(table) != 0:
        p = table[0]
        result.append(p)
        table = [x for x in table[1:] if x % p != 0]
    return result

main()

### FIXED CODE ###

#クエリにO(1)で返すためのテーブルを用意
import numpy as np
MAX = int(10e5+1)
List = list(range(2,MAX))
P = []
while len(List) > 0:
    p = List[0]
    if p >= np.sqrt(MAX): break
    P.append(p)
    List = [x for x in List if x % p != 0]
P = set(P+List)

Ans = [0] * MAX
cnt = 0
for i in range(1,MAX):
    if i in P and (i+1)//2 in P:
        cnt += 1
    Ans[i] = cnt

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(Ans[r]-Ans[l-1])
### BUGGY CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [0] * 60
  for a in A:
    for i in range(60):
      if (a >> i) & 1 == 1:
        ones[i] += 1
  # print(ones)
  res = 0
  for j in range(N):
    a = A[j]
    for i in range(60):
      if (a >> i) & 1 == 0:
        res += ones[i] * 2 ** i
      else:
        res += (N-ones[i]-j) * 2 ** i
        ones[i] -= 1
      res %= MOD
  
  print(res)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
  N = int(input())
  A = list(map(int, input().split()))
  MOD = 10 ** 9 + 7
  ones = [sum(1 for a in A if a&(1<<i)) for i in range(60)]
  res = 0
  for i in range(60):
    res += ones[i] * (N - ones[i]) * ((2 ** i) % MOD)
    res %= MOD
  print(res)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

sankaNum, scoreMax, ansCnt = map(int, input().split())

score = []

for i in range(sankaNum):
    score.append(scoreMax)

for n in range(ansCnt):
    ansSanka = input()

    for k in range(sankaNum):
        if int(ansSanka) - 1 != k:
            score[k] -=  1
    
for m in range(sankaNum):

    if score[m]  > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

sankaNum, scoreMax, ansCnt = map(int, input().split())

score = [scoreMax-ansCnt]*sankaNum

for _ in range(ansCnt):
    score[int(input()) - 1] +=  1

for m in range(sankaNum):

    if  score[m] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())

s = []
for _ in range(N):
  t = sorted(list(str(input())))
  s.append(''.join(t))          

cnt = 0
for i in range(N):
    for j in range(i + 1, N):
      if s[i] == s[j]:
        cnt += 1

print(cnt)

### FIXED CODE ###

import math
from collections import Counter

N = int(input())

s = []
for _ in range(N):
  s.append(''.join(sorted(str(input()))))
  
c = Counter(s) 

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

cnt = 0  
for i in c.values():
  if i >= 2:
    cnt += combinations_count(i, 2)

print(cnt)
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))

i=0
j=0
k=0
ta=0
rb=0
tc=0
cnt=0
for i in range(0,len(l)-2):

    for j in range(i+1,len(l)-1):

        for k in range(j+1,len(l)):
            if l[i] < l[j]+l[k] and l[j]<l[i]+l[k] and l[k]<l[i]+l[j]:
                cnt+=1
print(cnt)



### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int, input().split()))

i=1
j=0
k=0
ta=0
rb=0
tc=0
cnt=0
m=0
ls=sorted(l)



for i in range(0,len(ls)-2):

    for j in range(i+1,len(ls)-1):
        l1 = ls[i]
        l2 = ls[j]
        ll= l1+l2
        # mid = 0
        k = bisect.bisect_left(ls,ll) - 1

        cnt+=k-j
print(cnt)
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
p = 10**9+7
A = [list(format(a, '060b')) for a in A]
s = 0
for i in range(60):
    Ai = [a[i] for a in A]
    c0 = Ai.count('0')
    c1 = n-c0
    c = c0*c1
    s = (s+c*(2**(59-i))) % p
print(s)


### FIXED CODE ###

N=int(input())
A=[format(i,'060b') for i in map(int,input().split())]
ans=0
mod=10**9+7
for k in range(60):
    count=[a[60-1-k] for a in A].count('0')
    ans+=count*(N-count)*(2**k)%mod
print(ans%mod)
### BUGGY CODE ###

import sys
import numpy as np

N = int(sys.stdin.readline())

dp = np.zeros((N+1, N+1))
ans = np.zeros((N+1, N+1, N+1))

def gcd(a, b):
    if a < b:
        a, b = b, a
    
    if dp[a][b] != 0:
        return dp[a][b]

    while b>0:
        a, b = b, a % b
    
    dp[a][b] = a
    return a

for i in range(1,N+1):
    for j in range(1,N+1):
        temp = gcd(i, j)
        for k in range(1,N+1):
            ans[i][j][k] = gcd(temp, k)
            
print(int(ans.sum()))

### FIXED CODE ###

import sys
import numpy as np

from math import gcd

N = int(sys.stdin.readline())
ans = 0
"""
dp = np.zeros((N+1, N+1))
def gcd(a, b):
    if a < b:
        a, b = b, a
    
    if dp[a][b] != 0:
        return dp[a][b]

    while b>0:
        a, b = b, a % b
    
    dp[a][b] = a
    return a
"""
for i in range(1,N+1):
    for j in range(1,N+1):
        temp = gcd(i, j)
        for k in range(1,N+1):
            ans += gcd(temp, k)
            
print(ans)