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

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [[0]*60 for i in range(N)]
    for i in range(1, N):
        target = targets[N-i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[N-i-1][keta] = ttl_bins[N -
                                             i][keta] + int(target_str[keta])

    ans = 0

    for i in range(N-1):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            keta_int = int(target_str[keta])
            if keta_int == 0:
                ttl_others_1 = ttl_bins[i][keta]
                base = pow(2, 59-keta, MOD)
                ans += (ttl_others_1) * base
            if keta_int == 1:
                ttl_others_0 = (N - i - 1) - ttl_bins[i][keta]
                base = pow(2, 59-keta, MOD)
                ans += (ttl_others_0) * base
            ans = ans % MOD

    print(ans)


main()


### FIXED CODE ###

#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


MOD = 10 ** 9 + 7


def main():
    N = II()
    targets = LI()

    ttl_bins = [0]*60
    for i in range(N):
        target = targets[i]
        target_str = format(target, f"0{60}b")
        for keta in range(60):
            ttl_bins[keta] += int(target_str[keta])

    ans = 0
    for i in range(60):
        ttl = ttl_bins[i] * (N - ttl_bins[i])
        ans += pow(2, 59-i, MOD) * ttl
        ans %= MOD

    print(ans)


main()
### BUGGY CODE ###

a = int(input())
array = list(map(int, input().strip().split()))
out = 0
for i in range(a):
    if array[i] == min(array[0:i+1]):
        out = out + 1
print(out)

### FIXED CODE ###

a = int(input())
array = list(map(int, input().strip().split()))
out = 0
min_num = array[0]
for i in array:
    min_num = min(min_num, i)
    out = out + 1 if i == min_num else out
print(out)
### BUGGY CODE ###

n=int(input())
l=[0]*(n+1)
m=n
for x in range(1,m):
    for y in range(1,m-x):
        for z in range(1,m-x-y):
            value=x*x+y*y+z*z+x*y+y*z+z*x
            if value>n:
                m=x+y+z
                continue
            l[x*x+y*y+z*z+x*y+y*z+z*x-1]+=1
for i in range(n):
    print(l[i])

### FIXED CODE ###

n=int(input())
l=[0]*10**7
s=int(n**0.7)+10
for x in range(1,s):
    for y in range(1,s-x):
        for z in range(1,s-x-y):
            l[x*x+y*y+z*z+x*y+y*z+z*x-1]+=1
for i in range(n):
    print(l[i])
### BUGGY CODE ###

n , x , y = map(int,input().split())
p = [[0 for i in range(j+1)] for j in range(n)]
for i in range(1,n+1):
    for j in range(1,i+1):
        p[i-1][j-1] = min(abs(i-j),abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y))

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += p[j].count(i)
    print(ans)

### FIXED CODE ###

n , x , y = map(int,input().split())
p = [0 for i in range(n)]
for i in range(1,n+1):
    for j in range(1,i+1):
        p[min(abs(i-j),abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y))] += 1
for i in range(1,n):
    print(p[i])
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
list_num = list(map(int, input().split()))
list_num_ar = np.array(list_num)
result = []

for i in range(M):
	a, b = map(int, input().split())
	res_a = list_num_ar[list_num_ar >= b]
	# print(res_a)
	res_b = list_num_ar[list_num_ar < b]
	# print(res_b)

	if a >= res_b.size:
		res_b = np.full(res_b.size, b)
	else:
		res_b = np.sort(res_b)
		res_b[0:a] = b
	# print(res_b)
	tmp = sum(res_b) + sum(res_a)
	result.append(tmp)

	list_num_ar = np.r_[res_a, res_b]
	# print(list_num_ar)

print(int(max(result)))

### FIXED CODE ###

from sys import stdin
 
