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

def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    SENTINEL = max(A)+1
    L = A[left:mid]+[SENTINEL]
    R = A[mid:right]+[SENTINEL]
    i = 0
    j = 0
    c = 0
    for k in range(left, right):
        c += 1
        if L[i]<=R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return c

def mergesort(A, left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(A, left, mid)
        c += mergesort(A, mid, right)
        c += merge(A, left, mid, right)
    return c

n = f()
S = f2()

c = mergesort(S, 0, n)
for e in S:
    print e,
print
print c

### FIXED CODE ###

def f():
    return int(raw_input())
def f2():
    return map(int, raw_input().split())

def merge(left, mid, right):
    L = S[left:mid]
    R = S[mid:right]
    lp, rp, xp = 0, 0, 0
    a, b = L[0], R[0]
    c = right - left
    x = [0] * c
    flg = True
    while flg:
        while flg and a <= b:
            x[xp] = a
            lp += 1
            xp += 1
            try:
                a = L[lp]
            except:
                for e in R[rp:]:
                    x[xp] = e
                    xp += 1
                flg = False
        while flg and a >= b:
            x[xp] = b
            rp += 1
            xp += 1
            try:
                b = R[rp]
            except:
                for e in L[lp:]:
                    x[xp] = e
                    xp += 1
                flg = False
    S[left:right] = x
    return c

def mergesort(left, right):
    c = 0
    if left + 1 < right:
        mid = (left + right)/2
        c += mergesort(left, mid)
        c += mergesort(mid, right)
        c += merge(left, mid, right)
    return c

global S
n = f()
S = f2()

c = mergesort(0, n)
print " ".join(map(str,S))
print c
### BUGGY CODE ###

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

is_true = False
for i in range(10**7):
    if a == int(i * 0.08) and b == int(i * 0.1):
        is_true = True
        break
if is_true:
    print(i)
else:
    print('-1')


### FIXED CODE ###

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

is_true = False
for i in range(10**7):
    if a == int(i * 0.08) and b == int(i * 0.1):
        is_true = True
        break
if is_true:
    print(i)
else:
    print('-1')
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())

l_list = []
r_list = []

s_count = [0]
for i in range(len(S) - 1):
    if S[i:i+2] == 'AC':
        s_count.append(1)
    else:
        s_count.append(0)
     

for x in range(Q):
    l, r = map(int, input().split())
    sub_count = s_count[l:r]
    print(sum(sub_count))
    
    




### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())

l_list = []
r_list = []

s_count = [0]
for i in range(len(S) - 1):
    if S[i:i+2] == 'AC':
        s_count.append(1)
    else:
        s_count.append(0)
#print(s_count)

n_count = []
n_sum = 0
for n in s_count:
    n_sum = n_sum + n
    n_count.append(n_sum)

#print(n_count)


for x in range(Q):
    l, r = map(int, input().split())
    ans = n_count[r-1] - n_count[l-1]
    print(ans)
### BUGGY CODE ###

def pow_r(x, n):
    if n == 0:  # exit case
        return 1
    if n % 2 == 0:  # standard case ① n is even
        return pow_r(x ** 2, n // 2)
    else:  # standard case ② n is odd
        return x * pow_r(x ** 2, (n - 1) // 2)


x = int(input())
for a in range(-1000, 1000):
    for b in range(-1000, 1000):
        if x == (pow_r(a, 5)) - (pow_r(b, 5)):
            print(a, b)
            exit()



### FIXED CODE ###

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)


x = int(input())
for a in range(-100, 1000):
    for b in range(-100, 1000):
        if x == (pow_r(a, 5)) - (pow_r(b, 5)):
            print(a, b)
            exit()
### BUGGY CODE ###

#feel like this is to easy

def read_input():
  n = int(input())
  a = []
  for i in range(n):
    a.append(int(input()))
  return n,a

def main():
  n,a = read_input()
  sheet = []
  for item in a:
    if item not in sheet:
      sheet.append(item)
    else:
      sheet.pop(sheet.index(item))
  print(len(sheet))
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

#feel like this is to easy

def read_input():
  n = int(input())
  a = []
  for i in range(n):
    a.append(int(input()))
  return n,a

def TLE():
  n,a = read_input()
  sheet = []
  for item in a:
    if item not in sheet:
      sheet.append(item)
    else:
      sheet.pop(sheet.index(item))
  print(len(sheet))
  
def TLE2():
  n,a = read_input()
  items = list(set(a))
  count = 0
  for item in items:
    if a.count(item)%2 != 0:
      count += 1
  print(count)

def main():
  n,a = read_input()
  a.sort()
  items = list(set(a)).sort()
  t = 1
  count = 0
  for i in range(len(a)):
    if i+1 == len(a):
      count += t%2
      break
    if a[i] == a[i+1]:
      t += 1
    else:
      count += t%2
      t = 1
  print(count)

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

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

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    (n, ) = [int(e) for e in lines[0].split(' ')]

    return (n, )


def solve(n, ):

    
    a = []
    tmp = n
    while tmp > 0:
        q = tmp // 10
        r = tmp % 10
        a.append(r)
            
        tmp = q

    a.reverse()
    if debug:
        log("a=%s" % a)

    result = 'No' 
    if sum(a) % 9 == 0:
        result = 'Yes'


    return result 


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
	

### FIXED CODE ###

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

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        for line in sys.stdin:
            lines.append(line.strip())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]

    n = lines[0]

    return (n, )


