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

n=int(input())

import math
def num_divisors_trial_division(n):
    num = 0
    for i in range(1, int(math.sqrt(n) + 1e-9) + 1):
        if n % i == 0:
            num += 1
            if n != i**2:
                num += 1
    
    return num

result = 0
for ab in range(1,n):
  tmp = num_divisors_trial_division(ab)
  result += tmp
print(result)

### FIXED CODE ###

n=int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

tmp = num_divisors_table(n-1)
print(sum(tmp))
### BUGGY CODE ###

#!/usr/bin/env python
import numpy as np

def main():
    N = int(input().strip())
    arr = np.zeros(N, np.int32)
    for i in range(N):
        arr[i] = int(input().strip())
    for i in range(N):
        if i == 0:
            tmp = arr[i]
            arr[i] = 0
            print(arr.max())

        else:
            arr[i-1] = tmp
            tmp = arr[i]
            arr[i] = 0
            print(arr.max())

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
import numpy as np

def main():
    N = int(input().strip())
    arr = np.zeros(N, np.int32)
    for i in range(N):
        arr[i] = int(input().strip())
    arr2 = np.sort(arr)[::-1]
    max1, max2 = arr2[0], arr2[1]

    for i in range(N):
        print(max1) if arr[i] != max1 else print(max2)

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

def solve(s):
    k = 10 ** 9
    if s <= k:
        return 0, 0, 1, 0, 0, s
    X = k
    while True:
        Y = (s - 1) // X + 1
        while Y <= k:
            xy = X * Y - s
            lim = min(Y, int(xy ** 0.5))
            for y in range(1, lim + 1):
                x, m = divmod(xy, y)
                if x <= X and m == 0:
                    return 0, 0, X, y, x, Y
            Y += 1
        X -= 1


s = int(input())
print(*solve(s))


### FIXED CODE ###

def solve(s):
    k = 10 ** 9
    if s <= k:
        return 0, 0, 1, 0, 0, s
    X = k
    while True:
        Y = (s - 1) // X + 1
        while Y <= k:
            xy = X * Y - s
            if xy == 0:
                return 0, 0, X, 0, 0, Y
            lim = min(Y, int(xy ** 0.5))
            for y in range(1, lim + 1):
                x, m = divmod(xy, y)
                if x <= X and m == 0:
                    return 0, 0, X, y, x, Y
            Y += 1
        X -= 1


s = int(input())
print(*solve(s))
### BUGGY CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]


N, M = [int(x) for x in input().split()]
S = [int(x) for x in input().split()]
T = [int(x) for x in input().split()]

DP = [[0] * (M + 1) for _ in range(N + 1)]
DP[0][0] = 1
for n in range(N + 1):
    for m in range(M + 1):
        if n > 0 and m > 0 and S[n - 1] == T[m - 1]:
            for nn in range(n):
                for mm in range(m):
                    DP[n][m] += DP[nn][mm]

print(sum(sum(DP, [])) % MOD)


### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle

# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

def main():
    """"ここに今までのコード"""
    N, M = [int(x) for x in input().split()]
    S = [int(x) for x in input().split()]
    T = [int(x) for x in input().split()]

    DP = [[0] * (M + 1) for _ in range(N + 1)]
    DP[0] = [1] * (M + 1)
    for n in range(1, N + 1):
        DP[n][0] = DP[n - 1][0]
        for m in range(1, M + 1):
            DP[n][m] = DP[n][m - 1] + DP[n - 1][m] - DP[n - 1][m - 1]
            DP[n][m] %= MOD
            if S[n - 1] == T[m - 1]:
                DP[n][m] += DP[n - 1][m - 1]
                DP[n][m] %= MOD
    print(DP[n][m])


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

import numpy as np

N, K, Q = map(int, input().split())
A_list = []
i = 0
while i < Q:
  A_list.append(int(input()))
  i += 1

N_list = np.array([K] * N)

for idx, A in enumerate(A_list):
  minus_list = np.array([-1] * N)
  minus_list[A-1] += 1
  N_list = N_list + minus_list

for N in N_list:
  if N <= 0:
    print("No")
  else:
    print("Yes")
    

### FIXED CODE ###

import numpy as np

N, K, Q = map(int, input().split())
A_list = np.array([0] * N)
i = 0
while i < Q:
  A_list[int(input()) - 1] += 1
  i += 1

N_list = np.array([K] * N)
N_list = N_list + A_list - Q