def main():
    n,m = [int(x) for x in stdin.readline().split()]
    cards = [int(x) for x in stdin.readline().split()]
    cards.sort()
 
    bcs = [tuple(map(int,x.split())) for x in stdin.readlines()]
    bcs.sort(key=lambda x:x[1], reverse=True)
 
    ans = 0
    minIndex = 0
    isFinished = False
 
    for b,c in bcs:
 
        for _ in range(b):
            if minIndex < n and cards[minIndex] < c:
                ans += c
                minIndex += 1
            else:
                isFinished = True
                break
        
        if isFinished:
            break
 
    if minIndex < n:
        ans += sum(cards[minIndex:])
 
    print(ans)
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys, heapq, bisect, math, fractions
from collections import deque

N = int(input())
S = [sorted(sys.stdin.readline().strip()) for _ in range(N)]

res = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            res += 1

print(res)

### FIXED CODE ###

N = int(input())

dic = {}
for i in range(N):
    s = sorted(input())
    ss = "".join(s)
    if ss in dic:
        dic[ss] += 1
    else:
        dic[ss] = 1

res = 0
for d in dic.values():
    res += d * (d - 1) // 2

print(res)
### BUGGY CODE ###

N, T = list(map(int, input().split()))
m = T//N
if T%N==0:
  print(m)
else:
  while m>0 and T%m!=0:
    m -= 1
  print(max(m, 1))
  

### FIXED CODE ###

N, M = list(map(int, input().split(" ")))
def solv(N, M):
    d = M//N
    for i in range(d+1)[::-1]:
        if M%i == 0:
            return i
print(solv(N, M))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
r,c,k = map(int,input().split())
K = defaultdict(int)
for _ in range(k):
    x,y,z= [int(i) for i in input().split()]
    K[(x,y)] = z


dp = [[0]*(c+1) for _ in range(4)]
 
for i in range(1, r+1):
    for j in range(1, c+1):
        v = K[(i, j)]
        dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
        dp[1][j] = max(dp[1][j-1], dp[0][j]+v) if v>0 else dp[1][j-1]
        dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v) if v>0 else dp[2][j-1]
        dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v) if v>0 else dp[3][j-1]
        
print(max(dp[i][-1] for i in range(4)))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
H, W, K = map(int, input().split())
B = {}
for _ in range(K):
    r, c, v = map(int, input().split())
    B[(r, c)] = v

dp = [[0]*(W+1) for _ in range(4)]

for i in range(1, H+1):
    for j in range(1, W+1):
        if (i, j) in B:
            v = B[(i, j)]
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = max(dp[1][j-1], dp[0][j]+v)
            dp[2][j] = max(dp[2][j-1], dp[1][j-1]+v)
            dp[3][j] = max(dp[3][j-1], dp[2][j-1]+v)
        else:
            dp[0][j] = max(dp[0][j-1], dp[0][j], dp[1][j], dp[2][j], dp[3][j])
            dp[1][j] = dp[1][j-1]
            dp[2][j] = dp[2][j-1]
            dp[3][j] = dp[3][j-1]

print(max(dp[i][-1] for i in range(4)))
### BUGGY CODE ###

def main():
    x=int(input())
    ans=abs(x)
    L=[0]
    for i in range(1,10**9):
        P=L[:]
        for l in L:
            P.append(l+i)
            P.append(l-i)
        if x in P:
            print(i)
            break
        L=P[:]
main()

### FIXED CODE ###

def main():
    x=int(input())
    for i in range(1,10**9):
        if x>i*(i+1)//2: continue
        print(i)
        break
main()
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int, input().split()))
def combinations_count(n, r):
  if n == 0 or n == 1:
    return 0
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
C = [0]*n
for i in range(n):
  C[a[i]-1] += 1
for i in range(n):
  ans = sum(combinations_count(a, 2) for a in C)
for i in range(n):
  print(ans -max(0,C[a[i]-1]-1))

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
b=[0]*n
ans=0

for i in range(n):
    b[a[i]-1]+=1
for i in range(n):
    ans+=(b[i]*(b[i]-1))//2
for i in range(n):
    print(ans-b[a[i]-1]+1)
### BUGGY CODE ###

