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

#import sys
#input = sys.stdin.readline
def main():
    Q = 10**9+7
    N, M = map( int, input().split())
    S = list( map( int, input().split()))
    T = list( map( int, input().split()))
    dp = [ [0]*(M+1) for _ in range(N+1)]
    memo = [ [0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()


### FIXED CODE ###

#import sys
#input = sys.stdin.readline
def main():
    Q = 10**9+7
    N, M = map( int, input().split())
    S = list( map( int, input().split()))
    T = list( map( int, input().split()))
    dp = [ [0]*(M+1) for _ in range(N+1)]
    memo = [ [0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1]+1)%Q
            else:
                dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j])%Q
    print(dp[N][M]+1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
memo = []
ans = 0
for ai in a:
    if not memo or memo[-1] >= ai:
        memo.append(ai)
    else:
        for i in range(len(memo)):
            if memo[i] < ai:
                memo[i] = ai
                break
print(len(memo))


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
memo = []
ans = 0

def reverse_binary_serch(target, query):
    l = 0
    r = len(target) - 1
    while True:
        if r - l < 2:
            if target[l] < query:
                return l
            else:
                return r
        i = (l + r) // 2
        if target[i] >= query:
            l = i
        else:
            r = i

for ai in a:
    if not memo or memo[-1] >= ai:
        memo.append(ai)
    else:
        index = reverse_binary_serch(memo, ai)
        memo[index] = ai

print(len(memo))
### BUGGY CODE ###

def popcount(n):
    return bin(n).count('1')

N = int(input())
X = input()

X_int = int(X, 2)
pcount_X = popcount(X_int)

for i,bit in enumerate(X):
    mask_list = ['0']*N
    mask_list[i] = '1'
    mask_int = int(''.join(mask_list), 2)
    Xi = X_int ^ mask_int

    pcount_Xi = pcount_X + (-1)**int(bit)
    
    n = Xi
    pcount_n = pcount_Xi
    ans = 0
    while n > 0:
        ans += 1
        n %= pcount_n
        pcount_n = popcount(n)
    print(ans)

### FIXED CODE ###

def popcount(n):
    return bin(n).count('1')


def main():
    N = int(input())
    X = input()

    X_int = int(X, 2)

    pcount_X = popcount(X_int)

    pcount_X_pls1 = pcount_X + 1
    pcount_X_mns1 = pcount_X - 1
    
    X_mod_pcount_X_pls1 = X_int % pcount_X_pls1
    if pcount_X_mns1 != 0:
        X_mod_pcount_X_mns1 = X_int % pcount_X_mns1

    for i,bit in enumerate(X):
        bit = int(bit)
        if bit == 0:
            n = (X_mod_pcount_X_pls1 + pow(2, N-i-1, pcount_X_pls1)) % pcount_X_pls1
        else:
            if pcount_X_mns1 == 0:
                print(0)
                continue
            n = (X_mod_pcount_X_mns1 - pow(2, N-i-1, pcount_X_mns1)) % pcount_X_mns1

        ans = 1
        while n > 0:
            ans += 1
            n %= popcount(n)
        print(ans)
        
main()
### BUGGY CODE ###

import sys
import heapq

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

g = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append(b)
  g[b].append(a)#番号を修正。0スタートに。
#print(g)

INF = float('inf')
reach = [INF for _ in range(N)] #0からの距離を記録。INF未到達。
reach[0] = 0
par = [-1 for _ in range(N)] #親の位置を記録

Q =[]
heapq.heappush(Q, 0)

while Q:
  v = heapq.heappop(Q)
  for i in range(len(g[v])): #点vから行ける点をすべて探索
    u = g[v][i] #今探索している点
    if u == 0: #始点の場合はスルー
      continue
    if reach[v] + 1 >= reach[u]: #vから来たほうが遠い場合には何もしない。
      continue
    reach[u] = reach[v] + 1 #探索中の点の到達を記録。
    par[u] = v
    heapq.heappush(Q, u)

#print(reach,par)
if INF not in reach[1:]:
  print("Yes")
  for i in range(1,N):
    ans = par[i]+1
    print(ans)
else:
  print("No")

### FIXED CODE ###

import sys
import heapq

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

g = [[] for _ in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  a -= 1; b -= 1
  g[a].append(b)
  g[b].append(a)#番号を修正。0スタートに。
#print(g)

INF = float('inf')
reach = [INF for _ in range(N)] #0からの距離を記録。INF未到達。
reach[0] = 0
par = [-1 for _ in range(N)] #親の位置を記録

Q =[]
heapq.heappush(Q, (0,0)) #0からの距離と頂点を入れる。

while Q:
  d,v = heapq.heappop(Q)
  for i in range(len(g[v])): #点vから行ける点をすべて探索
    u = g[v][i] #今探索している点
    #print(v,u)
    if u == 0: #始点の場合はスルー
      continue
    if reach[u] != INF: #到達済みならスキップ
      continue
    reach[u] = d + 1 #探索中の点の到達を記録。
    par[u] = v
    heapq.heappush(Q, (reach[u],u))

#print(reach,par)
if INF not in reach[1:]:
  print("Yes")
  for i in range(1,N):
    ans = par[i]+1
    print(ans)
else:
  print("No")
### BUGGY CODE ###

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

dp = [1e+09]*N
dp[0] = 0
for i in range(1,N):
  for j in range(1,K+1):
    if i >= j: dp[i] = min(dp[i],dp[i-j]+abs(h[i] - h[i-j]))
print(int(dp[-1]))

### FIXED CODE ###

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

dp = [1e+09]*N
dp[0] = 0
for i in range(1,N):
  for j in range(1,K+1):
    if i >= j: dp[i] = min(dp[i],dp[i-j]+abs(h[i] - h[i-j]))
print(int(dp[-1]))
### BUGGY CODE ###

N=int(input())
ls=list(map(int,input().split()))
ls.sort()

#定数倍のやつに＋１する
A=[0]*(max(ls)+1)
for i in range(len(ls)):
  a=1
  while ls[i]*a<=max(ls):
    b=ls[i]*a
    if A[b]<=1:
      A[b]+=1
    a+=1
    
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
ls=list(map(int,input().split()))
ls.sort()

#定数倍のやつに＋１する
M=max(ls)
A=[0]*(M+1)
for i in range(N):
  a=M//ls[i]
  for j in range(1,a+1):
    if A[j*ls[i]]<=2:
      A[j*ls[i]]+=1
    
ans=0     
for i in range(len(ls)):
  if A[ls[i]]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

import copy
n = int(input())
n_list = []
ans = 0
for i in range(1,n+1):
    n_list.append(i)
m_list = copy.copy(n_list)
tmp = m_list.pop(0)
m_list.insert(n-1,tmp)
for i in range(len(n_list)):
    ans += n_list[i] % m_list[i]
print(ans)

### FIXED CODE ###

n = int(input())
ans = (n*(n-1))//2
print(ans)
### BUGGY CODE ###

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


def _condition(i, p):
    for j in range(i):
        if p[i] <= p[j]:
            pass
        else:
            return False
    return True


def _result(p):
    sum = 0
    for i in range(len(p)):
        sum += _condition(i, p)
    return sum


print(_result(p))

### FIXED CODE ###

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


def _result(p):
    sum = 0
    m = p[0]
    for i in range(0, len(p)):
        if p[i] > m:
            pass
        else:
            m = p[i]
            sum += 1
    return sum


print(_result(p))
### BUGGY CODE ###

# ABC 066 C
N = int(input())
A = input().split()

tmp = []
for i,a in enumerate(A):
    if i %2!=0:
        tmp.insert(0,a)
    else:
        tmp.append(a)
if N%2!=0:
    tmp.reverse()
print(' '.join(tmp))

### FIXED CODE ###

# ABC 066 C
N = int(input())
A = input().split()
from collections import deque

tmp = deque([])
for i,a in enumerate(A):
    if i %2!=0:
        tmp.appendleft(a)
    else:
        tmp.append(a)
if N%2!=0:
    tmp.reverse()
print(' '.join(tmp))
### BUGGY CODE ###

ans=1
a=[i for i in range(1,int(input())+1)]
for i in a:
  ans*=i
print(ans%(10**9+7))

### FIXED CODE ###

ans=1
a=[i for i in range(1,int(input())+1)]
for i in a:
  ans*=i
  ans%=10**9+7
print(ans)
### BUGGY CODE ###

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

ans = abs(n - k)

i = False

if n % k == 0:
  ans = 0
  i = True

while not i:
  if ans > abs(ans - k):
    ans = abs(ans - k)
  else:
    i = True

print(ans)

### FIXED CODE ###

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

ans = n % k

i = False

if ans == 0:
  i = True

while not i:
  if ans > abs(ans - k):
    ans = abs(ans - k)
  else:
    i = True

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

n=int(input())
ans=int(0)

for i in range(1,n+1):
    now=int(n/i)
    ans+=int(now*(now+1)/2*i)
print(ans)

### FIXED CODE ###

n=int(input())
ans=int(0)

for i in range(1,n+1):
    now=int(n/i)
    ans+=int(now*(now+1)/2*i)
print(ans)
### BUGGY CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

ans = 0

def check(ind, num, s, left, right):

    if right - left <= 1:
        global ans
        # print(left, right)
        ans = max(ans, left)
        return

    half = (left + right) // 2

    flg = 1

    for j in range(ind + half, num - half + 1):
        for k in range(half):
            if ind + k >= j or j + k >= num:
                break
            if s[ind + k] != s[j + k]:
                break
        else:
            # print(left, half, right, 'eee')
            check(ind, num, s, half, right)
            flg = 0
        # print(left, half, right)

    if flg:
        check(ind, num, s, left, half)

def main():
    global ans
    num = int(input())
    s = list(input())

    for i in range(num):
        if num - i <= ans:
            break
        left, right = ans, num // 2 + 1
        # print(left, right, 'yyy')
        check(i, num, s, left, right)
    print(ans)




if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque


def check(num, s, left, right):

    if right - left <= 1:
        print(left)
        sys.exit()

    half = (left + right) // 2

    data_set = set()

    for i in range(num -2 * half  + 1):
        now_str = s[i:i + half]
        data_set.add(now_str)
        if s[i + half : i + 2 * half] in data_set:
            check(num, s, half, right)
    check(num, s, left, half)

def main():
    num = int(input())
    s = input()

    left, right = 0, num // 2 + 1

    check(num, s, left, right)




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

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
cnt = 0
ans = 0
Hd = sorted(H, reverse=True)


for i in range(N - 1):

    idx = H.index(Hd[i])

    cnt = 0
    if ans > N - i:
        break

    else:
        for j in range(idx, N - 1):

            if H[j] >= H[j + 1]:
                cnt += 1
            else:
                break

    if ans < cnt:
        ans = cnt

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
H = list(map(int, input().split()))
ans = []
cnt = 0
for i in range(N - 1):
    if H[i] >= H[i + 1]:
        cnt += 1
    else:
        ans.append(cnt)
        cnt = 0

ans.append(cnt)
print(max(ans))
### BUGGY CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
for i in range(M):
  t.append(A.count(C[i]))
  temp = A.count(C[i])
  if temp >=2:
    anst += temp*(temp-1)/2

#print(t)
#print(anst)
#print(jisyo[1])
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-t[C.index(A[i])]+1))