for N in N_list:
  if N <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

import numpy as np
import itertools

N, M = map(int, input().split())
lists = []
for i in range(N):
    li =list(map(int, input().split()))
    lists.extend(li)
    li.clear()
    
Mat = np.reshape(lists, (N, 3))

X = 0
Y = 0
Z = 0
V = -np.inf

L = range(1, N+1)
for C in itertools.combinations(L, M):
    for j in C:
        X += Mat[j-1, 0]
    for j in C:
        Y += Mat[j-1, 1]
    for j in C:
        Z += Mat[j-1, 2]
    if abs(X) + abs(Y) + abs(Z) > V:
        V = abs(X) + abs(Y) + abs(Z)
    X = 0
    Y = 0
    Z = 0

print(V)

### FIXED CODE ###

from itertools import product

N, M = map(int, input().split())
L = [[] for _ in range(N)]

for i in range(N):
  x, y, z = map(int, input().split())
  L[i] += [x, y, z]

ans = 0

for pm in product([-1, 1], repeat=3):
  temp = []
  for l in L:
    temp.append(pm[0]*l[0] + pm[1]*l[1] + pm[2]*l[2])
  temp.sort(reverse = True)
  ans = max(ans, sum(temp[:M]))

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

N, Q = map(int, input().split())
c = list(map(int, input().split()))
q = []
for k in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  q.append([l, r, k])

q.sort(key = lambda x: x[1])
ans = [0 for k in range(Q)]
color = [[] for _ in range(N)]

for k in range(N):
  color[c[k]-1].append(k)

good = [0 for _ in range(N)]
lastapp = [-1 for _ in range(N)]
end = -1

for k in range(Q):
  l = q[k][0]
  r = q[k][1]
  a = q[k][2]
  for j in range(r, end, -1):
    if lastapp[c[j]-1] == -1:
      lastapp[c[j]-1] = j
      good[j] = 1
    elif lastapp[c[j]-1] < j:
      good[lastapp[c[j]-1]] = 0
      good[j] = 1
      lastapp[c[j]-1] = j
  ans[a] = sum(good[l:r+1])
  end = r
  
for k in range(Q):
  print(ans[k])

### FIXED CODE ###

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    # 1-index
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, Q = map(int, input().split())
c = list(map(int, input().split()))
q = []
for k in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  q.append([l, r, k])


q.sort(key = lambda x: x[1])
ans = [0 for k in range(Q)]


good = BIT(N)
lastapp = [-1 for _ in range(N)]
end = -1
for k in range(Q):
  l = q[k][0]
  r = q[k][1]
  a = q[k][2]
  for j in range(r, end, -1):
    if lastapp[c[j]-1] == -1:
      lastapp[c[j]-1] = j
      good.add(j+1, 1)
    elif lastapp[c[j]-1] < j:
      good.add(lastapp[c[j]-1]+1, -1)
      good.add(j+1, 1)
      lastapp[c[j]-1] = j
  ans[a] = good.sum(r+1) - good.sum(l)
  end = r
  
for k in range(Q):
  print(ans[k])
### BUGGY CODE ###

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

counter=0
for i in range(N):
  Pj_list=[]
  for j in range(i+1):
    Pj_list.append(List[j])
  Mi=min(Pj_list)
  if Mi==List[i]:
    counter+=1
print(counter)

### FIXED CODE ###

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

counter=0
mj=N
for i in range(N):
  if mj>List[i]:
    mj=List[i]
  if List[i]==mj:
    counter+=1
print(counter)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの最小値を変更する関数
def chmin(a, b):
    if a > b:
        return b
    else:
        return a

# 無限大の値
f_inf = float('inf')

# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)

# 初期条件
dp[0] = 0

# 足場 i-1 から足場 i へと移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
# 足場 i-j から足場 i へと移動する。コストは |h[i]−h[i-j]|
for i in range(1, n):
    # i-kが負の場合は、スタートはh[0]になる。
    start = max(0, i-k)
    if start == 0:
        dp[i] = abs(h[i]-h[0])
    else:
        for j in range(1, k+1):
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[n-1])



### FIXED CODE ###

import sys
import numpy as np

input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

dp = np.zeros(n, dtype=int)
h = np.array(h)


for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

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

ans = 0
for i in range(61):
  n = sum([int(bin(a>>i)[-1]) for a in A])
  ans += n * (N - n) * (2 ** i)