# coding:utf-8                                                                  

import copy

alls = raw_input()
tarx, tary = map(int, raw_input().split())

ss = alls.split("T")

xs = []
ys = []
posx = []
posy = [0]
for i, s in enumerate(ss):
    if i == 0:
        posx.append(len(s))
    elif i % 2 == 0:
        xs.append(len(s))
    else:
        ys.append(len(s))

for x in xs:
    tmpx = []
    for px in posx:
        tmpx.append(px+x)
        tmpx.append(px-x)
    set(tmpx)
    posx = copy.deepcopy(tmpx)

for y in ys:
    tmpy = []
    for py in posy:
        tmpy.append(py+y)
        tmpy.append(py-y)
    set(tmpy)
    posy = copy.deepcopy(tmpy)

if tarx in posx and tary in posy:
    print "Yes"
else:
    print "No"

### FIXED CODE ###

# coding:utf-8                                                                  

alls = raw_input()
tarx, tary = map(int, raw_input().split())

ss = alls.split("T")

xs = []
ys = []
posx = set()
posy = set()
posy.add(0)
for i, s in enumerate(ss):
    if i == 0:
        posx.add(len(s))
    elif i % 2 == 0:
        xs.append(len(s))
    else:
        ys.append(len(s))

for x in xs:
    tmpx = set()
    for px in posx:
        tmpx.add(px+x)
        tmpx.add(px-x)
    posx = tmpx

for y in ys:
    tmpy = set()
    for py in posy:
        tmpy.add(py+y)
        tmpy.add(py-y)
    posy = tmpy

if tarx in posx and tary in posy:
    print "Yes"
else:
    print "No"
### BUGGY CODE ###

import queue
x=int(input())
avail=list(range(100,106))
q=queue.Queue()
ok=[False]*max(x+1,106)
for i in avail:
    q.put(i)
    ok[i]=True
while not q.empty():
    f=q.get()
    for i in avail:
        if(i+f<=x and not ok[i+f]):
            avail.append(i+f)
            q.put(i+f)
            ok[i+f]=True
print(1 if x in avail else 0)

### FIXED CODE ###

import queue
x=int(input())
avail=list(range(100,106))
ok=[False]*max(x+1,106)
q=queue.Queue()
for i in avail:
    ok[i]=True
    q.put(i)
while not q.empty():
    f=q.get()
    for i in range(100,106):
        if(i+f<=x and not ok[i+f]):
            ok[i+f]=True
            q.put(i+f)
print(1 if ok[x] else 0)
### BUGGY CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
def dfs(x0, y0, cnt):
    ans = h * w
    for i, j in [(1, 0), (0, 1)]:
        x = x0 + i
        y = y0 + j
        ret = 0
        if 0 <= x < w and 0 <= y < h:
            if s[y][x] == "#" and s[y0][x0] == ".":
                ret += 1
            if x == w - 1 and y == h - 1:
                return cnt + ret
            ans = min(ans, dfs(x, y, cnt + ret))
    return ans

print(dfs(0, 0, 0 if s[0][0] == "." else 1))

### FIXED CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[h * w] * w for _ in range(h)]
dp[0][0] = 0 if s[0][0] == "." else 1

for x0 in range(w):
    for y0 in range(h):
        for i, j in [(0, 1), (1, 0)]:
            x = x0 + i
            y = y0 + j
            if x < w and y < h:
                n = 1 if s[y0][x0] == "." and s[y][x] == "#" else 0
                dp[y][x] = min(dp[y0][x0] + n, dp[y][x])

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

n=int(input())
l=list(map(int,input().split()))
for i in range(1,n):
    count=0
    for j in range(i,n):
        if i==l[j-1]:
            count+=1
    print(count)
print(0)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
m=[0]*n
for i in l:
    m[i-1]+=1
for j in range(n):
    print(m[j])
### BUGGY CODE ###

s = raw_input()
t = raw_input()
n = int(raw_input())
q = []
for i in range(n):
    abcd = map(int, raw_input().split())
    q.append(abcd)

