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

#!/usr/bin/env python3
 
import sys
import math
# 以下を記述しないとTLEになる, 何故？
# ---- ここまで -----------------------

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        sys.exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)


### FIXED CODE ###

import bisect
s=input()
t=input()
s_set=set([i for i in s])
t_set=set([i for i in t])
if t_set-s_set&t_set:
  print(-1)
  exit()
a={}
for i in t_set:
  a[i]=[]
  for k,j in enumerate(s):
    if j==i:
      a[i].append(k)
  a[i].sort()
ans=0
j=0
for i in t:
  if a[i][-1]<j:
    ans+=len(s)
    j=0
  k=bisect.bisect_left(a[i],j)
  j=a[i][k]+1
print(ans+j)
### BUGGY CODE ###

import sys

def main():
    lines = sys.stdin.readlines()
    n = int(lines[0])

    repo = []
    for i in range(1, n + 1):
        command, acgt = lines[i].split()
        if command[0] == 'i':
            if acgt not in repo:
                repo.append(acgt)
        elif command[0] == 'f':
            if acgt in repo:
                print('yes')
            else:
                print('no')
    return


main()


### FIXED CODE ###

import sys

def main():
    lines = sys.stdin.readlines()
    n = int(lines[0])

    repo = {}
    for i in range(1, n + 1):
        command, acgt = lines[i].split()
        if command[0] == 'i':
            if acgt not in repo:
                repo[acgt] = 0
        elif command[0] == 'f':
            if acgt in repo:
                print('yes')
            else:
                print('no')
    return


main()
### BUGGY CODE ###

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

dictS={}
dictS[0]=1

for n in range (1,N):
    if n<K:
        # S.append(A[n]*S[-1])
        dictS[n]=A[n]*dictS[n-1]

    else:
        # S.append(A[n]*S[-1]/A[n-K])
        dictS[n]=A[n]*dictS[n-1]/A[n-K]

for i in range (K,N):
    if dictS[i]>dictS[i-1]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range (K,N):
    if A[i]>A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

N, K=map(int, input().split())
HP=sorted(list(map(int, input().split())), reverse=True)

for i in range(K):
    if len(HP) > 0:
        HP.pop(0)

print(sum(HP))

### FIXED CODE ###

#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

N, K=map(int, input().split())
HP=sorted(list(map(int, input().split())), reverse=True)
cnt = 0
for i in range(N):
    if K > 0:
        K -= 1
        continue
    cnt += HP[i]

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

import math
import numpy as np

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [False] * (n+1)
    for i in range(3,n+1,2):
        if i < n and i >2:
            solve[i] = is_prime[i] and is_prime[int((i+1)/2)]

    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10**5 
is_prime = primes(L)
solve = like2017(is_prime,L)
# solve = np.ndarray(solve)
for l, r in LR:
    print(sum(solve[l:r+1]))


### FIXED CODE ###

import math
from itertools import accumulate

Q = int(input())
LR = []

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    # print(int(math.sqrt(n)))
    for i in range(2,int(math.sqrt(n))+1):
        for j in range(i*2, n+1 ,i):
            is_prime[j] = False

    return is_prime

def like2017(is_prime,n):
    solve = [0] * (n+1)
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[int((i+1)/2)]:
            solve[i] = 1
        
    return solve

for _ in range(Q):
    t = [int(i) for i in input().split(' ')]
    LR.append(t)

L = 10 ** 5
is_prime = primes(L)
solve = like2017(is_prime,L)
# print(solve)
ans = list(accumulate(solve))
# print(ans)

for l, r in LR:
    print(ans[r] - ans[l-1])
### BUGGY CODE ###

# A - Zero-Sum Ranges
import numpy as np

N = int(input())
A = list(map(int, input().split()))
S = np.zeros(N)
ans = 0

for j in range(N):
    for i in range(N-j):
        S[i] += A[i+j]
        ans += int(S[i]==0)

print(ans)

### FIXED CODE ###

# A - Zero-Sum Ranges
import numpy as np

N = int(input())
A = list(map(int, input().split()))
S = np.zeros(N+1)
ans = 0

for i in range(N):
    S[i+1] = S[i] + A[i]

S.sort()
tmp = 1

for i in range(N):
    if S[i]==S[i+1]:
        tmp += 1
    else:
        ans += tmp * (tmp-1) // 2
        tmp = 1
ans += tmp * (tmp-1) // 2

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

from decimal import Decimal, getcontext

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

getcontext().prec = 5000

if Decimal(a)**Decimal(0.5) + Decimal(b)**Decimal(0.5) < Decimal(c)**Decimal(0.5):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a, b, c = map(int, input().split())
d = c-a-b
if d > 0 and d**2 > 4*a*b:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