### FIXED CODE ###

import math

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

C = list(set(A))
M = len(C)
t = []
anst = 0
dic = {}
for i in A:
  if not i in dic:
    dic[i] = 0
  dic[i] += 1

jisyo = {}
for i in range(M):
  temp = dic[C[i]]
  jisyo[C[i]] = temp
  #t.append(A.count(C[i]))
  if temp >=2:
    anst += temp*(temp-1)/2

#jisyo = dict(zip(C, t))
#print(jisyo)   
for i in range(N):
  #print(t[C.index(A[i])])
  print(int(anst-jisyo[A[i]]+1))
### BUGGY CODE ###

from collections import Counter

input_line=int(input())
count=0
input_list=[]
set_list=set()
while count < input_line:
  input1=input()
  input_list.append(input1)
  set_list.add(input1)
  count+=1
ans_list=[]
#list_set=set(input_list)
max_appeard=Counter(input_list).most_common(1)[0][1]
for item in set_list:
    if Counter(input_list)[item] == max_appeard:
        ans_list.append(item)
ans_list.sort()
for item in ans_list:
  print (item)

### FIXED CODE ###

from collections import defaultdict

H=int(input())
d = defaultdict(int)
for _ in range(H):
    d[input()] += 1
max_appeard=max(d.items(), key=lambda x: x[1])[1]
ans=[k for k,v in d.items() if v == max_appeard]
ans.sort()
for item in ans:
  print (item)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

