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

def main():
    MOD = 10**9 + 7
    A_UB = 2**60  # upper bound
    MAX_BIN_LENGTH = len('{:b}'.format(A_UB))

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

    bit = 1
    answer = 0
    for b in range(MAX_BIN_LENGTH):
        a_bits = [a & 1 for a in A]
        one_num = sum(a_bits)
        answer += (one_num * (N - one_num) * bit) % MOD
        answer %= MOD
        bit *= 2
        bit %= MOD
        for i in range(N):
            A[i] >>= 1
    print(answer)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np


def main():
    MOD = 10**9 + 7
    A_UB = 2**60  # upper bound
    MAX_BIN_LENGTH = len('{:b}'.format(A_UB))

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

    bit = 1
    answer = 0
    for b in range(MAX_BIN_LENGTH):
        a_bits = A & 1
        one_num = np.count_nonzero(a_bits)
        answer += (one_num * (N - one_num) * bit) % MOD
        answer %= MOD
        bit *= 2
        bit %= MOD
        A >>= 1
    print(answer)


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

import functools
import operator

n = int(input())
a = list(map(int, input().split()))
s = functools.reduce(operator.mul, a)
if(s > 1e18):
    print(-1)
else:
    print(s)

### FIXED CODE ###

import math

n = int(input())
s = 1
frag = 0
a = list(map(int, input().split()))
if(0 in a):
    print(0)
else:
    for i in range(len(a)):
        s *= a[i]
        if(s > 10**18):
            frag = 1
            break
    if(frag):
        print(-1)
    else:
        print(s)
### BUGGY CODE ###

h,w=map(int,input().split())
inf=float("inf")
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))

def dist(a,b):
  if S[a][b]=="#":
    return 0
  else:
    D=[[inf]*(w+2) for _ in range(h+2)]
    D[a][b]=0
    Visit=[100*a+b]
    while Visit:
      v=Visit.pop()
      va,vb=v//100,v%100
      for dx,dy in d:
        if S[va+dx][vb+dy]=="#":
          continue
        elif D[va+dx][vb+dy]>D[va][vb]+1:
          Visit.append((va+dx)*100+(vb+dy))
          D[va+dx][vb+dy]=D[va][vb]+1
    ret=0
    for i in range(h):
      for j in range(w):
        if D[i+1][j+1]<inf:
          ret=max(ret,D[i+1][j+1])
    return ret
ans=0
for i in range(h):
  for j in range(w):
    ans=max(dist(i+1,j+1),ans)
print(ans)





### FIXED CODE ###

h,w=map(int,input().split())
inf=float("inf")
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["#"]*(w+2)]
S.extend([["#"]+[s for s in input()]+["#"] for _ in range(h)])
S.append(["#"]*(w+2))

def dist(a,b):
  if S[a][b]=="#":
    return 0
  else:
    D=[[inf]*(w+2) for _ in range(h+2)]
    D[a][b]=0
    Visit=[100*a+b]
    while Visit:
      v=Visit.pop()
      va,vb=v//100,v%100
      for dx,dy in d:
        if S[va+dx][vb+dy]=="#":
          continue
        elif D[va+dx][vb+dy]>D[va][vb]+1:
          Visit.append((va+dx)*100+(vb+dy))
          D[va+dx][vb+dy]=D[va][vb]+1
    ret=0
    for i in range(h):
      for j in range(w):
        if D[i+1][j+1]<inf:
          ret=max(ret,D[i+1][j+1])
    return ret
ans=0
for i in range(h):
  for j in range(w):
    ans=max(dist(i+1,j+1),ans)
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
    mod = 998244353

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

    if d[0] > 0:
        print('0')
        exit()

    tmp = 1
    ans = 1
    for i in range(1, max(d)+1):
        count = d.count(i)
        if count == 0:
            print('0')
            exit() 
        ans *= tmp ** count
        ans %= mod
        tmp = count

    print(ans)


### FIXED CODE ###

if __name__ == "__main__":
    mod = 998244353

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

    if d[0] > 0:
        print('0')
        exit()

    if len(d) == 1:
        print('1')
        exit()

    d.sort()
    d.pop(0)
    if d[0] == 0:
        print('0')
        exit()

    tmp = 1
    ans = 1
    max_num = max(d)
    dic = dict()
    for i in range(n-1):
        if d[i] in dic:
            dic[d[i]] += 1
        else:
            dic[d[i]] = 1

    for i in range(1, max_num+1):
        if i in dic:
            count = dic[i]
        else:
            print('0')
            exit()
        if count == 0:
            print('0')
            exit()
        ans *= tmp ** count
        ans %= mod
        tmp = count

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