A,B,N = map(int,input().split())
x = N
a = 0
while x>9*N//10:
  if x%B != 0 and a < A*x//B - A*(x//B):
    a = A*x//B - A*(x//B)
    x -= 1
  else:
    x -= 1
print(a)

### FIXED CODE ###

A,B,N = map(int,input().split())
x = min(N, B-1)
a = A*x//B - A*(x//B)
print(a)
### BUGGY CODE ###

import sys
N,A,B=map(int,input().split())
S=[]
for i in range(N):
  S+=[int(input())] 
count=0
S.sort()
h=[S[0]]
for i in range(N-1):
  if S[i+1]>=S[0]*(B/A):
    h+=[S[i+1]]
  else:
    break

N=len(h)

while True:
  h.sort(reverse=1)
  if h[0]<=0:
    print(count)
    sys.exit()
  if (h[0]/A)%1==0:
    t=int(h[0]/A)
  else:
    t=int(h[0]/A)+1
  h[0]-=A*t
  for i in range(N-1):
    h[i+1]-=B*t
  count+=t
  if h[N-1]<=-A:
    if (h[N-1]/A)%1==0:
      t=-int(h[N-1]/A)
    else:
      t=-int(h[N-1]/A)
    h[N-1]+=t*(A-B)
    for i in range(N):
      h[i]+=t*B
    count-=t

### FIXED CODE ###

import math
N,A,B=map(int,input().split())
S=[]
for i in range(N):
  S+=[int(input())] 
S.sort(reverse=1)
count=0

def Check(T):
  count=0
  for i in range(N):
    a=math.ceil((S[i]-B*T)/(A-B))
    if a>0:
      count+=a
    else:
      break
  if count<=T:
    return 1
  else:
    return 0

L=1
while True:
  if S[0]/B >=2**L:
    L+=1
  else:
    break

T=2**L#checkしたいナンバー。
for l in range(L,0,-1):
  if Check(T)==1:
    T-=2**(l-1)
  elif Check(T)==0:
    T+=2**(l-1)
if Check(T)==0:
  print(T+1)
else:
  print(T)
### BUGGY CODE ###

S = list(input())

a = ''
count = 0
for i in range(0,len(S)):
    for j in range(i,len(S)):
        a += S[j]
        if(int(a) % 2019 == 0):
            count += 1
    a = ''
print(count)

### FIXED CODE ###

S = input()
P =2019
ans = 0
 
count = [0] * P
count[0] = 1
u = 0
for i, s in enumerate(reversed(S)):
    u = (int(s) * pow(10, i, P) + u) % P
    ans += count[u]
    count[u] += 1
print(ans)
### BUGGY CODE ###

S = input()[::-1]
N = len(S)

"""
    例： S = '31415926535'
        S[3:8] = '15926535' が 2019 で割り切れるかどうか？
     <=> S[3:-1] - S[8:-1] が 2019 で割り切れるかどうか
     <=> S[3:-1] % 2019 == S[8:-1] % 2019 か
    よって、2019で割ったときの異なるあまりをそれぞれカウントすればよい
"""

mod_cnts = [0] * 2019
mod_cnts[0] = 1 # 累積和のはじめ
current_cusum, ans = 0, 0
# O(N)
d = 1
# for i in range(N):
for s in S:
    # s = S[i]
    # current_cusum += pow(10, i) * int(s) # 累積和
    current_cusum += d * int(s)
    current_cusum %= 2019
    mod_cnts[current_cusum] += 1

    d *= 10 % 2019

# O(2019)
for cnt in mod_cnts:
    ans += cnt * (cnt - 1) // 2 # n_C_2 2つ選ぶ組み合わせ
 
print(ans)


### FIXED CODE ###

S = input()
N = len(S)

num = [0] * 2019
num[0] = 1
now, ans = 0, 0
_10 = 1

for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % 2019
    _10 *= 10
    _10 %= 2019
    ans += num[now]
    num[now] += 1
 
print(ans)
### BUGGY CODE ###

D,G=map(int,input().split())
p=[0]*D
c=[0]*D
ans=1000000000
for i in range(D):
    p[i],c[i]=map(int,input().split())
for i in range(1<<D):
    s=0
    cnt=0
    P=[0]*D
    for j in range(D):
        if ((i>>j)&1)==1:
            s+=c[j]+(j+1)*p[j]*100
            cnt+=p[j]
            P[j]=1
    while s<G:
        for k in range(D):
            if s>=G:
                break
            if P[D-k-1]==0:
                for l in range(p[D-k-1]-1):
                    if s>=G:
                        break
                    else:
                        s+=(D-k)*100
                        cnt+=1
    if cnt<ans:
        ans=cnt
print(ans)

### FIXED CODE ###

D,G=map(int,input().split())
p=[0]*D
c=[0]*D
ans=1000000000
for i in range(D):
    p[i],c[i]=map(int,input().split())