print(max(a[1:]))
for i in range(1,n-1):
    aa = max(a[0:i])
    ab = max(a[i+1:])
    print(max(aa,ab))
print(max(a[:n]))

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
sortA=sorted(A)
for i in range(N):
    if A[i]!=sortA[-1]:
        print(sortA[-1])
    else:
        print(sortA[-2])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    q = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((0,h,w))
    while q:
        num,h,w = heappop(q)
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and HMANY[h+1][w] > num+1:
                heappush(q, (num+1,h+1,w))
            if w+1 <W and HMANY[h][w+1] > num+1:
                heappush(q,(num+1,h,w+1))
            if 0<=h-1 and HMANY[h-1][w] > num+1:
                heappush(q,(num+1,h-1,w))
            if 0<=w-1 and HMANY[h][w-1] > num+1:
                heappush(q,(num+1,h,w-1))

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    print(ans)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ list(input()) for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    
    # q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                HMANY[h][w] = 0
    for w in range(W):
        for h in range(H-1):
            if HMANY[h][w]+1 < HMANY[h+1][w]:
                HMANY[h+1][w] = HMANY[h][w] + 1
        for h in range(H-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h-1][w]:
                HMANY[h-1][w] = HMANY[h][w] + 1
    
    for h in range(H):
        for w in range(W-1):
            if HMANY[h][w]+1 < HMANY[h][w+1]:
                HMANY[h][w+1] = HMANY[h][w] + 1
        for w in range(W-1, 0, -1):
            if HMANY[h][w]+1 < HMANY[h][w-1]:
                HMANY[h][w-1] = HMANY[h][w] + 1        
    #             q.append((h,w))
    #             A[h][w] = "."
    # ans = 0
    # while q:
    #     nextQ = deque()
    #     for h,w in q:
    #         A[h][w] = "#"
    #         if h+1 <H and A[h+1][w] == ".":
    #             nextQ.append( (h+1,w))
    #         if w+1 <W and A[h][w+1] == ".":
    #             nextQ.append((h,w+1))
    #         if 0<=h-1 and A[h-1][w] == ".":
    #             nextQ.append((h-1,w))
    #         if 0<=w-1 and A[h][w-1] == ".":
    #             nextQ.append((h,w-1))        
    #     ans += 1
    #     q = nextQ
        # num,h,w = q.popleft()        
        # if HMANY[h][w] > num and A[h][w] == ".":
        #     HMANY[h][w] = num
        #     A[h][w] = "#"
        #     if h+1 <H and A[h+1][w] == ".":
        #         q.append( (num+1,h+1,w))
        #     if w+1 <W and A[h][w+1] == ".":
        #         q.append((num+1,h,w+1))
        #     if 0<=h-1 and A[h-1][w] == ".":
        #         q.append((num+1,h-1,w))
        #     if 0<=w-1 and A[h][w-1] == ".":
        #         q.append((num+1,h,w-1))

    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    # print(ans-1)
    print(ans)

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