import bisect
n = int(input())
c = [int(input())]
for i in range(n-1):
  a = int(input())
  if c[-1] >= a:
    c.append(a)
  else:
    ind = bisect.bisect_left(c[::-1],a)
    c[len(c)-ind] = a
print(len(c))

### FIXED CODE ###

import bisect
n = int(input())
a = [int(input()) for i in range(n)]
c = [a[-1]]
for i in a[n-2::-1]:
  if c[-1] <= i:
    c.append(i)
  else:
    c[bisect.bisect_left(c,i+1)] = i
  #print(c)
print(len(c))
### BUGGY CODE ###

from collections import Counter

if __name__ == '__main__':
    s = list(input())
    s.reverse()
    n = len(s)
    mods = [0] * n
    for i in range(n):
        mods[i] = int(''.join(list(reversed(s[:i + 1])))) % 2019
    mods.sort()
    m = Counter(mods)
    ans = 0
    for k, v in m.items():
        if k == 0:
            ans += v
        ans += (v * (v - 1)) // 2
    print(ans)


### FIXED CODE ###

if __name__ == '__main__':

    s = list(input())
    s.reverse()
    n = len(s)
    now = 0
    mods = [0] * 2019
    mods[0] += 1
    ten = 1
    for i in range(n):
        now += ten * int(s[i])
        now %= 2019
        ten *= 10
        ten %= 2019
        mods[now] += 1
    ans = 0
    for i in mods:
        ans += (i * (i - 1)) // 2
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
    if t[-2]!=a[1]:
        ans=0
for i in range(n):
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans*=min(t[i+1],a[i+1])
print(ans%(10**9+7))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
t=list(map(int,input().split()))
a=list(map(int,input().split()))
t=[0]+t+[t[-1]]
a=[a[0]]+a+[0]
ans=1
#print(t,a)
for i in range(n):
    if t[i]<t[i+1]:
        if a[i+1]<t[i+1]:
            ans=0
            break
    if a[i]>a[i+1]:
        if t[i]<a[i]:
            ans=0
            break
    if t[-2]!=a[1]:
        ans=0
        break
    if t[i]==t[i+1] and a[i+1]==a[i+2]:
        ans=(ans*(min(t[i+1],a[i+1])))%(10**9+7)
print(ans)
### BUGGY CODE ###

import itertools

X, Y, Z, K  = list(map(int, input().split()))
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

AB = [a + b for (a, b) in list(itertools.product(A, B))]
AB.sort(reverse = True)
ans = [ab + c for (ab, c) in list(itertools.product(AB[:min(3000, X*Y*Z)], C))]
ans.sort(reverse = True)

for i in range(K):
    print(ans[i])

### FIXED CODE ###

X, Y, Z, K  = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

l = []
for a in A:
    for b in B:
        l.append(a+b)
l = sorted(l, reverse = True)[:K]

ans = []
for c in C:
    for k in l:
        ans.append(c + k)
        
ans = sorted(ans, reverse = True)
print(*ans[:K], sep="\n")
### BUGGY CODE ###

u_list = []
uo_list = []
e = int(input())

for i in range(e):
    u = input()
    uo_list.append(u)
    
unique = [u_list.append(x) for x in uo_list if x not in u_list]
print(len(unique))

### FIXED CODE ###

s = set([])
things = int(input())

for i in range(things):
    p = input()
    s.add(p)

print(len(s))
### BUGGY CODE ###

D, G = map(int, input().split())
G //= 100
problems = []
for i in range(D):
    b = i + 1
    p, c = map(int, input().split())
    c //= 100
    problems.append((b, p, c))  # 基本点, 問題数, ボーナス

nsolved = {0: 0}  # 総合点 → 必要問題数

for b, p, c in problems:
    nsolved2 = {}
    for k in nsolved:
        for n in range(p + 1):
            s = b * n + (0 if n < p else c)  # n問解いたときの総合点
            g = min(k + s, G)                # 総合点
            if g not in nsolved2:
                nsolved2[g] = nsolved[k] + n
            else:
                nsolved2[g] = min(nsolved2[g], nsolved[k] + n)
    nsolved = nsolved2

print(nsolved[G])


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
from math import ceil
 
D, G = [int(t) for t in input().split()]
p = []
c = []
for i in range(D):
    p_, c_ = [int(t) for t in input().split()]
    p.append(p_)
    c.append(c_)
 