def shorten(s):
    if s[0] != s[1]:
        return s[2:]
    elif s[1] != s[2]:
        return s[0] + s[3:]
    return s[3:]

def check(s):
    sc = [s]
    while len(s) >= 3:
        if s in visited:
            s = visited[s]
            break
        s = shorten(s)
        sc.append(s)

    if len(s) == 2:
        if s == 'AA':
            s = 'B'
        elif s == 'BB':
            s = 'A'
        else:
            s = ''

    for sci in sc:
        visited[sci] = s

    return s

visited = {}
for a,b,c,d in q:
    si = check(s[a-1:b])
    ti = check(t[c-1:d])

    if si == ti:
        print 'YES'
    else:
        print 'NO'


### FIXED CODE ###

S = raw_input()
T = raw_input()
n = int(raw_input())
q = []
for i in range(n):
    abcd = map(int, raw_input().split())
    q.append(abcd)

toi = lambda c: 1 if c == 'A' else 2
s = [0] * (len(S)+1)
for i in range(len(S)):
    s[i+1] = s[i] + toi(S[i])

t = [0] * (len(T)+1)
for i in range(len(T)):
    t[i+1] = t[i] + toi(T[i])

for a,b,c,d in q:
    si = (s[b] - s[a-1]) % 3
    ti = (t[d] - t[c-1]) % 3
    if si == ti:
        print 'YES'
    else:
        print 'NO'
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)
ans = 0
st = set()
for i in a:
  x,y = divmod(i-1,n)
  ans += ls[i-1]
  st.add(i-1)
  q = deque([i-1])
  while q:
    j = q.popleft()
    px,py = divmod(j,n)
    for nx,ny in (px-1,py),(px+1,py),(px,py+1),(px,py-1):
      if 0 <= nx < n and 0 <= ny < n:
        k = nx*n+ny
        if j in st:
          if ls[j] < ls[k]:
            ls[k] = ls[j]
            q.append(k)
        elif ls[j]+1 < ls[k]:
          ls[k] = ls[j]+1
          q.append(k)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = [0]*(n*n)
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st[i]=1
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if st[j]:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
S = [input() for i in range(N)]
input_dict = defaultdict(int)
for key in S:
    input_dict[key] += 1
max_list = [kv for kv in input_dict.items() if kv[1] == max(input_dict.values())]
max_list.sort()
for i in range(len(max_list)):
    print(max_list[i][0])

### FIXED CODE ###

from collections import defaultdict
N = int(input())
S = [input() for i in range(N)]
input_dict = defaultdict(int)
for key in S:
    input_dict[key] += 1
max_value = max(input_dict.values())
max_list = []
for k, v in input_dict.items():
    if v == max_value:
        max_list.append(k)
max_list.sort()
[print(i) for i in max_list]
### BUGGY CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
b=1
for i in a:
  b=b//gcd(b,i)*i
ans=0
for i in a:
  ans+=(b//i)
print(ans%(10**9+7))

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
b=1
for i in a:
  b=b//gcd(b,i)*i
ans=0
for i in a:
  ans+=(b//i)
print(ans%(10**9+7))
### BUGGY CODE ###

N,A,B,C=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 2*N):
	fact_tmp *= i
	fact_tmp %= mod
	fact.append(fact_tmp)
	inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


P=0
for g in range(N, 2*N):
	P+=100**(2*N-1-g) * g*(A**N)*(B**(g-N))*ncr(g-1,(N-1))
	P%=mod
	P+=100**(2*N-1-g) * g*(A**(g-N))*(B**N)*ncr(g-1,(N-1))
	P%=mod

Q=pow( 100 , 2*N-1 ,mod)

if C>0: P,Q=Q,P
print ( P*pow(Q, mod-2 , mod) ) % mod

### FIXED CODE ###

N,A,B,C=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, 2*N):
	fact_tmp *= i
	fact_tmp %= mod
	fact.append(fact_tmp)
	inv_fact.append(pow(fact_tmp, mod-2, mod))
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


