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

# import numpy as np
# import math as np
import copy
import sys
sys.setrecursionlimit(10000000)

f_inf = float("inf")

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
# cost = np.empty(N, dtype = int) - f_inf
cost[0] = 0

def solve(pos, already):
    global cost

    if not(pos in ABC_d): return

    for B, C in ABC_d[pos]:
        if already[B - 1] == True:
            if cost[B - 1] == f_inf:
                pass
            elif cost[pos-1] == f_inf or cost[B - 1] < cost[pos - 1] + C:
                cost[B-1] = f_inf
                solve(B, already)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            already2 = copy.deepcopy(already)# already.copy()
            already2[B - 1] = True
            solve(B, already2)


# already = np.zeros(N, dtype = bool)
already = [False] * N
already[0] = True
solve(1, already)

if (cost[-1] == f_inf):
    print (-1)
else:
    print (max(0, int(cost[-1])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

f_inf = sys.maxsize

N, M, P = map(int, input().split())
ABC_d = {}
for m in range(M):
    A, B, C = map(int, input().split())
    if A in ABC_d:
        ABC_d[A].append([B, C - P])
    else:
        ABC_d[A] = [[B, C - P]]

cost = [-f_inf] * N
cost[0] = 0

def solve(pos, cnt):
    global cost

    if not(pos in ABC_d): return
    if cnt > N: cost[pos-1] = f_inf;

    for B, C in ABC_d[pos]:
        if cost[B - 1] == f_inf or cost[B - 1] >= cost[pos - 1] + C:
            pass
        elif cost[pos-1] == f_inf:
            cost[B-1] = f_inf
            solve(B, cnt + 1)
        elif cost[B - 1] < cost[pos - 1] + C:
            cost[B - 1] = cost[pos - 1] + C
            solve(B, cnt + 1)

solve(1, 1)

if (cost[-1] == sys.maxsize):
    print (-1)
else:
    print (max(0, int(cost[-1])))
### BUGGY CODE ###

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__main__":
    H, W = map(int, input().split())
    ch, cw = map(lambda x: int(x)-1, input().split())
    dh, dw = map(lambda x: int(x)-1, input().split())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    warp = [(y, x) for x in range(-2, 3) for y in range(-2, 3) if abs(y) + abs(x) > 1]
    que = deque()
    que.append((ch, cw, 0))
    while que:
        y, x, w = que.popleft()
        if mc[y][x] < w:
            continue
        for dy, dx in walk:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                que.appendleft((ny, nx, w))
        for dy, dx in warp:
            ny = y + dy
            nx = x + dx
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                mc[ny][nx] = w + 1
                que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])


### FIXED CODE ###

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()


if __name__ == "__main__":
    H, W = map(int, input().split())
    ch, cw = map(lambda x: int(x)-1, input().split())
    dh, dw = map(lambda x: int(x)-1, input().split())
    maze = [list(input()) for _ in range(H)]
    INF = 10**8
    mc = [[INF]*W for _ in range(H)]
    mc[ch][cw] = 0
    walk_que = deque()
    walk_que.append((ch, cw, 0))
    while walk_que:
        y, x, w = walk_que.popleft()
        for ny, nx in [(y+1, x), (y-1, x), (y, x+1), (y, x-1)]:
            if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w and maze[ny][nx] == ".":
                mc[ny][nx] = w
                walk_que.appendleft((ny, nx, w))
        for dy in range(-2, 3):
            ny = y + dy
            for dx in range(-2, 3):
                nx = x + dx
                if H > ny >= 0 and W > nx >= 0 and mc[ny][nx] > w+1 and maze[ny][nx] == ".":
                    mc[ny][nx] = w + 1
                    walk_que.append((ny, nx, w+1))
    if mc[dh][dw] == INF:
        print(-1)
    else:
        print(mc[dh][dw])
### BUGGY CODE ###

from math import sqrt
def main():
    N=int(input())
    A=list(map(int,input().split()))
    s=set()
    A.sort()
    a=0
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.5)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()

### FIXED CODE ###