def solve(n, ):

    
    total = sum([int(e) for e in n])

    result = 'No' 
    #if sum(a) % 9 == 0:
    if total % 9 == 0:
        result = 'Yes'


    return result 


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        for r in result:
            print("%s" % r, sep='')
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()
### BUGGY CODE ###

def main():
    n, k= map(int, input().split())
    a = list(map(int, input().split()))
    pre = -1
    for i in range(n-k+1):
        now = 1
        for b in a[i:k+i]:
            now *= b
        if pre == -1:
            pre = now
            continue
        if pre < now:
            print('Yes')
        else:
            print('No')
        pre = now
    
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k= map(int, input().split())
    a = list(map(int, input().split()))

    for i in range(1, n-k+1):
        if a[i - 1] < a[k+ i -1]:
            print('Yes')
        else:
            print('No')
            
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s=input()
li=list(input())

min = 100000000

for index, i in enumerate(li):
  a = 0
  
  w1 = li[0:index].count('W')
  s1 = li[index + 1:].count('E')

  a = w1 + s1
    
  if min > a:
    min = a
    
print(min)

### FIXED CODE ###

from itertools import accumulate
 
n = int(input())
s = [c == 'W' for c in input()]
l = accumulate([0] + s[:-1])
r = accumulate([0] + [not c for c in reversed(s[1:])])
print(min(e + w for e, w in zip(l, reversed(list(r)))))
### BUGGY CODE ###

from sys import setrecursionlimit


def f(u, l, r, a, dp):
    if l > r:
        return 0
    t = dp[l][r]
    if t is not None:
        return t
    if u == 0:
        t0 = f(u ^ 1, l + 1, r, a, dp) + a[l]
        t1 = f(u ^ 1, l, r - 1, a, dp) + a[r]
        if t0 > t1:
            result = t0
        else:
            result = t1
    else:
        t0 = f(u ^ 1, l + 1, r, a, dp) - a[l]
        t1 = f(u ^ 1, l, r - 1, a, dp) - a[r]
        if t0 < t1:
            result = t0
        else:
            result = t1
    dp[l][r] = result
    return result


setrecursionlimit(1000000)

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

dp = [[None] * N for _ in range(N)]
print(f(0, 0, N - 1, a, dp))


### FIXED CODE ###

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

dp = [[0] * (N + 1) for _ in range(N + 1)]
for l in range(1, N + 1):
  for i in range(N + 1 - l):
    j = i + l
    if (N - l) % 2 == 0:
      dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
    else:
      dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])
print(dp[0][N])
### BUGGY CODE ###

def solve():
    H, N = map(int, input().split())
    
    INF = 10 ** 9
    dp = [INF] * (10 ** 7)
    dp[0] = 0

    for _ in range(N): 
        a, b = list(map(int, input().split()))
        for i in range(H+1):
            if dp[i] == INF: continue
            dp[i+a] = min(dp[i+a], dp[i] + b)
            
    return min(dp[H:])

print(solve())

### FIXED CODE ###

import numpy as np

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

A = []
B = []
for i in range(N):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)

A = np.array(A)
B = np.array(B)

dp = np.full((H+1), np.inf)
dp[0] = 0

def solve():
    for i in range(1, H + 1):
        dp[i] = np.amin(dp[np.maximum(i - A , 0)] + B)
    return int(dp[H])

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

def dfs_rec(start,prev):
    ans[start] = cnt[start]
    if start!=0:
        ans[start] +=ans[prev]
    for node in tree[start]:
        if node != prev:
            dfs_rec(node,start)
    return
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,q = map(int,input().split())
tree = [[] for i in range(n)]
cnt = [0] *n
ans = [0] *n