P=0
for g in range(N, 2*N):
	P+=pow( A+B , (2*N-1-g) , mod) * g*pow(A,N,mod)* pow(B,g-N,mod) *ncr(g-1,(N-1))
	P%=mod
	P+=pow( A+B , (2*N-1-g) ,mod) * g*pow(A,g-N,mod) * pow(B,N,mod) *ncr(g-1,(N-1))
	P%=mod

Q=pow( A+B , 2*N-1,mod) 

hikiwake=100*pow(100-C,mod-2, mod) 
print ( P*pow(Q, mod-2 , mod) *hikiwake )%mod
### BUGGY CODE ###

N = int(input())
a=list(map(int, input().split()))
Q = int(input())
num_a =[0]*100001
b=[]
c=[]
for i in range(Q):
  b1,c1=map(int, input().split())
  b.append(b1)
  c.append(c1)
for i in range(Q):
  if b[i] not in a:
    continue
  elif num_a[b[i]]>0:
    continue
  else:
    num_a[b[i]] = a.count(b[i])
num_b = []
sum_a = sum(a)
for i in range(Q):
  if num_a[b[i]]==0:
    num_b.append(0)
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  else:
    num_b.append(num_a[b[i]])
    num_a[c[i]] += num_a[b[i]]
    num_a[b[i]] = 0
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  print(sum_a)

### FIXED CODE ###

N = int(input())
a=list(map(int, input().split()))
Q = int(input())
num_a =[0]*100001
num_b = []
sum_a = sum(a)
b=[]
c=[]
for i in a:
  num_a[i]+= 1
for i in range(Q):
  b1,c1=map(int, input().split())
  b.append(b1)
  c.append(c1)
for i in range(Q):
  if num_a[b[i]]==0:
    num_b.append(0)
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  else:
    num_b.append(num_a[b[i]])
    num_a[c[i]] += num_a[b[i]]
    num_a[b[i]] = 0
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  print(sum_a)
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
s = []
t = [0]*1010
u = []
for i in range(2,1010):
    x = 1
    for j in range(2,i):
        if(i%j == 0):
            x = 0
            break
    if(x == 1):
        u.append(i)
