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

from operator import mul
from functools import reduce


def cmb(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


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

A.sort()
n = A[-1]

before_cmb = -1
max_cmb = -1
r = 0
for i in range(N):
    tmp_cmb = cmb(n, A[i])
    if max_cmb < tmp_cmb:
        max_cmb = tmp_cmb
        r = A[i]

    if before_cmb == -1:
        before_cmb = tmp_cmb
    elif before_cmb >= tmp_cmb:
        break

    before_cmb = tmp_cmb
print(n, r)


### FIXED CODE ###

import bisect

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

A.sort()
n = A[-1]
mid = bisect.bisect(A, n/2)

if abs(n/2-A[mid-1]) > abs(n/2-A[mid]):
    print(n, A[mid])
else:
    print(n, A[mid-1])
### BUGGY CODE ###

import sys
f=lambda:map(int,sys.stdin.readline().split())
n,m=f()
l=sorted(f())
s=[]
t=0
for i in range(m):
  b,c=f()
  s+=[c]*b
  t+=b
s.sort(reverse=1)
a=0
for i in range(n):
  if i<t: a+=max(l[i],s[i])
  else: a+=l[i]
print(a)

### FIXED CODE ###

import sys
f=lambda:map(int,sys.stdin.readline().split())
n,m=f()
la=sorted(f())
ll=sorted([list(f()) for _ in range(m)],key=lambda k:-k[1])
ls=[]
t=0
for b,c in ll:
  if t+b>n:
    ls+=[c]*(n-t)
    t=n
    break
  ls+=[c]*b
  t+=b
ls.sort(reverse=1)
a=0
for i in range(n):
  if i<t: a+=max(la[i],ls[i])
  else: a+=la[i]
print(a)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


n=int(input())

s=[]
cnt=[]

for i in range(n):
    tmp=input()
    tmp = ''.join(sorted(tmp))
    
    for j in range(len(s)):
        if tmp==s[j]:
            cnt[j]+=1
            break
    else:
        s.append(tmp)
        cnt.append(1)
ans=0
for c in cnt:
    if(c>1):
        ans+=combinations_count(c, 2)
    
print(ans)


### FIXED CODE ###

def main():
    n=int(input())
    d={}
    for i in range(n):
        tmp = ''.join(sorted(input()))
        
        if tmp in d:
            d[tmp]+=1
        else:
            d[tmp]=1
    ans=0
    for i in d.values():
        ans+=i*(i-1)//2
    print(ans)

main()
### BUGGY CODE ###

import collections
from sys import stdin


def get_result(data):
    S = data[0]
    int_S = int(S)
    mod_all_bit = [0]
    for i in range(len(S)):
        mod_all_bit.append(int_S % (10**(i+1)) % 2019)
    counter = collections.Counter(mod_all_bit)
    ans = 0
    dict_list = counter.items()
    for key, val in dict_list:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin


def get_result(data):
    S = data[0]
    mod_all_bit = [0] * 2019
    mod_all_bit[0] = 1
    # 10**i の mod を漸化式的に事前計算
    # こうすることで計算が効率化できる
    ten_i_mod = [0] * len(S)
    ten_i_mod[0] = 1
    for i in range(len(S)-1):
        ten_i_mod[i+1] = (ten_i_mod[i] * 10) % 2019
    mod = 0
    for i in range(len(S)):
        mod = (mod + ten_i_mod[i] * int(S[-(i+1)])) % 2019
        mod_all_bit[mod] += 1
    ans = 0
    for val in mod_all_bit:
        if val >= 2:
            ans += val * (val-1) * 0.5
    return int(ans)


if __name__ == '__main__':
    data = list(map(str, stdin.readline().rstrip().split(' ')))
    result = get_result(data)
    print(result)
### BUGGY CODE ###

from sys import stdin

n, k = map(int,input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

def solve():
    max_score = -10000000000
    for i in range(len(p)):
        score = 0
        nx = i
        for _ in range(k):
            score = score + c[p[nx]-1]
            nx = p[nx] -1 
            max_score = max(max_score, score)
    
    print(max_score)

solve()

### FIXED CODE ###

from numba import jit

@jit
def solve():
    n, k = map(int,input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    max_score = -10**10

    for i in range(n):
        count = 1
        val = c[i]

        next_i = p[i] -1
        while next_i != i:
            count += 1
            val += c[next_i]
            next_i = p[next_i] - 1
        
        if val > 0:
            loop_num = (k//count -1)
            tmp_score = loop_num * val
            max_score = max(tmp_score, max_score)
            num = k%count+count

        else:
            tmp_score = 0
            num = min(k, count)

        next_i = i
        for _ in range(num):
            next_i = p[next_i] - 1
            tmp_score += c[next_i]
            max_score = max(tmp_score, max_score)
    
    print(max_score)

solve()
### BUGGY CODE ###

s = input()
res = 0
ir_place = s.find('BW')
while ir_place != -1:
    res += 1
    s = s[:ir_place] + 'WB' + s[ir_place+2:]
    ir_place = s.find('BW')
print(res)

### FIXED CODE ###

s = input()
ans = 0
tmp = 0
for c in s:
    if c == 'B':
        tmp += 1
    else:
        ans += tmp
print(ans)
### BUGGY CODE ###

import heapq
def SME(start,end):
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end//2):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None in ANS[i:i+L] :
            while True:
                if ANS[i] :
                    i += 1
                    continue
                else : 
                    ANS[i] = min(Whole[i+1-L:i+1])
                    i += 1
                    break
        else :
            i += L
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.99
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
s=[0]
x=0
for i in a:
    x+=i
    s.append(x)
x=0
for i in range(n+1):
    x+=s[i+1:].count(s[i])
print(x)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
s=[0]
x=0
for i in a:
    x+=i
    s.append(x)
cs=Counter(s).most_common()
x=0
for i,j in cs:
    x+=j*(j-1)//2
print(x)
### BUGGY CODE ###

from decimal import *
N, K = map(int, input().split())

ans = Decimal(0)
if K <= N:
    ans += Decimal(max(N-K+1, 0))/Decimal(N)
thres = N+1
if K <= N:
    thres = K

for i in range(1, thres):
    p = Decimal(1/N)
    score = Decimal(i)
    while score < K:
        score = score * Decimal(2)
        p = p / Decimal(2)
    ans = ans + p

print(ans)



### FIXED CODE ###

from decimal import *
N, K = map(int, input().split())

ans = Decimal(0)
if K <= N:
    ans += Decimal(max(N-K+1, 0))/Decimal(N)
thres = N+1
if K <= N:
    thres = K

for i in range(1, thres):
    p = Decimal(1/N)
    score = Decimal(i)
    while score < K:
        score = score * Decimal(2)
        p = p / Decimal(2)
    ans = ans + p

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

from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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

def solve(val):
    ruiseki = [0] * (n + 1)
    for i in range(n):
        if a[i] >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    bit = BIT(n + 1)
    res = 0
    for i, num in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= (cnt + 1) // 2:
            return True
    return False

ok = 0
ng = 10**9 + 1
cnt = 0
for i in range(n):
    cnt += n - i
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



n =int(input())
a = list(map(int, input().split()))
a_sorted = sorted(a)


def solve(val):
    val = a_sorted[val]
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = n
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(a_sorted[ok])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x = input()

    for _ in range(10 ** 5):
        if "ST" in x:
            x = x.replace("ST", "")
            x = list(x)
            x = "".join(x)
        else:
            break

    print(len(x))


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x = input()

    cnt_S = 0
    cnt_T = 0
    res = 0
    i = 0
    while i < len(x):
        if x[i] == "S":
            cnt_S += 1
            i += 1

        elif x[i] == "T" and cnt_S != 0:
            while i < len(x) and x[i] == "T":
                cnt_T += 1
                i += 1
            res += min(cnt_S, cnt_T) * 2
            cnt_S -= min(cnt_S, cnt_T)
            cnt_T = 0
        else:
            i += 1

    print(len(x) - res)


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

s = str(input())
n = int(input())

for i in range(n):
    q = list(map(str,input().split()))
    if len(q) == 1 and q[0] == "1":
        s = s[::-1]
    elif q[1] == "1":
        s = q[2] + s
    elif q[1] == "2":
        s = s + q[2]


print(s)

### FIXED CODE ###

s = str(input())
n = int(input())

right = ""
left = ""

flag = 0
for i in range(n):
    q = list(map(str,input().split()))
    if len(q) == 1:
        flag = 1 - flag 
    elif q[1] == "1":
        if flag == 0:
            left = q[2] + left
        else:
            right = right + q[2]
    else:
        if flag == 0:
            right = right + q[2]
        else:
            left = q[2] + left


if flag == 0:
    print(left + s + right)
elif flag == 1:
    print(right[::-1] + s[::-1] + left[::-1])
### BUGGY CODE ###

s=input()
t=input()
l=len(s)
sl=[]
tl=[]
slist=[]
tlist=[]
flag=0
for i in range(l):
    if not i in slist:
        si=s[i]
        for j in range(l):
            if s[j]==si:
                slist.append(j)
    if not i in tlist:
        ti=t[i]
        for j in range(l):
            if t[j]==ti:
                tlist.append(j)
    if slist!=tlist:
        flag=1
        break
if flag==1:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

s=input()
t=input()
l=len(s)
sl=[]
tl=[]
slist=[0]*26
tlist=[0]*26
flag=0
sabc=''
tabc=''
for i in range(l):
    sb=not s[i] in sabc
    tb=not t[i] in tabc
    if sb:
        sabc+=s[i]
    else:
        slist[sabc.find(s[i])]+=1
    if tb:
        tabc+=t[i]
    else:
        tlist[tabc.find(t[i])]+=1
    
    if slist!=tlist:
        flag=1
        break
if flag==1:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

from collections import Counter

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

result = []

for m in range(M):
    L, R = map(int, input().split())
    result = result + list(range(L, R+1))

counter = 0
for v in Counter(result).values():
    if v == M:
        counter += 1
    else:
        continue

print(counter)

### FIXED CODE ###

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

for m in range(M):
    L, R = map(int, input().split())
    if m==0:
        l = L
        r = R
    else:
        if l<L:
            l = L
        if R<r:
            r = R

print(len(list(range(l,r+1))))
### BUGGY CODE ###

a,b,x=map(int, input().split())
flag=0
for i in range(a, b+1):
    if i%x==0:
        flag=flag+1

print(flag)


### FIXED CODE ###

a, b, x = [int(x) for x in input().split()]
print(b // x - (a - 1) // x)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 0
for i in range(n):
  k = 1
  if (i + a[i]) < n:
    k= a[i]
  for j in range(i+k,n):
    d = j-i
    h = a[i] + a[j]
    if d == h :
      res += 1

print(res)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
res = 0
ia = []
ja = []
dia={}
dja={}
for i in range(n):
  dia[i+a[i]] = dia.get(i+a[i],0)+1
  dja[i-a[i]] = dja.get(i-a[i],0)+1
ans = 0
for di,nmi in dia.items():
  nmj = dja.get(di,0)
  ans += nmi*nmj

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

import sys
n, k = map(int,input().split())
As = list(map(int, input().split()))
ans = 1
tmp = -1
for i in range(n-k+1):
    for j in range(k):
        ans= ans*As[k+i-j-1]
    if not tmp==-1:
        if tmp<ans:
            print('Yes')
        else:
            print('No')
    tmp = ans
    ans = 1

### FIXED CODE ###

n, k = map(int,input().split())
As = list(map(int, input().split()))
ans = 1
tmp = -1
for i in range(n-k):
    if As[k+i]>As[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from math import factorial

def modpow(a, n, p):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7

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 )

ans = modpow(2, n, mod) - 1
ans -= (cmb(n, a, mod) + cmb(n, b, mod))

print(ans % mod)


### FIXED CODE ###

def cmb(n, r, mod):
    numerator = 1
    # n * (n-1) * ... * (n-r+1)
    for i in range(n-r+1, n+1):
        numerator = (i * numerator) % mod
    denominator = 1
    # r * (r-1) * ... * 1
    for i in range(1, r+1):
        denominator = (i * denominator) % mod
    # y^(mod-2) % mod
    fermat = pow(denominator, mod-2, mod)
    return (numerator * fermat) % mod


n, a, b = map(int, input().split())
mod = 10 ** 9 + 7

ans = pow(2, n, mod) - 1
ans -= (cmb(n, a, mod) + cmb(n, b, mod))

print(ans % mod)
### BUGGY CODE ###

import sys
import math

sys.setrecursionlimit(10**7)

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0 for __ in range(n+1)] for _ in range(s+1)]
dp[0][0] = 1
index = [(0, 0)]
for i in range(n):
    _index = []
    for j, k in index:
        if j+a[i] <= s:
            dp[j+a[i]][k+1] += 1
            _index.append((j+a[i], k+1))
    index = index + _index

ans = 0
for i in range(n+1):
    if dp[s][i] != 0:
        ans += dp[s][i]*2**(n-i)
        ans %= 998244353
print(ans)

### FIXED CODE ###

import sys
import math

sys.setrecursionlimit(10**7)

n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [0 for _ in range(s+1)]
dp[0] = 1
for i in range(n):
    _dp = [0 for _ in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:
            _dp[j+a[i]] += dp[j]
            _dp[j+a[i]] %= 998244353
        _dp[j] += 2*dp[j]
        _dp[j] %= 998244353
    dp = _dp
print(dp[s])
### BUGGY CODE ###

a, b, n = map(int, input().split())
if n < b:
    print((a*n)//b)
else:
    ans = -1
    for x in range(n+1):
        tmp = (a*x)//b - a*(x//b)
        if tmp > ans:
            ans = tmp
        elif tmp < ans:
            break
    print(ans)


### FIXED CODE ###

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

def f(x):
    return (a*x)//b-a*(x//b)

if n < b:
    print(f(n))
else:
    print(f(b-1))
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
#0が進めるところ、1は無理
lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]
#ゴールは9
lis[h-1][w-1] = 9
#print(lis)
#[[0, 0, 1], [1, 0, 0], [0, 0, 9]]

#この問題ではbfsを始める前に、もともと移動可能だったところの数を記録しておく
road = 0
for row in lis:
    for column in row:
        if column != 1:
            road +=1

count = 0
#(開始x,開始y,移動回数)
pos = [[0,0,0]]
que = deque(pos)
while len(pos)>0:
    x,y,depth = pos.pop(0)

    if lis[x][y] == 9:
        count = depth
        break

    #探索済みのところは、1にする
    lis[x][y] = 1

    #遷移先は0or9なので、1以外なら行ける
    if x-1>=0 and lis[x-1][y] != 1:
        pos.append([x-1,y,depth+1])
    if x+1<h and lis[x+1][y] != 1:
        pos.append([x+1,y,depth+1])
    if y-1>=0 and lis[x][y-1] != 1:
        pos.append([x,y-1,depth+1])
    if y+1<w and lis[x][y+1] != 1:
        pos.append([x,y+1,depth+1])

#そもそも行けない
if count == 0:
    print(-1)
#(移動可能マス数) - (移動する道順上のマスの数 ＝ 最短の移動回数＋１）
else:
    print(road-(count+1))

### FIXED CODE ###

h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)
### BUGGY CODE ###

def calcGCD3(a,b,c):
    for i in reversed(range(1,a+1)):
        if a % i == 0 and b % i ==0 and c% i ==0:
            return i
    return 0

def calcGCD2(a,b):
    for i in reversed(range(1,a+1)):
        if a % i == 0 and b % i ==0 :
            return i
    return 0
        
ans = 0
n = int(input())
for k in range(1,n+1):
    for b in range(k+1,n+1):
        for c in range(b+1,n+1):
            gcd = calcGCD3(k,b,c)
            ans += gcd

ans *= 6

tmp = 0

for k in range(1, n+1):
    for b in range(k+1, n+1):
        gcd = calcGCD2(k,b)
        tmp += gcd
        
tmp *= 6

tmp2 = sum(range(1,n+1))

print(ans+tmp+tmp2)

### FIXED CODE ###

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


ans = 0
n = int(input())
for k in range(1, n+1):
    for b in range(k + 1, n + 1):
        for c in range(b + 1, n + 1):
            gcd1 = dcg(k, b)
            gcd2 = dcg(gcd1, c)
            ans += gcd2

ans *= 6

tmp = 0

for k in range(1, n+1):
    for b in range(k+1, n+1):
        gcd = dcg(k,b)
        tmp += gcd
        
tmp *= 6

tmp2 = sum(range(1,n+1))

print(ans+tmp+tmp2)
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

water = set()
sugar = set()

for i in range(F+1):
    for j in range(F+1-A):
        w = (100*A*i) + (100*B*j)
        water.add(w)

for i in range(F+1):
    for j in range(F+1):
        s = (i*C)+(j*D)
        sugar.add(s)

per = -10000
for w in water:
    for s in sugar:
        ws = w+s
        # 砂糖水の質量合計はFg以下 and 砂糖が溶け残らない
        if (0 < ws <= F) and (s <= w*E // 100):
            if s/(ws) > per:
                per = s/(ws)
                ans = ws, s

print(ans[0], ans[1])


### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

water = set()
sugar = set()

for i in range(0, F+1, 100*A):
    for j in range(0, F+1-A, 100*B):
        water.add(i+j)

for i in range(0, F+1, C):
    for j in range(0, F+1-C, D):
        sugar.add(i+j)

per = -1
for w in water:
    for s in sugar:
        ws = w+s
        # 砂糖水の質量合計はFg以下 and 砂糖が溶け残らない
        if 0 < ws <= F and s <= w*E // 100:
            if s/(ws) > per:
                per = s/(ws)
                ans = ws, s

print(ans[0], ans[1])
### BUGGY CODE ###

MOD = 10 ** 9 + 7

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    max_bin_digits = len(bin(max(A))[2:])
    cnts = [0] * max_bin_digits

    for a in A:
        bin_a = bin(a)[2:].zfill(max_bin_digits)
        for i, b in enumerate(bin_a):
            if int(b):
                cnts[-i-1] += 1

    ans = 0
    for i in range(max_bin_digits):
        ans += cnts[i] * (N - cnts[i]) * 2 ** i
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

MOD = 10 ** 9 + 7

def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    max_bin_digits = len(bin(max(A))[2:])
    cnts = [0] * max_bin_digits

    for a in A:
        for i in range(max_bin_digits):
            if 1 << i & a:
                cnts[i] += 1

    ans = 0
    for i in range(max_bin_digits):
        ans += cnts[i] * (N - cnts[i]) * 2 ** i
        ans %= MOD

    print(ans)


if __name__ == "__main__":
    main()