for i in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for i in range(q):
    p,x = map(int,input().split())
    cnt[p-1]+=x
dfs_rec(0,0)
print(*ans)


### FIXED CODE ###

def main():
    def dfs_rec(start,prev):
        ans[start] = cnt[start]
        if start!=0:
            ans[start] +=ans[prev]
        for node in tree[start]:
            if node != prev:
                dfs_rec(node,start)
        return
    import sys
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline

    n,q = map(int,input().split())
    tree = [[] for i in range(n)]
    cnt = [0] *n
    ans = [0] *n

    for i in range(n-1):
        a,b = map(int,input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)
    for i in range(q):
        p,x = map(int,input().split())
        cnt[p-1]+=x
    dfs_rec(0,0)
    print(*ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
ln = list(input())
sum_min = n - 1
for i in range(n):
    # E->Wに向く人数
    #ln[i+1:n].count('E')
    # W->Eに向く人数
    #ln[0:i].count('W')
    sum_min = min(sum_min, ln[i+1:n].count('E') + ln[0:i].count('W'))

print(sum_min)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
ln = list(map(int, input().replace('W', '0 ').replace('E', '1 ').split()))

# 先頭だけ先に計算（do-while相当）
w_sum = 0                           # 西側で振り返る人
sum_min = e_sum = sum(ln) - ln[0]   # 東側で振り返る人

for i in range(1, n-1):
    #sum_min = min(sum_min, sum(ln[i+1:n]) + (i - sum(ln[0:i])))
    w_sum += 1 if ln[i-1] == 0 else 0
    e_sum -= ln[i]
    sum_min = min(sum_min, w_sum + e_sum)

# 末尾も個別に計算
else:
    w_sum += 1 if ln[n-1] == 0 else 0
    sum_min = min(sum_min, w_sum)


print(sum_min)
### BUGGY CODE ###

import itertools

N = int(input())
S = input()

r = S.count('R')
g = S.count('G')
b = S.count('B')


cnt = r * g * b

sum = 0
for i in range(0,N-2):
    for j in range(i,N-1):
        for k in range(j,N):
            if j - i == k - j:
                if (S[i] != S[j]) and (S[i] != S[k] and S[j] != S[k]):
                    sum += 1
                    break
                
cnt -= sum

print(cnt)

### FIXED CODE ###

import itertools
from collections import Counter

N = int(input())
S = input()

C=Counter(S)
r = C['R']
g = C['G']
b = C['B']


cnt = r * g * b

for i in range(0,N-2):
    for j in range(i,N-1):
        k = j + j - i
        if k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                cnt -= 1

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

import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    S = list(inputs[0])
    max_len = None
    for i, c1 in enumerate(S):
        if c1 == "A":
            end_z = None
            for j, c2 in enumerate(S[i:]):
                if c2 == "Z":
                    end_z = j + i
            if end_z is not None:
                l = end_z - i
                if max_len is None or max_len < l:
                    max_len = l
    return max_len + 1


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


### FIXED CODE ###

import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    S = list(inputs[0])
    N = len(S)
    start = None
    for i in range(N):
        if S[i] == 'A':
            start = i
            break
    end = None
    for i in reversed(range(N)):
        if S[i] == 'Z':
            end = i
            break
    return end - start + 1


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)
### BUGGY CODE ###

N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]

arr = [-1]+arr+[N+1]
#from math import factorial
from functools import reduce
count = 0
for i in range(0,len(arr)-1):
    start,end = arr[i],arr[i+1]
    span = end - start - 2 # the first step is taken by a certain step (with no choice)
    if span < 0:
        count = 0 # impossible
        break 
    nptn = int(span/2)
    regional_count = 0

    for k in range(0,nptn+1):
        #regional_count += factorial(span-k) // factorial(k) // factorial(span-2*k)
        mul = lambda a,b: a*b
        regional_count += reduce(mul, range(span-k,k,-1),1) // reduce(mul, range(1,span-2*k+1),1)
    
    if count == 0:
        count += regional_count
    else:
        count *= regional_count
print(count % 1000000007)

### FIXED CODE ###

N,M = map(int, input().split())
arr = [int(input()) for _ in range(0,M)]
MOD = 10**9 + 7
stairs = [True for _ in range(0,N+1)]
for x in arr:
    stairs[x] = False

dp = [0 for _ in range(0,N+1)]

dp[0] = 1 if 0 not in arr else 0
dp[1] = 1 if 1 not in arr else 0