print(ans%MOD)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

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

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())

ans = h + w

def bfs(cur, pre, cnt):
    global ans
    stack = deque([[cur, pre, cnt]])
    while stack:
        cur, pre, cnt = stack.popleft()
        r, c = cur
        col = s[r][c]
        if col != pre:
            cnt += 1
        if r == h-1 and c == w-1:
            ans = min(ans, cnt)
        next = [[r+1, c], [r, c+1]]
        for r2, c2 in next:
            if r2 < h and c2 < w:
                stack.append([[r2, c2], col, cnt])

bfs([0, 0], '.', 0)

print((ans+1)//2)


### FIXED CODE ###

import sys
from collections import deque
imput = sys.stdin.readline

h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input().rstrip('\n'))

ans = h + w
memo = [[h + w for i in range(w)] for j in range(h)]

def bfs(cur, pre, cnt):
    global ans
    stack = deque([[cur, pre, cnt]])
    while stack:
        cur, pre, cnt = stack.popleft()
        r, c = cur
        col = s[r][c]
        if col != pre:
            cnt += 1
        if memo[r][c] > cnt:
            memo[r][c] = cnt
            if r == h-1 and c == w-1:
                ans = min(ans, cnt)
            next = [[r+1, c], [r, c+1]]
            for r2, c2 in next:
                if r2 < h and c2 < w:
                    stack.append([[r2, c2], col, cnt])

bfs([0, 0], '.', 0)

print((ans+1)//2)
### BUGGY CODE ###

import itertools
H,W,K = map(int,input().split())
S = []
for i in range(H):
  s= map(int,input())
  S.append(list(s))
l = list(itertools.product([0,1], repeat=H-1))
l = [list(li) for li in l]
for i in range(len(l)):
  l[i] = [j+1 for j in range(len(l[i])) if l[i][j] > 0]
  
S_t = [list(x) for x in zip(*S)]
flag = False  
min_cnt = H*W
for i in range(len(l)):
  cnt = 0
  bh = [0]+[li  for li in l[i] if li > 0]+[H]
  white = [0]*(len(bh)-2+1)
  j = 0
  while j < W:
    if flag == True:
      white = [0]*(len(bh)-2+1)
      cnt += 1
      flag = False
    for k in range(len(bh)-1):
      if white[k] + sum(S_t[j][bh[k]:bh[k+1]]) > K:
        flag = True
        break
      white[k] += sum(S_t[j][bh[k]:bh[k+1]])
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)

### FIXED CODE ###

import itertools
H,W,K = map(int,input().split())
S = []
for i in range(H):
  s= map(int,input())
  S.append(list(s))
l = list(itertools.product([0,1], repeat=H-1))
l = [list(li) for li in l]
for i in range(len(l)):
  l[i] = [j+1 for j in range(len(l[i])) if l[i][j] > 0]
  
S_t = [list(x) for x in zip(*S)]
for i in range(W):
  for j in range(1,H):
    S_t[i][j] += S_t[i][j-1]
flag = False  
min_cnt = H*W
for i in range(len(l)):
  cnt = 0
  bh = [0]+[li  for li in l[i] if li > 0]+[H]
  white = [0]*(len(bh)-2+1)
  j = 0
  while j < W:
    if flag == True:
      white = [0]*(len(bh)-2+1)
      cnt += 1
      flag = False
    for k in range(len(bh)-1):
      if bh[k] == 0:
        su = S_t[j][bh[k+1]-1]
      else:
        su = S_t[j][bh[k+1]-1]-S_t[j][max(0,bh[k]-1)]
      if white[k] + su > K:
        if su > K:
          j = W
          cnt = H*W+1
          flag = False
        else:
          flag = True
        break
      white[k] += su
    if flag == False:
      j += 1
  min_cnt = min(cnt+len(bh)-2,min_cnt)
  
