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

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

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        a=j
        b=N
        while a+1!=b and a!=b:
            if l[(a+b)//2]<l[i]+l[j]:
                a=(a+b)//2
            else:
                b=(a+b)//2
        #print(a,b)
        if a!=b:
            count+=a-j
        else:
            if a==b:
                if l[a]<l[i]+l[j]:
                    count+=b-j
                elif l[a]>l[i]+l[j]:
                    pass
            else:
                if l[a]<l[i]+l[j]:
                    count+=a-j



print(count)

### FIXED CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_left(l,l[i]+l[j],j+1)-j-1
         
print(count)
### BUGGY CODE ###

n = int(input())
ans = []
for _ in range(n):
    s = input()
    if s in ans:
        continue
    ans.append(s)
print(len(ans))

### FIXED CODE ###

n = int(input())
ans = {}
for _ in range(n):
    s = input()
    if not s in ans.keys():
        ans[s] = 1
    ans[s] += 1
print(len(ans.keys()))
### BUGGY CODE ###

import itertools

def main():
    n, m, q = map(int, input().split())
    r = list(map(int, input().split()))
    dist = [[10**18 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 10 ** 18
    for p in itertools.permutations(r):
        total = 0
        for i in range(q-1):
            total += dist[p[i]-1][p[i+1]-1]
        ans = min(ans, total)

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools

def main():
    n, m, q = map(int, input().split())
    r = list(map(int, input().split()))
    dist = [[10**18 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = 10 ** 18
    for p in itertools.permutations(r):
        total = 0
        for i in range(q-1):
            total += dist[p[i]-1][p[i+1]-1]
        ans = min(ans, total)

    print(ans)

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

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

def is_prime(n):
    if n == 1:
        return False
    for i in range(1, int(n**(1/2)) + 1):
        if n%i == 0:
            return False
    return True
    
def main():
    a, b = map( int, input().split())
    d = gcd(a,b)
    if d == 1:
        print(1)
        return
    if is_prime(d):
        print(2)
        return
    ans = 1
    for i in range(2, d+1):
        if d%i == 0:
            ans += 1
        while d%i == 0:
            d //= i
        if d == 1:
            break
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def is_prime(n):
    if n == 1:
        return False
    for i in range(2, int(n**(1/2)) + 1):
        if n%i == 0:
            return False
    return True

def factors(N): #約数を全て求める。ただし、順不同
    from collections import deque
    ret = 0
    middle = int( N**(1/2))
    for i in range(1, middle):
        if N%i == 0:
            if is_prime(i):
                ret += 1
            if is_prime(N//i):
                ret += 1
            
    if N%middle == 0:
        if is_prime(middle):
            ret += 1
        if middle != N//middle:
            if is_prime(N//middle):
                ret += 1
    return ret

    
def main():
    a, b = map( int, input().split())
    d = gcd(a,b)
#    print(2, is_prime(2))
    if d == 1:
        print(1)
        return
    if is_prime(d):
        print(2)
        return

    print(factors(d)+1)

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

N, K = [int(i) for i in input().split()]
ps = [int(i) for i in input().split()]
cs = [int(i) for i in input().split()]

global_max = -10**10
past_score = [[]]*N
past_time = [[]]*N
for n in range(N):
    score = 0
    itta = set([])
    iru = n
    k = 0
    while k < K:
        score += cs[ps[iru]-1]
        k += 1
        if iru in itta:
            # print('itta')
            # print(f'iru is {iru}')
            # print(f'score is {score}')
            # print(f'past_score is {past_score}')
            if score > past_score[iru]:
                # print('plus loop')
                T = k - past_time[iru]  # 周期
                # print(f'周期は {T}')
                if K - k > (2 * T) + 1:
                    # print(f'繰り返しは{((K-k)//T - 1)}回')
                    # print('それによって', (((K-k)//T - 1)*(score - past_score[iru])))
                    score += (((K-k)//T - 1)*(score - past_score[iru]))
                    k += T * ((K-k)//T - 1)
                    # print(f'new score is {score}')
                    # print(f'new k is {k}')
            else:
                # print('break!')
                break
        itta.add(iru)
        # print(iru)
        # print(ps[iru]-1)
        # print(f'score is {score}')
        global_max = max(score, global_max)
        past_score[iru] = score
        past_time[iru] = k
        iru = ps[iru]-1
print(global_max)


### FIXED CODE ###

N, K = [int(i) for i in input().split()]
ps = [int(i) for i in input().split()]
cs = [int(i) for i in input().split()]

global_max = -10**10
past_score = [[]]*N
past_time = [[]]*N
for n in range(N):
    score = 0
    itta = [0]*N
    iru = n
    k = 0
    while k < K:
        score += cs[ps[iru]-1]
        k += 1
        if itta[iru] == 1:
            # print('itta')
            # print(f'iru is {iru}')
            # print(f'score is {score}')
            # print(f'past_score is {past_score}')
            if score > past_score[iru]:
                # print('plus loop')
                T = k - past_time[iru]  # 周期
                # print(f'周期は {T}')
                if K - k > (2 * T) + 1:
                    # print(f'繰り返しは{((K-k)//T - 1)}回')
                    # print('それによって', (((K-k)//T - 1)*(score - past_score[iru])))
                    score += (((K-k)//T - 1)*(score - past_score[iru]))
                    k += T * ((K-k)//T - 1)
                    # print(f'new score is {score}')
                    # print(f'new k is {k}')
            else:
                # print('break!')
                break
        itta[iru] = 1
        # print(iru)
        # print(ps[iru]-1)
        # print(f'score is {score}')
        global_max = max(score, global_max)
        past_score[iru] = score
        past_time[iru] = k
        iru = ps[iru]-1
print(global_max)
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 重なるところに注意
A, B, K = lr()
answer = [x for x in range(A, B+1) if x < A+K or x > B-K]
print('\n'.join(map(str, answer)))

### FIXED CODE ###

A, B, K = map(int, input().split())
K = min(K, B - A + 1)
print(*sorted(set([i for i in range(A, A+K)] + [i for i in range(B-K+1, B+1)])), sep='\n')
### BUGGY CODE ###

import os
import sys
from io import BytesIO

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))

n, k = map(int, sys.stdin.readline().split())
a = map(int, sys.stdin.readline().split())
f = map(int, sys.stdin.readline().split())
a.sort()
f.sort(reverse=True)

'''
n, k = 100000, 0
a = range(n)
f = range(n)
a.sort()
f.sort(reverse=True)

print n, k

for i in range(n):
	print 1,
print

for i in range(n):
	print 1,
print
'''


def val(p):
	r = 0
	for i in range(n):
		t = 0 if a[i] * f[i] <= p else a[i] - p // f[i]
		r += t
	return r
		
def bin(l, r):
	if l == r:
		return l
	if l + 1 == r:
		if val(l) <= k:
			return l
		else:
			return r
	t = (l + r) // 2
	if val(t) <= k:
		return bin(l, t)
	else:
		return bin(t, r)
		
R = bin(0, 1000000000000)
print(R)

### FIXED CODE ###

import os
import sys
from io import BytesIO

sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))

n, k = map(int, sys.stdin.readline().split())
a = map(int, sys.stdin.readline().split())
f = map(int, sys.stdin.readline().split())
a.sort()
f.sort(reverse=True)

'''
n, k = 100000, 0
a = range(n)
f = range(n)
a.sort()
f.sort(reverse=True)

print n, k

for i in range(n):
	print 1,
print

for i in range(n):
	print 1,
print
'''


def val(p):
	r = 0
	for i in range(n):
		t = 0 if a[i] * f[i] <= p else a[i] - p // f[i]
		r += t
	return r
		
def bin(l, r):
	if l == r:
		return l
	if l + 1 == r:
		if val(l) <= k:
			return l
		else:
			return r
	t = (l + r) // 2
	if val(t) <= k:
		return bin(l, t)
	else:
		return bin(t, r)
		
R = bin(0, 1000000000000)
print(R)
### BUGGY CODE ###

from collections import deque
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

@lru_cache(maxsize=None)
def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)
### BUGGY CODE ###

n, x = map(int,input().split())
xl = list(map(int,input().split()))

xl.append(x)
xl.sort()
sa = []
for i in range(len(xl)-1):
    sa.append(xl[i+1] - xl[i])
    
samin = min(sa)

flag = 0
while flag == 0:
    amari = 0
    for i in sa:
        amari += i % samin
        break
    if amari == 0:
        flag =1
        break
    else:
        for j in range(1,samin+1):
            if samin % j == 0:
                samin = samin // j
                break
print(samin)
        

### FIXED CODE ###

n, x = map(int,input().split())
xl = list(map(int,input().split()))

xl.append(x)
xl.sort()

onesam = 0

if len(xl) == 1:
    print(abs(xl[0] - x))
    exit()

for i in range(len(xl)-1):
    one_sa = xl[i+1] - xl[i]
    if onesam == 0:
        onesam = abs(one_sa)
    else:
        short,big = min(onesam,one_sa),max(onesam,one_sa)
        if big % short == 0:
            onesam = short
            continue
        else:
            while big % short != 0:
                short = short -1
#                 for k in range(2,short+1):
#                     if short % k == 0:
#                         short = short // k
#                         break
            onesam = short
            
print(onesam)
### BUGGY CODE ###

N = int(input())
S = []
C = []
M = 1
pS = ''
pM = 0
for i in range(N):
  s = input()
  if s in S:
    n = S.index(s)
    C[n] += 1
    if C[n] > M:
      if pS != s:
        pS = s
        pM = M
      M = C[n]
      if M - pM > N - i:
        print(s)
        exit()
  else:
    S.append(s)
    C.append(1)
l = len(C)
A = [S[j] for j in range(l) if C[j] == M]
A.sort()
[print(k) for k in A]

### FIXED CODE ###

import collections
N = int(input())
l = [input() for i in range(N)]
L = collections.Counter(l)
a = L.most_common()
M = a[0][1]
A = [j[0] for j in a if j[1] == M]
[print(k) for k in sorted(A)]
### BUGGY CODE ###

h,w,m=map(int, input().split())
a = [0]*m
hc=[0 for i in range(w)]
wc=[0 for i in range(h)]
for i in range(m):
	x,y=map(int, input().split())
	a[i]=[x-1,y-1]
	hc[y-1]+=1
	wc[x-1]+=1
hcm=max(hc)
wcm=max(wc)
hk=[]
wk=[]
for i in range(len(hc)):
	if hc[i]==hcm:
		hk.extend([i])
for i in range(len(wc)):
	if wc[i]==wcm:
		wk.extend([i])
for i in range(len(hk)):
	for j in range(len(wk)):
		if [wk[j],hk[i]] not in a:
			print(hcm+wcm)
			exit()
print(hcm+wcm-1)

### FIXED CODE ###

h,w,m=map(int, input().split())
a=[0]*m
hc=[0]*w
wc=[0]*h
for i in range(m):
	x,y=map(int, input().split())
	a[i]=[x-1,y-1]
	hc[y-1]+=1
	wc[x-1]+=1
hcm=max(hc)
wcm=max(wc)
hk=[0]*w
wk=[0]*h
for i in range(len(hc)):
	if hc[i]==hcm:
		hk[i]=1
for i in range(len(wc)):
	if wc[i]==wcm:
		wk[i]=1
c=0
for i in range(len(a)):
	if wk[a[i][0]]==1 and hk[a[i][1]]==1:
		c+=1
if c==sum(hk)*sum(wk):
	print(hcm+wcm-1)		
else:
	print(hcm+wcm)
### BUGGY CODE ###

# Editorial solution 4
import sys

def f(a, b, c, border, cond):
    na, nb, nc = len(a), len(b), len(c)
    cnt = 0
    for i in range(na):
        for j in range(nb):
            for k in range(nc):
                if a[na-1-i] + b[nb-1-j] + c[nc-1-k] >= border:
                    cnt += nc-k
                    if cnt >= cond:
                        return True
                    break
    return False


def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), key=lambda x: -x)
    B = sorted(list(map(int, input().split())), key=lambda x: -x)
    C = sorted(list(map(int, input().split())), key=lambda x: -x)

    l, r = A[X-1] + B[Y-1] + C[Z-1], A[0] + B[0] + C[0]
    while r - l > 1:
        p = (l + r) // 2
        if f(A, B, C, p, K):
            l = p
        else:
            r = p

    deli = []
    for i in range(X):
        for j in range(Y):
            for k in range(Z):
                if A[i] + B[j] + C[k] < r:
                    break
                deli.append(A[i] + B[j] + C[k])

    num = len(deli)
    deli = sorted(deli, key=lambda x: -x)
    deli += [l] * (K - num)
    for i in range(K):
        print(deli[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = sorted(list(map(int, input().split())), key=lambda x: -x)
    B = sorted(list(map(int, input().split())), key=lambda x: -x)
    C = sorted(list(map(int, input().split())), key=lambda x: -x)

    deli = []
    heappush(deli, (-A[0]-B[0]-C[0], 0, 0, 0))
    pushed = set((0,0,0))
    for _ in range(K):
        d = heappop(deli)
        i, j, k = d[1], d[2], d[3]

        if i+1 < X and (i+1, j, k) not in pushed:
            heappush(deli, (-A[i+1]-B[j]-C[k], i+1, j, k))
            pushed.add((i+1, j, k))

        if j+1 < Y and (i, j+1, k) not in pushed:
            heappush(deli, (-A[i]-B[j+1]-C[k], i, j+1, k))
            pushed.add((i, j+1, k))

        if k+1 < Z and (i, j, k+1) not in pushed:
            heappush(deli, (-A[i]-B[j]-C[k+1], i, j, k+1))
            pushed.add((i, j, k+1))

        print(-d[0])


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

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])

### FIXED CODE ###

import collections

h,w,k=map(int,input().split())
sy,sx,gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
board=[input() for _ in range(h)]
q=collections.deque()
q.append((sx,sy))
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
cost=[[10**18]*w for _ in range(h)]
cost[sy][sx]=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while len(q)!=0:
  x,y=q.popleft()
  c=cost[y][x]
  for i in range(4):
    for j in range(1,k+1):
      if x+j*dx[i]<0 or w<=x+j*dx[i] or y+j*dy[i]<0 or h<=y+j*dy[i]:
        break
      if board[y+j*dy[i]][x+j*dx[i]]=='@':
        break
      if cost[y+j*dy[i]][x+j*dx[i]]<=c:
        break
      if cost[y+j*dy[i]][x+j*dx[i]]>c+1:
        q.append((x+j*dx[i],y+j*dy[i]))
        cost[y+j*dy[i]][x+j*dx[i]]=c+1
if cost[gy][gx]==10**18:
  print(-1)
else:
  print(cost[gy][gx])
### BUGGY CODE ###

N,K = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
maxwa = 0
for i in range(N-K+1):
    wa = 0
    for j in range(K):
        wa += l[i+j]
    maxwa = max(maxwa,wa)
print((maxwa+K)/2)

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
rui = [0]*(N+1)
for i in range(1,N+1):
    rui[i] = rui[i-1] + l[i-1]
maxwa = 0
for i in range(N-K+1):
    wa = rui[K+i]-rui[i]
    maxwa = max(maxwa,wa)
print((maxwa+K)/2)
### BUGGY CODE ###

h,w = map(int,input().split())
lis = [str(input()) for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
        if lis[sx][sy] == "#":
            num = [[0] * w for i in range(h)]
            now = {(sx,sy,1)}
            while len(now) != 0:
                tmp = set()
                for x,y,iro in now:
                    if x > 0:
                        if lis[x-1][y] != lis[x][y] and num[x-1][y] == 0:
                            ans += iro
                            tmp.add((x-1,y,(iro+1)%2))
                            num[x-1][y] = 1
                    if x < h-1:
                        if lis[x+1][y] != lis[x][y] and num[x+1][y] == 0:
                            ans += iro
                            tmp.add((x+1,y,(iro+1)%2))
                            num[x+1][y] = 1
                    if y > 0:
                        if lis[x][y-1] != lis[x][y] and num[x][y-1] == 0:
                            ans += iro
                            tmp.add((x,y-1,(iro+1)%2))
                            num[x][y-1] = 1
                    if y < w-1:
                        if lis[x][y+1] != lis[x][y] and num[x][y+1] == 0:
                            ans += iro
                            tmp.add((x,y+1,(iro+1)%2))
                            num[x][y+1] = 1
                now = tmp

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

dxdy = {(-1, 0), (1, 0), (0, -1), (0, 1)}

h,w = map(int,input().split())
s = [str(input()) for i in range(h)]

ch = [[0] * w for i in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        if ch[i][j] == 0:
            black,white = 0,0
            q = [(i,j)]
            while q:
                y,x = q.pop()
                if ch[y][x] == 0:
                    if s[y][x] == "#":black += 1
                    else:white += 1
                    ch[y][x] = 1
                    for dx,dy in dxdy:
                        if 0 <= x + dx < w and 0 <= y + dy < h and ch[y+dy][x+dx] == 0 and s[y+dy][x+dx] != s[y][x]:
                            q.append((y+dy,x+dx))
            ans += black * white

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

from fractions import gcd

M = 10 ** 9 + 7

def xgcd(a, b):
    x0, x1 = 1, 0
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
    return x0 % M

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = xgcd(a, M)
    ans = (ans + lcm_ * m) % M

print(ans)

### FIXED CODE ###

from fractions import gcd

M = 10 ** 9 + 7

def xgcd(a, b):
    x0, x1 = 1, 0
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
    return x0 % M

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = xgcd(a, M)
    ans = ans + lcm_ * m

print(ans % M)
### BUGGY CODE ###

from collections import Counter
N =int(input())
A = Counter(list(map(int,input().split())))
B = Counter(list(map(int,input().split())))
C = Counter(list(map(int,input().split())))
A_sort = sorted(A.items())
B_sort = sorted(B.items())
C_sort = sorted(C.items())

ans = 0
for i in range(len(A_sort)):
    sum_val = N
    now_k = 0
    now_j = 0
    for j in range(now_j , len(B_sort)):
        if A_sort[i][0] >= B_sort[j][0]:
            continue
        for k in range(now_k , len(C_sort)):
            if A_sort[i][0] < B_sort[j][0] < C_sort[k][0]:
                ans += (sum_val * B_sort[j][1] * A_sort[i][1])
                now_k = k
                now_j = j
                break
            else:
                sum_val -= C_sort[k][1]
print(ans)

### FIXED CODE ###

from collections import Counter
N =int(input())
A = Counter(list(map(int,input().split())))
B = Counter(list(map(int,input().split())))
C = Counter(list(map(int,input().split())))
A_sort = sorted(A.items())
B_sort = sorted(B.items())
C_sort = sorted(C.items())

BtoC = []
ans = 0
start_j = 0
start_k = 0
sum_val = N
for j in range(len(B_sort)):
    for k in range(start_k , len(C_sort)):
        if B_sort[j][0] >= C_sort[k][0]:
            sum_val -= C_sort[k][1]
            start_k = k + 1
        else:
            BtoC.append([B_sort[j][0] , sum_val * B_sort[j][1]])
            break
#print(BtoC)
work = 0
for i in range(len(BtoC) - 2 , -1 , -1):
    BtoC[i][1] = BtoC[i+1][1] + BtoC[i][1]
    work = BtoC[i+1][1]
#print(BtoC)
for i in range(len(A_sort)):
    for j in range(start_j , len(BtoC)):
        if A_sort[i][0] >= BtoC[j][0]:
            start_j = j + 1
        else:
            ans += A_sort[i][1] * BtoC[j][1]
            break
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

INF = 10**9 + 7
n = int(input())
ans =1
while n != 0:
    ans = n*ans % INF
    n -= 1
print(ans)