for i in range(2,N+1):
    if dp[i-1] == 0 and dp[i-2] == 0:
        break
    if stairs[i-1]: dp[i] += dp[i-1]
    if stairs[i-2]: dp[i] += dp[i-2]

    dp[i] %= MOD

print(dp[-1] % MOD)
### BUGGY CODE ###

S = list(input())
S.reverse()
amari = []
A = 0
for i in range(len(S)):
    a = (int(A) + int(S[i]) *(10 ** i)) % 2019
    amari.append(a)
    A = a
c = 0
if 0 in amari:
    c += 1
print(c + len(amari) - len(set(amari)))


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]


def main():
    S = input()[::-1] # 入力文字列を逆順で格納
    counts = [0] * 2019
    counts[0] = 1
    num, d = 0, 1

    for char in S:
        num = num + int(char) * d
        num = num % 2019
        d = d * 10
        d = d % 2019
        counts[num] += 1 #余りの数の番号のリストに+1していくことでカウント

    ans = 0
    for cnt in counts:
        ans += cnt * (cnt - 1) // 2
    print(ans)

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

N = int(input())
def triplets(n):
  counter = 0
  lower = 1
  upper = round(n**0.5)
  for x in range(1, upper+1):
    y_upper = round(0.5*((4*n-3*x**2)**0.5-x))
    for y in range(1, y_upper+1):
      root = (4*n-3*x**2-3*y**2-2*x*y)**0.5
      z = 0.5*(root-x-y)
      if z%1==0 and z>0:
        counter += 1
  return counter
for m in range(1, N+1):
  print(triplets(m))

### FIXED CODE ###

N = int(input())
l = [0]*N
upper = round((N-1)**0.5-1)
for x in range(1, upper+1):
    for y in range(1, upper + 1):
        for z in range(1, upper + 1):
            tmp = x**2+y**2+z**2+x*y+y*z+z*x
            if tmp < N+1:
                l[tmp-1]+=1
for x in l:
    print(x)
### BUGGY CODE ###

def sigma(n):
    return sum([i for i in range(n+1)])
 
def main():
    N, K = map(int, input().split(' '))
    p = list(map(int, input().split(' ')))
 
    max_value = 0
    for i in range(N-K+1):
        sum_ = sum(p[i:i+K])
        if sum_ > max_value:
            max_value = sum_
            max_list = p[i:i+K]
 
    expected = 0
    for v in max_list:
        expected += sigma(v) / v
 
    print(expected)
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    p = list(map(int, input().split()))

    p = [(p_i+1)/2 for p_i in p]
    ans = 0
    for i in range(N-K+1):
        if i == 0:
            sum_ = sum(p[i:i+K])
        else:
            sum_ = sum_ + p[i+K-1] - p[i-1]
        ans = max(ans, sum_)

    print(ans)

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

import numpy as np

n,m = map(int,input().split())
list_a = list(map(int,input().split()))
#b_list = list(map(int,input().split()))
#print(" ".join(map(str,c_list)))
check = 0
list_a.sort(reverse = True)
for i in range(m):
    list_a[np.argmax(list_a[0:6])] = list_a[np.argmax(list_a[0:6])] //2
    check += 1
    if check == 5:
        list_a.sort(reverse = True)
        check = 0
print(sum(list_a))


### FIXED CODE ###

import sys
n,m = map(int,input().split())
lst_a = list(map(int,input().split()))
temp = 0
cnt = 0
fin = 0
loop = 0
debug = 0
temp2 = 0
if n == 1:
    for i in range(m):
        lst_a[0] //= 2
    print(lst_a[0])
    sys.exit()
while debug < 10:
    loop = 0
    #temp2 = temp
    temp = 0
    lst_a.sort(reverse=True)
    while loop < n-1:
        lst_a[loop] //= 2
        cnt += 1
        temp = max(temp,lst_a[loop])
        if cnt == m:
            #print(lst_a)
            print(sum(lst_a))
            sys.exit()
        if temp > max(lst_a[loop],lst_a[loop + 1]):
            break
        if lst_a[loop + 1] > lst_a[loop]:
            loop += 1
        
        
        
"""        if lst_a[loop] >= max(lst_a[loop + 1],temp):
            lst_a[loop] //= 2
            temp = max(lst_a[loop],lst_a[loop+1])
            cnt += 1
            if cnt == m:
                print(sum(lst_a))
                sys.exit()
            if temp > lst_a[loop + 1]:
                break
            
            
        loop += 1
    
    #debug += 1
print(lst_a[99999])
# print(temp)
# print(cnt)
# print(lst_a)
# print(sum(lst_a))
"""
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
print(1 + sum([int(P[i] <= min(P[:i])) for i in range(1, N)]))


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
Q = []
m = 10**17
for p in P:
    m = min(m, p)
    Q.append(m)