for i in range(1<<D):
    s=0
    cnt=0
    P=[0]*D
    for j in range(D):
        if ((i>>j)&1)==1:
            s+=c[j]+(j+1)*p[j]*100
            cnt+=p[j]
            P[j]=1
    m=-1
    for k in range(D):
        if m<0:
            if P[D-k-1]==0:
                m=D-k
        else:
            break
    if m>=0:
        for l in range(p[m-1]-1):
            if s<G:
                s+=m*100
                cnt+=1
    if s>=G and cnt<ans:
        ans=cnt
print(ans)
### BUGGY CODE ###

INF = 10**12
maxH = 2 * 10**4 + 10

def solve():
    H, N = map(int, input().split())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [INF] * (maxH+1)
    dp[0] = 0
    for A, B in ABs:
        for h in range(maxH-A+1):
            h2 = h + A
            dp2 = dp[h] + B
            if dp2 < dp[h2]:
                dp[h2] = dp2

    print(min(dp[H:]))


solve()


### FIXED CODE ###

INF = 10**12
maxH = 2 * 10**4 + 10

def solve():
    H, N = map(int, input().split())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [INF] * (maxH+1)
    dp[0] = 0
    for A, B in ABs:
        for h in range(maxH-A+1):
            h2 = h + A
            dp2 = dp[h] + B
            if dp2 < dp[h2]:
                dp[h2] = dp2

    print(min(dp[H:]))


solve()
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%c!=0 and i%d!=0:
        ans+=1
print(ans)



### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())
ans=0
ca=[]
da=[]
cda=[]
minimunc=-(-a//c)
minimund=-(-a//d)
minimuncd=-(-a//((c*d)//fractions.gcd(c,d)))
maximunc=b//c
maximund=b//d
maximuncd=b//((c*d)//fractions.gcd(c,d))
totalc=maximunc-minimunc+1
totald=maximund-minimund+1
totalcd=maximuncd-minimuncd+1

print((b-a+1)-(totalc+totald-totalcd))
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W, K = map(int,input().split())
sth,stw,glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
init_q =[]

from collections import deque

def bfs(init):
    next_q = deque([])
    for i in init:
        next_q.append(i)
        Dist[i[0]][i[1]] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h,w = next_q.popleft()
        for d in direc:
            for sk in range(1,K+1):
                hs, ws = h + d[0]*sk, w + d[1]*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF:
                    next_q.append([hs,ws])
                    Dist[hs][ws] = Dist[h][w] + 1
    return Dist

def main():
    #固定
    init_q.append([sth, stw])

    ret = bfs(init_q)
    print(ret[glh][glw])


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

H, W, K = map(int,input().split())
sth, stw, glh, glw = map(int,input().split())
sth, stw = sth-1, stw-1
glh, glw = glh-1, glw-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Seen = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}

from collections import deque

def bfs(sth, stw, glh, glw):
    next_q = deque([])
    next_q.append((sth,stw,0))
    Seen[sth][stw] = 0

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, c = next_q.popleft()
        for dh, dw in direc:
            for sk in range(1,K+1):
                hs, ws = h + dh*sk, w + dw*sk
                if not (0<=hs<H and 0<=ws<W):
                    break
                if Gmap[hs][ws]=='@':
                    break
                if Seen[hs][ws]==INF:
                    next_q.append((hs,ws,c+1))
                    Seen[hs][ws] = c + 1
                elif Seen[hs][ws]<=c:
                    break
                if hs==glh and ws==glw:
                    return c + 1
    return -1

def main():
    ret = bfs(sth, stw, glh, glw)
    print(ret)

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

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = {}
l = 0
for _ in range(1, n):
    for i, k in enumerate(p[1:]):
        if i+2 in d:continue
        if d[l] in k:
            d.append(i+2)
            con[i+2] = d[l]
    if len(d) > l:
        l += 1
    else:
        break
if len(con) < n-1:
    print('No')
else:
    print('Yes')
    for i in range(n-1):
        print(con[i+2])

### FIXED CODE ###

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
while d:
    l = d.pop(0)
    for k in p[l-1]:
        if con[k-2]==0:
            d.append(k)
            con[k-2] = l
print('Yes')
for i in range(n-1):
    print(con[i])
### BUGGY CODE ###

n,m=map(int,input().split())
t=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=0
    for i in c:
        d+=2**(i-1)
    t.append([a,d])
e=[float("INF")]*(2**n)
e[0]=0
for i,j in t:
    for h in range(2**n):
        e[h|j]=min(i+e[h],e[h|j])
print(e[-1] if e[-1]!=float("INF") else -1)


### FIXED CODE ###

n,m=map(int,input().split())
t=[]
for i in range(m):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    d=0
    for i in c:
        d+=2**(i-1)
    t.append([a,d])
e=[float("INF")]*(2**n)
e[0]=0
for i,j in t:
    for h in range(2**n):
        e[h|j]=min(i+e[h],e[h|j])
print(e[-1] if e[-1]!=float("INF") else -1)
### BUGGY CODE ###

import itertools 
N = int(input())
A = list(map(int,input().split()))
A_comb = list(itertools.combinations(A,2))

tot = 0
for i,j in A_comb:
    cnt = (i*j)%(10**9+7)
    tot = (tot + cnt)%(10**9+7)
    
print(tot)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
A_sum = sum(A[1:])

tot = 0
for i in range(N-1):
    tot += (A[i]*A_sum)%(10**9+7)
    tot = tot%(10**9+7)
    A_sum -= A[i+1]
    
print(tot)
### BUGGY CODE ###

def main():
    n = int(input())
    *A, = map(int, input().split())
    a, b, c = A.count(1), A.count(2), A.count(3)
    DP = [[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for k in range(c+1):
        for j in range(b+c-k+1):
            for i in range(n-j-k+1):
                if i+j+k > 0:
                    DP[i][j][k] += n/(i+j+k)
                if i > 0:
                    DP[i][j][k] += DP[i-1][j][k]*i/(i+j+k)
                if j > 0:
                    DP[i][j][k] += DP[i+1][j-1][k]*j/(i+j+k)
                if k > 0:
                    DP[i][j][k] += DP[i][j+1][k-1]*k/(i+j+k)
    print(DP[a][b][c])


main()


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                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)
print(DP[a][b][c])
### BUGGY CODE ###

n=int(input())
N=[n]
import collections
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0 and i!=1:
      divisors.append(i)
      if i != n // i and n//i!=1:
        divisors.append(n//i)
  return divisors+[n]
t=make_divisors(n)+make_divisors(n-1)
ans=0
for k in t:
  n=N[0]
  while n>=k:
    if n%k==0:
      n//=k
    else:
      n-=k
  if n==1:
    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
N=[n]
import collections
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a
t=prime_factorize(n-1) # n-1の素因数
c = collections.Counter(t)
w=1
for i in c.values():
  w *= 1+i
w-=1
#print(w)
# wはn-1の約数の個数（1以外）

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0 and i!=1:
      divisors.append(i)
      if i != n // i and n//i!=1:
        divisors.append(n//i)
  return divisors
t=make_divisors(n)+[n]

for i in t:
  n=N[0]
  while n%i==0:
    n//=i
  if n%i==1:
    w+=1
print(w)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
indices = []

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        # sub = int(S[N - i] + str(sub))
        sub += int(S[N - i]) * 10 ** (i-1)
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) / 2
print(int(ans))


### FIXED CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)
### BUGGY CODE ###

l,r=map(int,input().split())
t=[]
for i in range(l,r):
    for j in range(i+1,r+1):
        t.append((i*j)%2019)

print(min(t))

### FIXED CODE ###

l,r=map(int,input().split())
minimum=2019
for i in range(l,r):
    for j in range(i+1,r+1):
        tmp=(i*j)%2019
        if minimum>tmp:
            minimum=tmp
        if minimum==0:
            print(0)
            exit()
print(minimum)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(n):
  ans+=i
print(ans)

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)
### 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 ###

#from collections import Counter
#from itertools import combinations
import sys
input = sys.stdin.readline

N = int(input())
S = [sorted(input().rstrip()) for _ in range(N)]
#print(S)

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

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
S={}
for _ in range(N):
  s = ''.join(sorted(input().rstrip()))
  if s in S:
    S[s] += 1
  else:
    S[s] = 1

ans=0
for s in S.values():
  ans += s*(s-1)//2
  
print(ans)
### BUGGY CODE ###

'''
Created on 2020/08/26

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  s=pin()[:-1]
  K=int(pin())
  d=[]
  for i in range(1,len(s)+1):
    for j in range(len(s)-i+1):
      t=s[j:j+i]
      if t not in d:
        d.append(t)
  l=sorted(d)
  print(l[K-1])
  return 
main()

### FIXED CODE ###

'''
Created on 2020/08/26

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  s=pin()[:-1]
  K=int(pin())
  d=[]
  for i in range(1,K+1):
    for j in range(len(s)-i+1):
      d.append(s[j:j+i])
  ans=sorted(list(set(d)))
  print(ans[K-1])
  return
main()

#解説AC
### BUGGY CODE ###

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

mod = 10**9 + 7
d = 1
total = 0
for _ in range(60):
  cnt = 0
  for each in A:
    cnt += (each & d) != 0
  total += cnt * (n-cnt) * d
  total %= mod
  d <<= 1
print(total)


### FIXED CODE ###

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

mod = 10**9 + 7
total = 0
for i in range(60):
  cnt = sum([1 for a in A if (a>>i & 1)])
  total += cnt * (n-cnt) * (1 << i)
  total %= mod
print(total)