# -*- coding:utf-8 -*-

n = int(input())
print(n,':',sep='',end=' ')
array = []
count = 0
while True:
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n-1:
            count += 1
            break
    if count == 5:
        break
array.append(n)
for i in range(len(array)):
    print(array[i],end=' ')
print('')

### FIXED CODE ###

# -*- coding:utf-8 -*-

n = int(input())
print(str(n)+':',end='')
array = []
count = 0
while True:
    if n == 999993031:
        break
    for i in range(2,n+1):
        if n%i == 0 and i != n:
            array.append(i)
            n = int(n/i)
            break
        if i == n:
            count += 1
            break
    if count == 24:
        break

array.append(n)
for i in range(len(array)):
    print(' ',array[i],sep = '',end='')
print('')
### BUGGY CODE ###

s = input()[::-1]
 
dp = [[0 for i in range(13)] for j in range(len(s)+1)]
dp[0][0]=1

res = [[x * 10 ** i % 13 for x in range(10)] for i in range(6)]
 
mod = 10 ** 9 + 7
 
for idx, char in enumerate(s):

    if char != "?":
        for i in range(13):
            new_i = (i + res[idx % 6][int(char)]) % 13
            dp[idx+1][new_i] += dp[idx][i]
    else:
        for i in range(13):
            for j in range(10):
                new_i = (i + res[idx % 6][j]) % 13
                dp[idx+1][new_i] += dp[idx][i] % mod
        #dp = [x % mod for x in new_dp]

 