c = 0
for x, y in zip(P, Q):
    if x <= y:
        c += 1
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate
n = int(input())
A = [0] + list(map(int, input().split()))
B = tuple(accumulate(A))
dp = [[-1]*(n+1) for _ in range(n+1)]
def f(i, j):
  if i == j:
    return 0
  if dp[i][j] != -1:
    return dp[i][j]
  if j-i == 1:
    dp[i][j] = A[i]+A[j]
    return dp[i][j]
  res = float("inf")
  for m in range(i, j):
    res = min(res, f(i,m)+f(m+1,j)+(B[j]-B[i-1]))
  dp[i][j] = res
  return res
ans = f(1, n)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from itertools import accumulate
n = int(input())
A = [0] + list(map(int, input().split()))
B = tuple(accumulate(A))
dp = [[-1]*(n+1) for _ in range(n+1)]
def f(i, j):
  if i == j:
    return 0
  if dp[i][j] != -1:
    return dp[i][j]
  if j-i == 1:
    dp[i][j] = A[i]+A[j]
    return dp[i][j]
  res = float("inf")
  for m in range(i, j):
    res = min(res, f(i,m)+f(m+1,j)+(B[j]-B[i-1]))
  dp[i][j] = res
  return res
ans = f(1, n)
print(ans)
### BUGGY CODE ###

n = int(input())
P = list(map(int,input().split()))
ans = 0
for i in range(n):
    P2 = P[0:i+1]
    m = min(P2)
    if P[i] <= m:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
P = list(map(int,input().split()))
ans = 0
mi = P[0]
for i in range(n):
    if P[i] <= mi:
        mi = P[i]
        ans += 1
print(ans)
### BUGGY CODE ###

import math
def comb(a,b,p):
    if b==0:
        return 1
    elif b%2==0:
        d=comb(a,b//2,p)
        return (d*d)%p
    else:
        return (a*comb(a,b-1,p))%p

n,a,b=map(int,input().split())
num=10**9+7

l=[]
for i in [a,n-a,b,n-b]:
    temp=1
    for j in range(1,i+1):
        temp*=comb(j,num-2,num)

    l.append(temp%num)

ans = comb(2,n,num)-1-((math.factorial(n)%num)*(l[0]*l[1]+l[2]*l[3]))%num
print(ans)
#print(l)


### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
def comb(n,k):
    temp=1
    k=min(k,n-k)
    for i in range(1,k+1):
        temp=temp*pow(i,mod-2,mod)
        temp=temp*(n-i+1)%mod

    return temp%mod
#二分累乗法を勉強する
ans=pow(2,n,mod)-1-comb(n,a)-comb(n,b)
print(ans%mod)
### BUGGY CODE ###

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

cntL = [0] * (M + 1)
for l in L:
    cntL[l] += 1

accCntL = [0] * (M + 2)
for i in range(1, M + 2):
    accCntL[i] = accCntL[i - 1] + cntL[i - 1]

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L):
        if i == j:
            continue

        right = min(A + B, M + 1)
        left = abs(A - B) + 1
        ans += accCntL[right] - accCntL[left]

        if left <= A < right:
            ans -= 1
        if left <= B < right:
            ans -= 1

print(ans // 6)


### FIXED CODE ###

from bisect import bisect_left

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

ans = 0
for i, A in enumerate(L):
    for j, B in enumerate(L[i + 1:], start=i + 1):
        right = bisect_left(L, A + B)
        ans += right - j - 1

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

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

# dp[i] := 足場iに来るのにかかる最小のコスト
INF = 10**18
dp = [INF for _ in range(N)]
dp[0] = 0
for i in range(1, N):
    for j in range(1, K + 1):
        idx = i - j
        if idx < 0:
            continue
        v = dp[idx] + abs(H[i] - H[idx])
        dp[i] = min(dp[i], v)
# print('dp', dp)
ans = dp[-1]
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
H = [H[0]] * K + H

# dp[i] := 足場iに来るのにかかる最小のコスト
INF = 10**18
dp = [INF] * (K + N)
dp[0] = 0
for i in range(K, N + K):
    h = H[i]
    dp[i] = min(x + abs(y - h) for x, y in zip(dp[i - K:i], H[i - K:i]))
#     for j in range(1, K + 1):
#         v = dp[i - j] + abs(H[i] - H[i - j])
#         dp[i] = min(dp[i], v)
# print('dp', dp)
ans = dp[-1]
print(ans)