def minsolve(G, p, c, i):
    """100i点以下の問題だけでGを達成する最小問題数"""
    if i <= 0:
        return float('inf')
    n = min(ceil(G / (100 * i)), p[i-1])
    s = 100 * i * n
    if n == p[i-1]:
        s += c[i-1]
    if s >= G:
        return min(n, minsolve(G, p, c, i-1))
    else:
        return min(n + minsolve(G - s, p, c, i-1), minsolve(G, p, c, i-1))
 
m = min(minsolve(G, p, c, i) for i in range(1, D+1))
print(m)
### BUGGY CODE ###

N = int(input())
P = 1
for i in range(N):
    P = P * (i+1)
print(P % (10**9 + 7))

### FIXED CODE ###

import math
N = int(input())
P = math.factorial(N)
print(P % (10**9 + 7))
### BUGGY CODE ###

#全探索でO(N^2)
N = int(input())
A = [int(input()) for _ in range(N)]

count = 0
tmp = - 10 ** 10
for i in range(N):
    # print ('i', i)
    if A[i] == -10 ** 11:
        continue
    else:
        tmp = A[i]
        count += 1
        for j in range(i + 1, N):
            if tmp < A[j]:
                tmp = A[j]
                A[j] = - 10  ** 11
            if j == N - 1:
                tmp = - 10 ** 10
# print (A)
print (count)



### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

dp = [-A[0]]
def solve():
    import bisect
    for i in range(1, N):
        a = bisect.bisect_left(dp, -A[i]+0.1) #入れるべき場所
        # print (a)
        if a == len(dp):
            dp.append(-A[i])
        else:
            dp[a] = -A[i]
        # print (dp)
    return len(dp)


print (solve())
### BUGGY CODE ###

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

N,M,K=MI()
A=[0]+LI()
B=[0]+LI()
from itertools import accumulate
A=list(accumulate(A))
B=list(accumulate(B))
ans=0
for i in range(N+1):
  if A[i]>K:
    continue
  for j in range(M,-1,-1):
    if A[i]+B[j]>K:
      continue
    ans=max(ans,i+j)
    break
print(ans)

### FIXED CODE ###

N,M,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[0]
B=[0]
ans=0
j=M
for i in range(N):
  A.append(A[i]+a[i])
for i in range(M):
  B.append(B[i]+b[i])
for i in range(N+1):
  if A[i]>K:
    break
  while A[i]+B[j]>K:
    j-=1
  ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

from collections import Counter

N = int(input())
a = Counter(map(int, input().split()))
Q = int(input())

for i in range(Q):
    b, c = map(int, input().split())
    a[c] += a[b]
    a[b] = 0
    #print(sum([x*y for x, y in a.items()]))
    print(sum(a.elements()))

### FIXED CODE ###

from collections import Counter

N = int(input())
a = Counter(map(int, input().split()))
Q = int(input())

sum_a = sum(a.elements())

for i in range(Q):
    b, c = map(int, input().split())
    a[c] += a[b]
    sum_a += (c-b) * a[b]
    a[b] = 0
    print(sum_a)
### BUGGY CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                ans+=1
print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for i in range(K+1):
    for j in range(K+1):
        k=S-i-j
        if 0<=k and k<=K:
            ans+=1
print(ans)
### BUGGY CODE ###

def main():
  _max = max
  h, w = map(int, input().split())
  s = [input() + '#' for _ in range(h)]
  s.append('#' * (w + 1))

  rt = [[-1] * (w + 1) for _ in range(h + 1)]

  tstart = [-1] * (w + 1)
  for i in range(h + 1):
    si = s[i]
    rti = rt[i]
    ystart = -1
    for j in range(w + 1):
      if si[j] == '#':
        if ystart != -1:
          jy = j - ystart
          for k in range(ystart, j):
            rti[k] += jy
          ystart = -1
        tj = tstart[j]
        if tj != -1:
          itj = i - tj
          for k in range(tj, i):
            rt[k][j] += itj
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tstart[j] == -1:
          tstart[j] = i

  print(_max(_max(l) for l in rt))

main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
for i in range(q):
	m=int(raw_input())
	print max([c[i]%m for i in range(n)])

### FIXED CODE ###

N,Q=map(int,raw_input().split())
c=map(int,raw_input().split())

mxc=max(c)
p=[0]*(mxc+1)
for i in c:
    p[i]=1
    
l=[0]*(mxc+1)
num=0
for i in range(mxc+1):
    l[i]=num
    if p[i]:
        num=i
        