print(dp[-1][5]%mod)



### FIXED CODE ###

s=input()[::-1]

amari=[[(10**i)*x%13 for x in range(10)] for i in range(6)]
dp=[1]+[0]*12
new_dp=[0]*13

mod=10**9+7

for id,char in enumerate(s):
    new_dp=[0]*13
    if char!='?':
        for i in range(13):
            new_i=(i+amari[id%6][int(char)])%13
            new_dp[new_i]+=dp[i]
        dp=new_dp
    else:
        for i in range(13):
            for j in range(10):
                new_i=(i+amari[id%6][j])%13
                new_dp[new_i]+=dp[i]
        dp=[x%mod for x in new_dp]
print(dp[5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())

ab = [[int(x) for x in input().split()] for _ in range(n)]

ab.sort(key=lambda x: x[0])

temp = sum(ab, [])  # 疑似Flatten
a, b = temp[0::2], temp[1::2]

count, index, remainder = 0, 0, 0

for i in range(n):
  if count + b[i] < m:  
    count += b[i]
  else:
    index = i
    remainder = m - count
    
total = a[index] * remainder


total += sum([a[i] * b[i] for i in range(index)])


print(total)


### FIXED CODE ###

# cf. https://rion778.hatenablog.com/entry/2019/03/10/004006
import sys
input = sys.stdin.readline
 
N, M = [int(i) for i in input().split()]
 
plices = [[int(i) for i in input().split()] for _ in range(N)]
 
plices.sort(key = lambda x:x[0])
 
m = 0
cost = 0
 
for i in range(N):
    if m < M:
      buy = min(M - m, plices[i][1])
      cost += plices[i][0] * buy
      m += buy
    else:
      break

print(cost)
### BUGGY CODE ###

n=int(input())
B=[]
for i in range(n):
  x,l=map(int,input().split())
  B.append([x+l,x-l])
B.sort()
Left=[]
for b in B:
  l=b[1];r=b[0]
  flag=1
  for c in Left:
    if (c[0]<l and c[1]>l) or (c[0]<r and c[1]>r):
      flag=0;break   
    elif c[0]>=l and c[1]<=r:
      flag=0;break    
  if flag:
    Left.append([l,r])
print(len(Left))

### FIXED CODE ###

n=int(input())
B=[]
for i in range(n):
  x,l=map(int,input().split())
  B.append([x-l,x+l])
B.sort(key=lambda x:x[1])
max_l=-10**18-5
ans=0
for b in B:
  if max_l <= b[0]:
    max_l = b[1]
    ans+=1
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new
#print(dp)
ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)