from math import sqrt
from time import perf_counter
t0=perf_counter()
N=int(input())
A=list(map(int,input().split()))
A.sort()
def main():
    a=0
    s=set()
    t=0
    if A[0]!=1:
        for i in A:
            if i in s:
                if t==i:
                    a-=1
                    t=0
                continue
            for j in range(2,int(sqrt(i)+1.1)):
                if i%j:
                    continue
                if j in s:
                    break
                if i//j in s:
                    break
            else:
                t=i
                a+=1
            s.add(i)
            if perf_counter()-t0>1.9:
                a=N
                break                
    else:
        if N>1 and A[1]==1:
            a=0
        else:
            a=1
    print(a)
main()
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7




pair_flg=0
set_flg=0
n=I()
A=LI()
t_set=set()
s_set=set(range(2,n+1))
for j in range(n):
    a=A[j]
    prime_set = set()
    for i in range(2, int(a ** 0.5) + 1):
        while a % i == 0:
            prime_set.add(i)
            a //= i
        if a == 1:
            break
    if a != 1:
        prime_set.add(a)
    if prime_set&t_set:
        pair_flg=1
    t_set|=prime_set
    s_set&=prime_set


if not pair_flg:
    print("pairwise coprime")
elif not s_set:
    print("setwise coprime")
else:
    print("not coprime")




### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n=I()
A=LI()
l=A[0]
num=[0]*(10**6+1)
for i in range(1,n):
    num[A[i]]+=1
    l=gcd(l,A[i])



if l!=1:
    print("not coprime")
    exit()


for j in range(2,10**6):
    ret=0
    for k in range(j,10**6+1,j):
        ret+=num[k]
    if ret>1:
        print("setwise coprime")
        exit()

print("pairwise coprime")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
c=0
for i in range(N):
  for j in range(i+1,N+1):
    if sum(A[i:j])==0:
      c+=1
print(c)

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
b=ans=0
c=collections.Counter([0])
for a in A:
  b+=a
  ans+=c[b]
  c[b]+=1
print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
nums = LI()
for i, j in LIR(m):
    nums += [j] * i


nums.sort()
print(sum(nums[-n:]))


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
nums = LI()
que = []
for k, v in Counter(nums).items():
    heappush(que, (-k, v))
for i, j in LIR(m):
    heappush(que, (-j, i))


ret = 0
ans = 0
while ret < n:
    k, v = heappop(que)
    ret += v
    ans += -k * v


print(ans + (ret - n) * k)
### BUGGY CODE ###

n,m = map(int,input().split())
if m == 1:
    print("IMPOSSIBLE")
    exit()
a = []
for i in range(m):
    arr = list(map(int,input().split()))
    a.append(arr)
l = [i[0] for i in a if i[1]==n]
if len(l)==0:
    print("IMPOSSIBLE")
    exit()
for i in l:
    if [1,i] in a:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")

### FIXED CODE ###

n,m = map(int,input().split())
if m == 1:
    print("IMPOSSIBLE")
    exit()
a = set()
b = set()
for i in range(m):
    arr = list(map(int,input().split()))
    if 1 in arr:a.add(arr[1])
    if n in arr:b.add(arr[0])
if len(a&b)==0:print("IMPOSSIBLE")
else:print("POSSIBLE")
### BUGGY CODE ###

n = int(input())
s = list(input())
b = [s[i:].count(".") for i in range(n)]
c = [s[:i-1].count("#") for i in range(n)]
a = [b[i]+c[i] for i in range(n)]
if "." not in s:
    a.append(0)
elif "#" not in s:
    a.append(0)
print(min(a))

### FIXED CODE ###

import bisect
n = int(input())
s = list(input())
b = [0]*(n+1)
c = [s.count(".")]*(n+1)
a = []
a.append(c[0])
for i in range(n):
    if s[i] == "#":
        b[i+1] = b[i] + 1
        c[i+1] = c[i]
    else:
        c[i+1] = c[i] - 1
        b[i+1] = b[i]
    a.append(b[i+1] + c[i+1])
if "." not in s:
    a.append(0)
elif "#" not in s:
    a.append(0)