for i in range(Q):
    q=int(raw_input())
    sp=mxc
    ans=0
    while 1:
        r=sp%q
        ans=max(ans,r)
        if sp-r<=0:break
        sp=l[sp-r]
    print ans
### BUGGY CODE ###

p = 998244353

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

hop = []

for i in range(K):
    L, R = map(int, input().split())
    for j in range(L, R + 1):
        hop.append(j)

dp = [0]*N

dp[0] = 1

for i in range(N - 1):
    for j in range(len(hop)):
        if i + hop[j] < N:
            dp[i + hop[j]] += dp[i]
            dp[i + hop[j]] %= p

print(dp[N - 1] % p)

### FIXED CODE ###

class BITRAQ:
    def __init__(self, n, mod):
        self.n = n + 1
        self.mod = mod
        self.bit = [[0]*(self.n) for _ in range(2)]
    
    def add_sub(self, p, i, x):
        while i < self.n:
            self.bit[p][i] += x
            self.bit[p][i] %= self.mod
            i += i & -i
    
    def add(self, l, r, x):
        self.add_sub(0, l, -x * (l - 1))
        self.add_sub(0, r, x * (r - 1))
        self.add_sub(1, l, x)
        self.add_sub(1, r, -x)

    def sum_sub(self, p, i):
        s = 0
        while i > 0:
            s += self.bit[p][i]
            i -= i & -i
        return s
    
    def sum(self, i):
        return self.sum_sub(0, i) + self.sum_sub(1, i) * i

    def get(self, i):
        return self.sum(i) % self.mod - self.sum(i - 1) % self.mod

p = 998244353

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

hop = []

for i in range(K):
    hop.append(tuple(map(int, input().split())))

dp = BITRAQ(N, p)

dp.add(1, 2, 1)

for i in range(N - 1):
    for j in range(K):
        dp.add(i + hop[j][0] + 1, min(N + 1, i + hop[j][1] + 2), dp.get(i + 1) % p)

print(dp.get(N) % p)
### BUGGY CODE ###

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

C = [0] * N
D = [0] * (N + 1)
for a in A:
    C[a-1] += 1
    D[C[a-1]] += 1

S = [0] * (N + 1)
for i in range(N):
    S[i+1] = S[i] + D[i+1]

for K in range(1,N+1):
    l = 0
    r = N + 1
    while(r-l>1):
        m = int((l+r)/2)
        if S[m] >= K * m:
            l = m
        else:
            r = m
    print(l)

### FIXED CODE ###

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

C = [0] * N
D = [0] * (N + 1)
for a in A:
    C[a - 1] += 1
    D[C[a - 1]] += 1

S = [0] * (N + 1)
for i in range(N):
    S[i + 1] = S[i] + D[i + 1]

ans = N
for K in range(1, N + 1):
    while ans > 0 and S[ans] < K * ans:
        ans -= 1
    print(ans)
### BUGGY CODE ###

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

ans = 0
for i in range(2 ** N):
    tmp = 0
    for j in range(N):
        if (i >> j) & 1:
            tmp += V[j] - C[j]
    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

N = int(input())
V = [int(i) for i in input().split()]

for i,x in enumerate(input().split()):
    V[i] -= int(x)

V.sort()

ans = 0
for v in V:
    if v > 0:
        ans += v

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

import numpy as np
from scipy.ndimage.interpolation import shift
h, w = map(int, input().split())
a = np.array([[c == "#" for c in input()] for _ in range(h)], dtype=bool)
cnt = 0
while a.all() == False:
    a += shift(a, [0, -1], order=1, cval=False) \
        + shift(a, [0, 1], order=1, cval=False) \
        + shift(a, [1, 0], order=1, cval=False) \
        + shift(a, [-1, 0], order=1, cval=False)
    cnt += 1
print(cnt)

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
cm = [[0 for j in range(w + 2)] for i in range(h + 2)]
que = deque([])
for i in range(1, h + 1):
    s = input()
    for j in range(1, w + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
        else:
            que.append(i)
            que.append(j)
ans = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    ans = cm[y][x] + 1
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = ans
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = ans
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = ans
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = ans
        que.append(y)
        que.append(x - 1)
print(ans - 1)
### BUGGY CODE ###

import math
A,B,N = map(int,input().split())
ret = 0
ans = 0
for x in range(1,min(B,N+1)):
  temp = math.floor(A*x/B) - A*math.floor(x/B)
  if temp > ret:
    ret = temp
    ans = x
print(ret)

### FIXED CODE ###

import math
A,B,N = map(int,input().split())
ret = 0
ans = 0
if B == 0:
  print(0)
  exit()
if B > N:
  base = N
else:
  base = B - 1
ret = math.floor(A*base/B) - A*math.floor(base/B)
print(ret)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0 for i in range(N)]