### FIXED CODE ###

N, M = map(int, input().split())
A = []
C = []
for _ in range(M):
    a, _ = map(int, input().split())
    A.append(a)
    C_ = list(map(int, input().split()))
    c = 0
    for c_ in C_:
        c |= 1<<c_-1
    C.append(c)
dp = [float("inf")] * (1<<N)
dp[0] = 0
for a, c in zip(A, C):
    dp_new = dp[:]
    for s, d in enumerate(dp):
        dp_new[s|c] = min(d+a, dp_new[s|c])
    dp = dp_new
#print(dp)
ans = dp[(1<<N)-1]
print(ans if ans != float("inf") else -1)
### BUGGY CODE ###

import math
n,a,b = map(int,input().split())
tmp = 2**n - 1
mn = math.factorial(n)
tmp_a = mn//(math.factorial(n-a)*math.factorial(a))
tmp_b = mn//(math.factorial(n-b)*math.factorial(b))
print((tmp-tmp_a-tmp_b)%(10**9+7))


### FIXED CODE ###

import math
n,a,b = map(int,input().split())
mod = 10**9 + 7
s = pow(2,n,mod) - 1
a_ue = 1
a_shita = 1
b_ue = 1
b_shita = 1
for i in range(1,a+1):
    a_ue = a_ue * (n-i+1) % mod
    a_shita = a_shita * i % mod
a_tmp = a_ue * pow(a_shita,mod-2,mod) % mod
# pow(a_shita,mod-2,mod) で逆元を求める
for j in range(1,b+1):
    b_ue = b_ue * (n-j+1) % mod
    b_shita = b_shita * j % mod
b_tmp = b_ue * pow(b_shita,mod-2,mod) % mod
#print('j',j,b_ue,b_shita,b_ue/b_shita)
print((s-a_tmp-b_tmp)%mod)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from heapq import heappush,heappop
from collections import deque
from sys import stdin,stdout


def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = deque()
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX.append([x,s-x,t-x])
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)]+[10**10]

  ans = []
  for x,s,t in sorted(list(STX)):
    l = bisect_left(Dn,s)
    while Dn[l] < t:
      heappush(ans,(Dn[l],x))
      Dn.pop(l)
  for d in Dn:
    heappush(ans,(d,-1))

  return ans


if __name__ == "__main__":
  ans = main()
  while len(ans)>1:
    print(heappop(ans)[1])


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

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

p = 1

for i in range(N):
    p *= A[i]

if p > 10 ** 18:
    print(-1)
else:
    print(p)


### FIXED CODE ###

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

p=1

for k in range(N):
    if A[k] == 0:
        p = 0
        break

if p == 0:
    print(p)    
else:   
    for i in range(N):
        p *= A[i]
        if p > 10 ** 18:
            p = -1
            break

    print(p)
### BUGGY CODE ###

import itertools

def main():
	N = int(input())
	A = map(int, input().split())
	sum = 0
	for i, j in  itertools.combinations(A, 2):
		sum = sum + (i ^ j)
	print( sum % (10**9+7))


if __name__ == '__main__':
	main()


### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int, input().split()))
	
	keta =len(bin(max(A)))-2
	A = [ '{a:0{keta}b}'.format(a=a,keta=keta) for a in A]
	sum = 0
	for i in range(keta):
		bit = [a[i] for a in A]
		sum = sum + (2**(keta-i-1) * ( bit.count('1')*bit.count('0')))
	print(sum % (10**9+7))

if __name__ == '__main__':
	main()