print(min(a))
### BUGGY CODE ###

n, a, b, c, d = map(int, raw_input().split())
dp = [0]*(n+1)
dp[0] = 1

MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)
for g in xrange(a, b+1):
    y = frev[g]
    Y = [pow(y, j, MOD)*frev[j] for j in xrange(c, d+1)]
    for i in rn:
        dp[i] = (dp[i] + frev[n-i]*sum(dp[i-g*j] * fact[n-i+g*j] * Y[j-c] % MOD for j in xrange(c, min(d, i/g)+1)) % MOD)
print dp[n]%MOD

### FIXED CODE ###

n, a, b, c, d = map(int, raw_input().split())
dp = [0]*(n+1)
dp[0] = 1

MOD = 10**9+7
fact = [1]*(n+1)
frev = [1]*(n+1)

rn = range(n, -1, -1)

for i in xrange(1, n+1):
    fact[i] = (fact[i-1] * i) % MOD
    frev[i] = pow(fact[i], MOD-2, MOD)
for g in xrange(a, b+1):
    y = frev[g]
    for i in rn:
        x = frev[n-i]
        dp[i] = (dp[i] + sum(dp[i-g*j] * fact[n-i+g*j] * x * pow(y, j, MOD) * frev[j] for j in xrange(c, min(d, i/g)+1))) % MOD
print dp[n]
### BUGGY CODE ###

# from functools import lru_cache

n = int(input())


# @lru_cache(maxsize=None)
# def dp(num, typ, mod=10 ** 9 + 7):
#     print(num, typ)
#     if num == 1:
#         if typ == 1:  # contain 0 not 9
#             return 1
#         elif typ == 2:  # contain 9 not 0
#             return 1
#         elif typ == 3:  # not contain
#             return 8
#         elif typ == 0:
#             return 0

#     if typ == 0:
#         return (dp(num - 1, 1) + dp(num - 1, 2) + dp(num - 1, 0) * 10) % mod
#     elif typ == 1:  # contain 0 not 9
#         return (dp(num - 1, 1) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 2:  # contain 9 not 0
#         return (dp(num - 1, 2) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 3:  # not contain
#         return (dp(num - 1, 3) * 8) % mod


# print(dp(n, 0))

dp = [[0 for j in range(4)] for i in range(n + 1)]