print(min_cnt)
### BUGGY CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        waru = 4 * h * n - N * n - N * h
        if waru > 0 and (N * h * n) % waru == 0:
                print("{} {} {}".format(h, n, (N * h * n) // waru))
                exit()

### FIXED CODE ###

N = int(input())
for h in range(1, 3501):
    for n in range(1, 3501):
        waru = 4 * h * n - N * n - N * h
        if waru != 0:
            w = (N * h * n) / waru
            if w > 0 and int(w) / w == 1:
                print("{} {} {}".format(h, n, int(w)))
                exit()
### BUGGY CODE ###

n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
x.sort()
a = []
for i in x:
	if i[0]==1:
		a.append(i[1])
	else:
		break
for j in a:
	if [j,n] in x:
		m = 0
		print("POSSIBLE")
		break
if m != 0:
	print("IMPOSSIBLE")

### FIXED CODE ###

n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
a ,b= [],[]
for i in x:
	if i[0]==1:
		a.append(i[1])
	if i[1]==n:
		b.append(i[0])
if len(a)+len(b) == len(set(a+b)): print("IMPOSSIBLE")
else: print("POSSIBLE")
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

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

lcm = reduce(lambda a,b: a*b//gcd(a,b), A)
ans = 0

for n in map(lambda x: lcm//x, A):
    ans += n
    ans %= mod

print(ans)

### FIXED CODE ###

from functools import reduce

def gcd(x, y):
    if (y==0):return x
    else:return gcd(y, x%y)

N = int(input())
*A, = map(int, input().split())
mod = 10**9 + 7
lcm = reduce(lambda a,b: a*b//gcd(a,b), A)

print(sum(map(lambda x: lcm//x, A))%mod)
### BUGGY CODE ###

def primes(n):
    res = [1]
    a = 2
    while n > 1:
        if n % a == 0:
            res.append(a)
            while n % a == 0:
                n //= a
        a += 1
    return set(res)


if __name__ == '__main__':
    a, b = map(int, input().split(' '))
    print(len(primes(a) & primes(b)))


### FIXED CODE ###

def primes(n):
    res = [1]
    a = 2
    while n > 1 and a < (10**6):
        if n % a == 0:
            res.append(a)
            while n % a == 0:
                n //= a
        a += 1
    if a == 10**6:
        res.append(n)
    return set(res)


if __name__ == '__main__':
    a, b = map(int, input().split(' '))
    print(len(primes(a) & primes(b)))
### BUGGY CODE ###

def bi(l,x,m):
    ok = m
    ng = -1
    while ok - ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

def bi2(l,x,c,m):
    ok = c
    ng = -1
    while ok - ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return l[:ok] + [x] + l[ok:c] + l[c+1:]

n = int(input())
a = [int(input()) for _ in range(n)]
t = [a[0]]
m = 1
for x in a[1:]:
    c = bi(t,x,m)
    if c == m:
        t.append(x)
        m += 1
    else:
        t = bi2(t,x,c,m)
print(m)

### FIXED CODE ###

def bi(l,x):
    ok = len(l)
    ng = -1
    while ok-ng > 1:
        mid = (ng+ok)//2
        if l[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

n = int(input())
a = [int(input()) for _ in range(n)]
t = [-1]
m = 1
for x in a:
    c = bi(t,x) 
    if c == m:
        t.append(x)
        m += 1
    else:
        t[c] = x
print(m)
### BUGGY CODE ###

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

ans = 0
for i in range(1, N+1):
    for j in range(1, N+1):
       if i % j >= K:
           ans += 1

print ans


### FIXED CODE ###

import sys

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

if K == 0:
    print N * N
    sys.exit()

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


print ans
### BUGGY CODE ###

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

start = []
goal = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
    
for i in range(len(start)):
    if start[i] in goal:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

### FIXED CODE ###

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

start = set()
goal = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        start.add(b)
    if b == N:
        goal.add(a)
    
if len(start & goal) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N,M=map(int,input().split());D=[9**9for _ in range(2**N)];D[0]=0
for i in range(M):
 a,_=input().split();s=sum(2**~-int(c)for c in input().split())
 for j in range(2**N):D[s|j]=min(D[s|j],D[j]+int(a))
print(-1*(D[-1]>8**9)or D[-1])

### FIXED CODE ###

N,M=map(int,input().split());D=[0]+[9**9]*(1<<N)
for i in range(M):
 a=int(input().split()[0]);s=sum(1<<~-int(c)for c in input().split())
 for j in range(1<<N):D[s|j]=min(D[s|j],D[j]+a)
print(D[-2]%(9**9)or-1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
L = list(map(int, input().split()))
tri = 0
ran = list(range(N-2))

for i in ran:
    for j in ran:
        for k in range(N-2-i-j):
            if ((L[i] + L[i+j+1]) > L[i+j+k+2]) and ((L[i] + L[i+j+k+2]) > L[i+j+1]) and ((L[i+j+k+2] + L[i+j+1]) > L[i]):
                tri += 1
print(tri)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
L = list(map(int, input().split()))

def main():
    tri = 0
    L.sort()
    for i in range(N-1,-1,-1): #range(初期値,終了条件,変化量)
        mn = 0
        sl = i-1
        while(mn<sl):
            if (L[mn] + L[sl]) > L[i]:
                tri += sl - mn
                sl -= 1
            else:
                mn += 1
    print(tri)
    
main()
### BUGGY CODE ###

s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        x = z[i][1]
        a = z[i][0]
        a_ = ((3*a+x)*(3 ** (x-1))) % (10 ** 9 + 7)
        y = z[i][3]
        c = z[i][2]
        c_ = ((3*c+y)*(3**(y-1)))%(10**9+7)
        ans += (a_*c_)%(10**9+7)
    ans %=(10**9+7)

print(int(ans))

### FIXED CODE ###

s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))
### BUGGY CODE ###

n  = int(input())
m  = 10 ** 9 + 7
l  = 2 ** 64
xs = [int(x) % l for x in input().split()]
r  = 0

for i in range(0, n - 1):
	for j in range(i + 1, n):
		r = (r + (xs[i] ^ xs[j])) % m

print(r)


### FIXED CODE ###

n  = int(input())
m  = 10 ** 9 + 7
xs = [int(x) for x in input().split()]
bs = [0] * 60
b  = 1

for x in xs:
	e = 0
	
	while 0 < x:
		if x % 2 == 1:
			bs[e] += 1
			
		e  += 1
		x //= 2

b = 1
r = 0

for i in range(0, 60):
	r  += ((n - bs[i]) * bs[i]) * b
	b <<= 1
	
print(r % m)
### BUGGY CODE ###

from collections import Counter

N = int(input())
a = list(map(float, input().split()))

dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
c = Counter(a)

# メモ化再帰ではpypy3でもTLEするのでforループを使う
# j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
for k in range(c[3]+1):
    for j in range(c[3]+c[2]-k+1):
        for i in range(N-j-k+1):
            if i+j+k == 0:
                continue
            else:
                tmp = N/(i+j+k)
                if i > 0: # IndexError防止
                    tmp += dp[i-1][j][k]*(i/(i+j+k))
                if j > 0:
                    tmp += dp[i+1][j-1][k]*(j/(i+j+k))
                if k > 0:
                    tmp += dp[i][j+1][k-1]*(k/(i+j+k))
                dp[i][j][k] = tmp

print(dp[c[1]][c[2]][c[3]])

### FIXED CODE ###

def main():
    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

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

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
t = 10**9+7
for i in ln:
    r += k//A[i]
    if r > t:
        r %= t
print(r)

### FIXED CODE ###

from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
print(r%(10**9+7))
### BUGGY CODE ###

n=int(input())
a=[0 for _ in range(n)]
b=[0 for _ in range(n)]
for i in range(n):
    a[i],b[i] = map(int,input().split())	
cnt=0
for i in range(n):
    i=n-1-i
    while (a[i]+cnt)%b[i]!=0:
        cnt+=1
print(cnt)


### FIXED CODE ###

n=int(input())
a=[0 for _ in range(n)]
b=[0 for _ in range(n)]
for i in range(n):
    a[i],b[i] = map(int,input().split())	
cnt=0
for i in range(n):
    i=n-1-i
    if (a[i]+cnt)%b[i]!=0:
        cnt+=b[i]-(a[i]+cnt)%b[i]
print(cnt)
### BUGGY CODE ###

def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (N + 1)
for i in range(1, N + 1):
    fac[i] = (fac[i - 1] * i) % p

ans = 0
for k in range(K + 1):
    ans += M * pow(M - 1, N - k - 1, p) * cmb(N - 1, k, p)
    ans %= p
print(ans)


### FIXED CODE ###

def cmb(n, r, p):
    return (fac[n] * pow(fac[r], p - 2, p) * pow(fac[n - r], p - 2, p)) % p


p = 998244353
N, M, K = map(int, input().split())
fac = [1] * (max(N, M) + 1)
for i in range(1, max(N, M) + 1):
    fac[i] = (fac[i - 1] * i) % p

ans = 0
for k in range(K + 1):
    ans += M * pow(M - 1, N - k - 1, p) * cmb(N - 1, k, p)
    ans %= p
print(ans)