m = len(u)
for i in range(n):
    for j in range(m):
        if(a[i]%u[j] == 0):
            t[j] += 1
            a[i] //= u[j]
            if(a[i] == 1):
                break
    if(a[i] != 1):
        s.append(a[i])
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    z = 0
    for i in range(1,len(s)):
        for j in range(i):
            if(math.gcd(s[i],s[j]) > 1):
                z = 1
                break
    if(z == 1):
        print('setwise coprime')
    else:
        print('pairwise coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    if(s[i] == []):
        for j in range(1,-(-r//i)):
            s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

n, c, k = map(int, input().split())
l = sorted([int(input()) for i in range(n)])
count = 0
while len(l) > 0:
    check = l[0] + k
    pas = 0
    for i in range(len(l)):
        if (l[i] <= check) and (pas < c):
            pas += 1
        else:
            break
    l = l[pas:]
    count += 1
print(count)

### FIXED CODE ###

n, c, k = map(int, input().split())
l = sorted([int(input()) for i in range(n)])
count = 1
pas = 0
now = l[0]
for i in range(len(l)):
    check = now + k
    if pas < c and l[i] <= check:
        pas += 1
    else:
        now = l[i]
        pas = 1
        count += 1
print(count)
### BUGGY CODE ###

input=[input().split() for i in range(2)]
length=int(input[0][0])
list=[]
for i in range(length):
    list.append(int(input[1][i]))
ret=0
list.sort()
for i in range(length):
    flg=True
    num=list[i]
    if list.count(num)==1:
        for j in range(i):
            if i!=j and num%list[j]==0:
                flg=False
                break
        if flg:
            ret=ret+1
print(ret)

### FIXED CODE ###

import numpy as np
from collections import Counter

length=int(input())
list=list(map(int,input().split()))
list.sort()

max=list[-1]
dp=[0]*(max+1)
dp=np.array(dp,int)

for num in list:
    dp[num]=1

for num in list:
    if dp[num]==1:
        dp[2*num::num]=0

count=Counter(list)

for num,cnt in count.items():
    if cnt>1:
        dp[num]=0

print(dp.sum())
### BUGGY CODE ###

s = input()
m = [0 for _ in range(2019)]
m[0] = 1
for i in range(len(s)):
    t = int(s[i:])
    m[t % 2019] += 1
print(sum([int(x * (x - 1) / 2) for x in m if x > 1]))


### FIXED CODE ###

s = input()
s = s[::-1]
n = len(s)
m = [0] * 2019
m[0] = 1
a = 0
d = 1
for i in range(n):
    a = (a + int(s[i]) * d) % 2019
    d = (d * 10) % 2019
    m[a] += 1
print(sum([int(x * (x - 1) / 2) for x in m if x > 1]))
### BUGGY CODE ###

def main():
    def check(m):
        DP = [False]*(k+1)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            for j in reversed(range(k+1-a[i])):
                DP[a[i]+j] = DP[a[i]+j] or DP[j]
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()

### FIXED CODE ###

import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()
### BUGGY CODE ###

N=int(input())
A=[int(i) for i in input().split()]
D={}
x=0
for a in A:
	if a in D.keys():
		D[a]=D[a]+1
	else:
		D[a]=1

for i in range(len(A)):
	if D[A[i]]>1:
		D[A[i]]=D[A[i]]-1
	else:
		D.pop(A[i])
	x=0
	lis=list(D.keys())
	for j in range(len(D.keys())):
		y=D[lis[j]]
		x+=int((y**2-y)/2)
	print(x)
	if A[i] in D.keys():
		D[A[i]]=D[A[i]]+1
	else:
		D[A[i]]=1

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
D={}
x=0
lis=[]
for a in A:
	try:
		D[a]=D[a]+((D[a]*2)**0.5//1)+1
	except:
		D[a]=0

z=sum(D.values())
for i in range(len(A)):
	x=0
	y=((D[A[i]]*2)**0.5)//1
	x=x+z-y
	print(int(x))
### BUGGY CODE ###

n=int(input())
for a in range(n//2,3501):
 for b in range(n//2,3501):
  if 4*a*b-n*b-a*n==0:
   continue
  c=(n*a*b)/(4*a*b-n*b-a*n)
  if c==int(c) and c>=1:
    print(a,b,int(c))
    exit()

### FIXED CODE ###

n=int(input())
for a in range(n//4+1,3501):
 for b in range((n*a)//(4*a-n),3501):
  if 4*a*b-n*b-a*n==0:
   continue
  c=(n*a*b)/(4*a*b-n*b-a*n)
  if c==int(c) and c>=1:
    print(a,b,int(c))
    exit()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Xor Sum 4
https://atcoder.jp/contests/abc147/tasks/abc147_d

"""
import sys


def solve(N, A):
    MOD = 10**9 + 7
    bit_len = max(map(int.bit_length, A))
    ans = 0
    for i in range(bit_len):
        zeros, ones = 0, 0
        for a in A:
            if (a & 1<<i):
                ones += 1
            else:
                zeros += 1
        ans = (ans + (ones * zeros * 2**i)) % MOD
    return ans % MOD


def main(args):
    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Xor Sum 4
https://atcoder.jp/contests/abc147/tasks/abc147_d

"""
import sys


def solve(N, A):
    MOD = 10**9 + 7
    bit_len = max(map(int.bit_length, A))
    ans = 0
    for i in range(bit_len):
        zeros, ones = 0, 0
        for a in A:
            if (a & 1<<i):
                ones += 1
            else:
                zeros += 1
        ans = (ans + (ones * zeros * 2**i)) % MOD
    return ans % MOD


def main(args):
    N = int(input())
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])