for j in range(1,N):
    a = float('inf')
    for k in range(max(0,j-K),j):
        a = min(a, abs(h[j]-h[k])+dp[k])
    dp[j] = a

print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

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

def gcd(a,b):
  aa=max(a,b)
  bb=min(a,b)
  return gcd(bb,aa%bb) if bb else aa
  

temp=0
for i in range(0,n):
  l_gcd=0
  r_gcd=0
  lis_left=a[:i]
  try:
    lis_right=a[i+1:]
  except IndexError:
    lis_right=[]
  if lis_left:
    for j in range(0,len(lis_left)):
      l_gcd=gcd(l_gcd,lis_left[j])
  if lis_right:
    for j in range(0,len(lis_right)):
      r_gcd=gcd(r_gcd,lis_right[j])
  gcdgcd=gcd(l_gcd,r_gcd)
  if gcdgcd>temp:
    temp=gcdgcd

print(temp)

### FIXED CODE ###

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

def gcd(a,b):
  aa=max(a,b)
  bb=min(a,b)
  return gcd(bb,aa%bb) if bb else aa
  

left=[]
right=[]
for i in range(0,n):
  j=n-i-1
  if left:
    hahaha=gcd(left[i-1],a[i])
    left.append(hahaha)
  else:
    left.append(a[i])
  if right:
    hahaha=gcd(right[i-1],a[j])
    right.append(hahaha)
  else:
    right.append(a[j])
    
keep=0
for i in range(0,n):
  if i==0:
    temp=right[-2]
  elif i==n-1:
    temp=left[-2]
  else:
    temp=gcd(left[i-1],right[n-i-2])
  if temp>keep:
    keep=temp

print(keep)
### BUGGY CODE ###

import bisect as bs
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for a in A:
    _b = bs.bisect_right(B, a)
    for b in range(_b, N):
        ans += N - bs.bisect(C, B[b])
print(ans)

### FIXED CODE ###

import bisect as bs
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
ans = 0
for b in B:
    a = bs.bisect_left(A, b)
    c = N - bs.bisect_right(C, b)
    ans += a * c
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
cnt,x = 0,0
total = (k+1)**2
if (k*2) >= s:
	x = 0
else:
	x = s-(k*2)
while(x<=k):
	res = s-x
	for i in range(k+1):
		for j in range(k+1):
			if i+j == res:
				#print(i,j)
				cnt += 1
	x += 1
print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())
cnt,x = 0,0
for y in range(k+1):
	for z in range(k+1):
		x = s-y-z
		if 0 <= x <= k:
			cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = list(set(a))
s =0
for i in b:
    c = a.count(i)
    if(c<i):
        s += c
    elif(c>i):
        s += c-i
print(s)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = {}
for i in a:
    b[i] = b.get(i,0)+1
s =0
for i in b.keys():
    c = b[i]
    if(c<i):
        s += c
    elif(c>i):
        s += c-i
print(s)
### BUGGY CODE ###

import math

K = int(input())
ans = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += math.gcd(math.gcd(a, b), c)

print(ans)

### FIXED CODE ###

import math

K = int(input())
ans = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        tmp = math.gcd(a, b)
        for c in range(1, K+1):
            ans += math.gcd(tmp, c)

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

from itertools import combinations
from functools import reduce
from collections import Counter


N = int(input())
S = input()
cnt = Counter(S)
ans = 0
for i in range(1, N + 1):
    for cs in combinations("abcdefghijklmnopqrstuvwxyz", i):
        ans += reduce(lambda x, y: x * y, [cnt[c] for c in cs])
print(ans)



### FIXED CODE ###

from collections import Counter


MOD = 10 ** 9 + 7
input()
S = input()
ans = 1
for v in Counter(S).values():
    ans *= v + 1
    ans %= MOD
print(ans - 1)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
mod = 10**9+7
for i in range(60):
    x = 0
    for j in range(n):
        if a[j] >> i & 1: x += 1 # i桁目が1である数の個数
    now = x*(n-x)%mod # 0と1の組み合わせの数(0 xor 1 = 1)
    for _ in range(i): now = now*2%mod # i桁目が1なら*2^i
    ans += now
    ans %= mod
print(ans)