mod = 10 ** 9 + 7
for i in range(1, n + 1):
    for j in range(4):
        if j == 0:
            dp[i][j] = (dp[i - 1][0] * 10 + dp[i - 1][1] + dp[i - 1][2]) % mod
            if i == 1:
                dp[i][j] = 0
        elif j == 1:
            dp[i][j] = (dp[i - 1][1] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 2:
            dp[i][j] = (dp[i - 1][2] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 3:
            dp[i][j] = (dp[i - 1][3] * 8) % mod
            if i == 1:
                dp[i][j] = 8

print(dp[n][0])



### FIXED CODE ###

# from functools import lru_cache

n = int(input())


# @lru_cache(maxsize=None)
# def dp(num, typ, mod=10 ** 9 + 7):
#     print(num, typ)
#     if num == 1:
#         if typ == 1:  # contain 0 not 9
#             return 1
#         elif typ == 2:  # contain 9 not 0
#             return 1
#         elif typ == 3:  # not contain
#             return 8
#         elif typ == 0:
#             return 0

#     if typ == 0:
#         return (dp(num - 1, 1) + dp(num - 1, 2) + dp(num - 1, 0) * 10) % mod
#     elif typ == 1:  # contain 0 not 9
#         return (dp(num - 1, 1) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 2:  # contain 9 not 0
#         return (dp(num - 1, 2) * 9 + dp(num - 1, 3)) % mod
#     elif typ == 3:  # not contain
#         return (dp(num - 1, 3) * 8) % mod


# print(dp(n, 0))

dp = [[0 for j in range(4)] for i in range(n + 1)]

mod = 10 ** 9 + 7
for i in range(1, n + 1):
    for j in range(4):
        if j == 0:
            dp[i][j] = (dp[i - 1][0] * 10 + dp[i - 1][1] + dp[i - 1][2]) % mod
            if i == 1:
                dp[i][j] = 0
        elif j == 1:
            dp[i][j] = (dp[i - 1][1] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 2:
            dp[i][j] = (dp[i - 1][2] * 9 + dp[i - 1][3]) % mod
            if i == 1:
                dp[i][j] = 1
        elif j == 3:
            dp[i][j] = (dp[i - 1][3] * 8) % mod
            if i == 1:
                dp[i][j] = 8

print(dp[n][0])
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
M = max(a)
p = len(format(M, 'b'))
l = [[0 for _ in range(n)] for _ in range(p)]
ans = 0
for i in range(n):
    a_s = format(a[i], '0' + str(p) + 'b')
    for c in range(p):
        l[c][i] = int(a_s[c])
for i in range(p):
    zero = 0
    for j in range(n):
        if l[i][j] == 0:
            zero += 1
    ans += (2**(p - i - 1)) * zero * (n - zero)
    ans %= (10**9 + 7)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    M = max(a)
    p = len(format(M, 'b'))
    l = [0 for _ in range(p)]
    ans = 0
    for i in range(n):
        a_s = format(a[i], '0' + str(p) + 'b')
        for c in range(p):
            if a_s[c] == '1':
                l[c] += 1
    for i in range(p):
        c1 = l[i]
        ans += (2**(p - i - 1)) * c1 * (n - c1)
        ans %= (10**9 + 7)
    print(ans)

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


def knapsack(n,c,w,v,dp):
  if dp[n][c]!=None:
    return dp[n][c]
  
  if n == 0 or c == 0:
    return 0
  if w[n] > c:
    dp[n][c] = knapsack(n-1,c,w,v,dp)
    return dp[n][c]
  else:
    opt1 = v[n] + knapsack(n-1,c-w[n],w,v,dp)
    opt2 = knapsack(n-1,c,w,v,dp)
    dp[n][c] = max(opt1,opt2)
    return dp[n][c]

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

w = [-1]; v = [-1]
size = n+1
dp = [ [None for i in range(c+1)] for j in range(n+1)]
for _ in range(n):
  wi , vi= map(int,input().split())
  w.append(wi)
  v.append(vi)

result = knapsack(n,c,w,v,dp)
print(result)        
        
        

### FIXED CODE ###

n,W = map(int,input().split())
wt =[];val=[]

dp = [[0 for i in range(W+1)] for j in range(n)]
for _ in range(n):
  wi , vi= map(int,input().split())
  wt.append(wi)
  val.append(vi)

for i in range(W+1):
  if i>=wt[0]:
    dp[0][i]=val[0]   
  else:
    dp[0][i]=0
    
    
    
#print(dp)  
for i in range(1,n):
  wi = wt[i]
  vi = val[i]
  for w in range(1,W+1):
    if wi <= w:
      dp[i][w] = max(vi + dp[i-1][w-wi] , dp[i-1][w] )
    else:
      dp[i][w] = dp[i-1][w]

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

n, m = map(int, input().split())
pys = [list(map(int, input().split())) for _ in range(m)]
d = [[] for _ in range(n)]
for py in pys:
    p, y = py
    d[p - 1].append(y)

for i in range(n):
    d[i] = sorted(d[i])

for py in pys:
    p, y = py
    number = d[p - 1].index(y) + 1

    print(str(p).zfill(6) + str(number).zfill(6))

### FIXED CODE ###

from bisect import bisect_left

n, m = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(m)]
pys = [[] for _ in range(n)]
for q in qs:
    p, y = q
    p -= 1
    pys[p].append(y)

for i in range(n):
    pys[i] = sorted(pys[i])

for q in qs:
    p, y = q
    p -= 1
    number = bisect_left(pys[p], y) + 1

    print(str(p + 1).zfill(6) + str(number).zfill(6))
### BUGGY CODE ###

x,y,a,b,c=map(int,input().split()) #x,yだけ見る。
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
s=sorted(p+q+r, reverse=True)
cntr,cntg,ans=0,0,0
for i in range(a+b+c):
    if cntr!=x and (s[i] in set(p) or s[i] in set(r)):
        ans+=s[i]
        cntr+=1
    elif cntg!=y and ( s[i] in set(q) or s[i] in set(r)):
        ans+=s[i]
        cntg+=1
print(ans)

### FIXED CODE ###

x,y,a,b,c=map(int,input().split()) #x,yだけ見る。
p=list(map(int,input().split()))
q=list(map(int,input().split()))
r=list(map(int,input().split()))
p=sorted(p,reverse=True)[:x]
q=sorted(q,reverse=True)[:y]
print(sum(sorted(p+q+r, reverse=True)[:x+y]))
### BUGGY CODE ###

H, W, M = map(int,input().rstrip().split())
l = [[0 for i in range(H)] for j in range(W)]
r = [0]*H
c = [0]*W
for i in range(M):
    h, w = map(int,input().rstrip().split())
    l[w-1][h-1] = 1
    r[h-1] += 1
    c[w-1] += 1
max_r = max(r)
max_c = max(c)
r_i =[i for i, x in enumerate(r) if x == max_r]
c_j =[i for i, x in enumerate(c) if x == max_c]
ans = max_r+max_c-1
for i in r_i:
    for j in c_j:
        if l[j][i] == 0:
            ans = max_r+max_c
            break
    else:
        continue
    break
print(ans)

### FIXED CODE ###

H, W, M = map(int,input().rstrip().split())
bomb = []
r = [0]*H
c = [0]*W
max_r = 0
max_c = 0
r_i = []
c_j = []
r_num = 0
c_num = 0
for i in range(M):
    h, w = map(int,input().rstrip().split())
    bomb.append([h-1,w-1])
    r[h-1] += 1
    if r[h-1]>max_r:
        max_r = r[h-1]
        r_i = [h-1]
        r_num = 1
    elif r[h-1]==max_r:
        r_i.append(h-1)
        r_num += 1
    c[w-1] += 1
    if c[w-1]>max_c:
        max_c = c[w-1]
        c_j = [w-1]
        c_num = 1
    elif c[w-1]==max_c:
        c_j.append(w-1)
        c_num += 1
r_set = set(r_i)
c_set = set(c_j)
num = 0
for i in range(M):
    if bomb[i][0] in r_set:
        if bomb[i][1] in c_set:
            num += 1
if num<r_num*c_num:
    ans = max_r+max_c
else:
    ans = max_r+max_c-1
print(ans)
### BUGGY CODE ###

#標準入力の受け取り
N = int(input())
A = list(map(int, input().split()))

#Aの各値を二進数にした時の桁ごとに配列にまとめる
bit_lis = [0] * 61
for i in range(N):
    tmp = A[i]
    for j in range(61):
        bit_lis[j] += tmp % 2
        tmp = tmp // 2
        if tmp == 0:
            break
        
#各桁について値を計算する
ans = 0
bit_1 = 0
mod = 10 ** 9 + 7
for i in range(61):
    bit_1 = bit_lis[i]
    if bit_1 == 0:
        continue
    ans += (2 ** i) * bit_1 * (N-bit_1) % mod
    ans = ans % mod
print(ans)

### FIXED CODE ###

#標準入力の受け取り
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))

#Aの各値を二進数にした時の桁ごとに配列にまとめる
bit_lis = [0] * 61
for i in range(61):
    bit_lis[i] = np.count_nonzero(A & 1)
    A >>=1
        
#各桁について値を計算する
ans = 0
bit_1 = 0
mod = 10 ** 9 + 7
for i in range(61):
    bit_1 = bit_lis[i]
    if bit_1 == 0:
        continue
    ans += pow(2, i, mod) * bit_1 * (N-bit_1) 
    ans = ans % mod
print(ans)
### BUGGY CODE ###

import sys

n = int(sys.stdin.readline())

power = 1L
for i in range(n):
    power = power * (i+1)

print power % (long(1e+9) + 7)



### FIXED CODE ###

import sys
import math

n = int(sys.stdin.readline())

power = math.factorial(n)

print(power % (int(1e+9) + 7))