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

N, M= map(int, input().strip().split(' '))
A_lst = list(map(int, input().strip().split(' ')))

pyramid = [[] for i in range(len(A_lst)+1)]
pyramid[0] = [0 for i in range(len(A_lst)+1)]
pyramid[1] = A_lst

count = 0

for i in range(2, len(pyramid)):
    for j in range(len(A_lst) - i + 1):
        new_elem = pyramid[i-1][j] + pyramid[i-1][j+1] - pyramid[i-2][j+1]
        pyramid[i].append(new_elem)
        if new_elem % M == 0 and new_elem != 0:
            count += 1

for elem in A_lst:
    if elem % M == 0 and elem != 0:
        count += 1

print(count)

### FIXED CODE ###

from collections import Counter

N, M= [int(x) for x in input().strip().split(' ')]
A = [int(a) for a in input().split()]
A_mod = [0]
s = 0
for elem in A:
    A_mod.append((elem+s) % M)
    s += elem

cnt = Counter(A_mod)
c = 0
for k in cnt.keys():
    if cnt[k] != 1.0:
        c += (cnt[k])*(cnt[k]-1)/2

print(int(c))
### BUGGY CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]

    filled = set()
    for i in range(n-1, -1, -1):
        count = 0
        for j in filled:
            if (j+1) % (i+1) == 0:
                count += 1
        if count % 2 != A[i]:
            filled.add(i)

    return len(filled), [i+1 for i in filled]



if __name__ == '__main__':
    m, output = main()
    if m == -1: print(str(m))
    else:
        print(str(m))
        if m > 0:
            print(' '.join(map(str, output)))

### FIXED CODE ###

# from other person's code
n = int(input())
a = list(map(int, input().split()))
ls = [0]*(n+1)
ans = []
for i in reversed(list(range(n))):
    if sum(ls[::i+1][1:]) % 2 != a[i]:
        ls[i+1] = 1
        ans.append(i+1)
print(sum(ls))
if ans: print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

for _ in range(m):
    if m%n==0:
        print(m//n)
        exit()
    n+=1



### FIXED CODE ###

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

def make_divisors(n,m):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i>=m:
                divisors.append(i)
            if i != n // i:
                if n//i>=m:
                    divisors.append(n//i)

    divisors.sort()
    return divisors

test=make_divisors(m,n)
print(m//min(test))
### BUGGY CODE ###

H, W, A, B = map(int, input().split())
MOD = 10 ** 9 + 7


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * mod_inverse(q, mod) % mod


def d_cmb(n, r, mod):
    return mod_cmb(n + r - 1, r, mod)


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


# aで割りたいときはa^(p-2)をかければよい（pは素数かつmodで使うやつ）
def mod_inverse(a, mod):
    return mod_pow(a, (mod - 2), mod)


n1 = A - 1
r1 = A - 1
n2 = W + (H - A - 1) - 1
r2 = H - A - 1
temp = d_cmb(W, H - A - 1, MOD) * d_cmb(1, 0, MOD)
ans = temp
for _ in range(1, W - B):
    temp = temp * (n1 + 1) * mod_inverse(n1 + 1 - r1, MOD) % MOD
    temp = temp * (n2 - r2) * mod_inverse(n2, MOD) % MOD
    n1 += 1
    n2 -= 1
    ans = (ans + temp) % MOD

print(ans)

### FIXED CODE ###

H, W, A, B = map(int, input().split())
MOD = 10 ** 9 + 7
limit = 2 * 10 ** 5


# modしながらコンビネーションを求める
def mod_cmb(n, r, mod):
    x = fact[n] * fact_inverse[r] % mod
    x = x * fact_inverse[n - r] % mod
    return x


def d_cmb(n, r, mod):
    return mod_cmb(n + r - 1, r, mod)


# modしたa^bを求める
def mod_pow(a, p, mod):
    if p == 0:
        return 1
    elif p % 2 == 1:
        return a * mod_pow(a, p - 1, mod)
    else:
        return (mod_pow(a, p // 2, mod) % mod) ** 2 % mod


fact = [1] * (limit + 1)
fact_inverse = [1] * (limit + 1)

for i in range(1, limit + 1):
    fact[i] = fact[i - 1] * i % MOD

fact_inverse[limit] = mod_pow(fact[limit], MOD - 2, MOD)
for i in reversed(range(1, limit + 1)):
    fact_inverse[i - 1] = fact_inverse[i] * i % MOD

n1 = W
r1 = H - A - 1
n2 = 1
r2 = A - 1
ans = 0
for i in range(W - B):
    ans += d_cmb(n1 - i, r1, MOD) * d_cmb(n2 + i, r2, MOD)
    ans %= MOD

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

def main():
  n, k = map(int, input().split())
  h = [int(n) for n in input().split()]
  dp = [0]*n
  dp[1] = abs(h[1]-h[0])
  for i in range(2, n):
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(i+1,k+1))])  
  print(dp[-1])

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  n, k = map(int, input().split())
  h = [int(n) for n in input().split()]
  dp = [0]*n
  for i in range(1, n):
    dp[i] = min([dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i)])  
  print(dp[-1])

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

#129
H,W=map(int,input().split())
s=[]
c_a=0
for i in range(H):
    s.append(list(input()))

for i in range(H):
    for j in range(W):
        c=0
        
        if s[i][j]!="#":
            c=W+H-1
            if j!=W-1:
                for n in range(1,W-j):
                    if s[i][j+n]=="#":
                        c-=W-j-n
                        break
            if j!=0:
                for n in range(1,j+1):
                    if s[i][j-n]=="#":
                        c-=j-n+1
                        break
            if i!=H-1:
                for m in range(1,H-i):
                    if s[i+m][j]=="#":
                        c-=H-i-m
                        break
            if i!=0:
                for m in range(1,i+1):
                    if s[i-m][j]=="#":
                        c-=i-m+1
                        break
        if c>c_a:
            c_a=c
print(c_a)           


### FIXED CODE ###

import numpy as np
h, w = map(int, input().split())
S = np.array([list(input()) for _ in range(h)]) == "."
U=np.zeros( (h,w),dtype=int )
D=np.zeros( (h,w),dtype=int )
L=np.zeros( (h,w),dtype=int )
R=np.zeros( (h,w),dtype=int )
for i in range(h):
    U[i]=(U[i-1]+1)*S[i]
    D[-i-1]=(D[-i]+1)*S[-i-1]
for j in range(w):
    L[:,j]=(L[:,j-1]+1)*S[:,j]
    R[:,-j-1]=(R[:,-j]+1)*S[:,-j-1]
print(np.max(U+D+R+L)-3)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
ans = 0
for i in range(N):
    try:
        for j in range(i):
            assert(P[i] <= P[j])
        ans += 1
    except AssertionError:
        continue
print(ans)

### FIXED CODE ###

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

N=int(input())
A=[int(i) for i in input().split()]
miss=0
if N%2==0:
    for i in range(int(N/2)):
        if A.count((2*i+1))!=2:
            miss=1
    if miss==1:
        print(0)
    else:
        print(2**int(N/2))
if N%2==1:
    if not 0 in A:
        miss=1
    for i in range(int((N-1)/2)):
        if A.count((2*i+2))!=2:
            miss=1
    if miss==1:
        print(0)
    else:
        print(2**int((N-1)/2))

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
A.sort()
miss=0

if N%2==0:
    for i in range(int(N/2)):    
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+1:
                A.pop(0)
            else:
                miss=1
                break
                
    if miss==1:
        print(0)
    else:
        print(int((2**int(N/2))%(10**9+7)))

else:
    if A[0]!=0:
        miss=1
        A.pop(0)
    else:
        A.pop(0)
    for i in range(int((N-1)/2)):
        if miss==1:
            break
        for j in range(2):
            if A[0]==2*i+2:
                A.pop(0)
            else:
                miss=1
                break
                
    if miss==1:
        print(0)
    else:
        print(int((2**int((N-1)/2))%(10**9+7)))
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
AS = [0]
for i in range(N):
    AS += [AS[i] + A[i]]
AN = []
for i in range(N):
    for j in range(i, N):
        AN += [AS[j + 1] - AS[i]]
selected = [0] * len(AN)
ans = 0
for i in range(100, -1, -1):
    c = 0
    p = ans + 2 ** i
    for x in AN:
        if p & x == p:
            c += 1
            selected[i]
    if c >= K:
        ans += 2 ** i
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
AS = [0]
for i in range(N):
    AS += [AS[i] + A[i]]
AN = []
for i in range(N):
    for j in range(i, N):
        AN += [AS[j + 1] - AS[i]]
ans = 0
for i in range(41, -1, -1):
    c = 0
    p = ans + 2 ** i
    for x in AN:
        if p & x == p:
            c += 1
    if c >= K:
        ans += 2 ** i
print(ans)
### BUGGY CODE ###

s = input()

li_1 = [1] * len(s)

for i in range(10000):
    li_2 = [0] * len(s)
    for j in range(len(s)):
        if s[j] == 'R':
            li_2[j+1] += li_1[j]
        elif s[j] == 'L':
            li_2[j-1] += li_1[j]
    li_1 = li_2

for i in li_1:
    print(i, end=' ')


### FIXED CODE ###

from math import ceil
from math import floor
import itertools

s = input()
n = len(s)
t = []

def output(r_cnt, l_cnt):
    global t
    r_num = ceil(r_cnt/2) + floor(l_cnt/2)
    l_num = ceil(l_cnt/2) + floor(r_cnt/2)
    x = [0 for _ in range(r_cnt + l_cnt)]
    x[r_cnt-1] = r_num
    x[r_cnt] = l_num
    t.append(x)


r_cnt = 0
l_cnt = 0
for i in range(n-1):
    if s[i] == 'R':
        r_cnt += 1
    elif s[i] == 'L':
        l_cnt += 1
    if s[i] == 'L' and s[i+1] =='R' or i == n-2:
        if i == n-2:
            l_cnt += 1
        output(r_cnt, l_cnt)
        r_cnt = 0
        l_cnt = 0


t = list(itertools.chain.from_iterable(t))
for i in t:
    print(i, end=' ')
### BUGGY CODE ###

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

for n in range(N):
  result = result*A[n]

if result >= 1000000000000000001:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
finish = 0
result = 1

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

    if finish == 0:
        print(result)
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
x = 0
for i in range(N):
    for j in range(i):
        if P[i] <= P[j]:
            x += 1
    if x == i:
        ans += 1
    x = 0

print(ans)



        


### FIXED CODE ###

N = int(input())
P = list(map(int,input().split()))
ans = 0
x = P[0]


for i in P:
    if i == 1:
        ans += 1
        x = 1
    else:
        if x >= i:
            ans += 1
            x = i



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

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

for i in range(N):
  p[i]=(1+p[i])/2
  
ans=[0]*(N-K+1)
for i in range(N-K+1):
  ans[i]=sum(p[i:i+K])

print(max(ans))

### FIXED CODE ###

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

for i in range(N):
  p[i]=(1+p[i])/2
  
ans=[0]*(N-K+1)
ans[0]=sum(p[:K])
for i in range(1, N-K+1):
  ans[i]=ans[i-1]-p[i-1]+p[i+K-1]

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

A,B,N=map(int,input().split())
count=0
for i in range(N+1):
    result=int(A*i/B)-(A*int(i/B))
#     print(result)
    if count<result:
        count=result
print(count)

### FIXED CODE ###

A,B,N=map(int,input().split())
x=min(B-1,N)
print(int(A*x/B)-A*int(x/B))
### BUGGY CODE ###

n=int(input())
for i in range(1,n+1):
  ans=0
  for x in range(1,round(i**0.5)+1):
    for y in range(1,round(i**0.5)+1):
      for z in range(1,round(i**0.5)+1):
        if x*x+y*y+z*z+x*y+y*z+z*x==i:
          ans+=1
  print(ans)

### FIXED CODE ###

n=int(input())
A=[0]*(n+1)
a=round(n**0.5)+1
for x in range(1,a):
  for y in range(1,a):
    for z in range(1,a):
      b=x*x+y*y+z*z+x*y+y*z+z*x
      if b<n+1:
        A[b]+=1
for i in range(1,n+1):
  print(A[i])
### BUGGY CODE ###

import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=0
    while len(s)>2:
        ps,cs,f=s[0],s[1],False
        for i,ns in enumerate(s[2:],1):
            if ps!=ns:
                s.pop(i)
                f,t=True,t^1
                break
            ps,cs=cs,ns
        if f is False:
            break
    print('First') if t==1 else print('Second')
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def main():
    s=list(sys.stdin.readline().strip())
    t=0
    while len(s)>2:
        ps,cs,i,f=s[0],s[1],1,False
        for ns in s[2:]:
            if ps!=ns:
                cs,f,t=ns,True,t^1
                s.pop(i)
            else:ps,cs,i=cs,ns,i+1
        if f is False:break
    print('First') if t==1 else print('Second')
if __name__=='__main__':main()
### BUGGY CODE ###

N = int(input())

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

ans = []
[ans.append(A.index(i)+1) for i in range(1,N+1)]
print(*ans)

### FIXED CODE ###

N = int(input())

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

ans = [0]*N
for i,j in enumerate(A):
    ans[j-1]=i+1
print(*ans)
### BUGGY CODE ###

from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    B = [0] * N
    for i in range(N):
        B[i] = (i + 1) - A[i]
        A[i] += i + 1

    d = defaultdict(int)
    C = []
    for i in range(N-1,-1,-1):
        d[B[i]] += 1
        C.append(d.copy())
    C.reverse()
    ans = 0
    for i in range(N-1):
        ans += C[i][A[i]]

    print(ans)

    


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 0
    B = [0] * N
    for i in range(N):
        B[i] = (i + 1) - A[i]
        A[i] += i + 1

    d = defaultdict(int)
    ans = 0
    for i in range(N-1,0,-1):
        d[B[i]] += 1
        ans += d[A[i-1]]

    print(ans)

    


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

a, b, x = [int(x) for x in input().split()]
ans = 0
while True:
    if a > b:
        break
    else:
        if a % x ==0:
            ans += 1
        a += 1
print(ans)

### FIXED CODE ###

a, b, x = [int(x) for x in input().split()]
print((b//x)-((a-1)//x))
### BUGGY CODE ###

S=input()
for i in range(int(input())):
    q=input()
    if q=='1':S=S[::-1]
    else:
        a,f,c=q.split()
        S=c+S if f=='1' else S+c
print(S)        

### FIXED CODE ###

S=input()
b=1
x=''
y=''
for i in range(int(input())):
    q=input()
    if q=='1':b^=1
    else:
        a,f,c=q.split()
        if (int(f)-1)^b:x=c+x
        else:y=y+c
S=x+S+y
print(S if b else S[::-1])
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N):
    ans += i
print(ans)

### FIXED CODE ###

N = int(input())
if N % 2 == 1:
    print(N * (N//2))
else:
    print(N * (N//2-1) + (N//2))
### BUGGY CODE ###

N=int(input())
As=list(map(int,input().split()))
ans=1
for i in range(N):
    ans*=As[i]
print(ans if ans<=int(1e18) else -1)

### FIXED CODE ###

N=int(input())
As=list(map(int,input().split()))
ans=1

if 0 in As:
    print(0)
else:
    for i in range(N):
        ans*=As[i]
        if ans>int(1e18):
            break
    print(ans if ans<=int(1e18) else -1)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=99999999999999999
for i in range(1,n):
  temp1=sum(a[0:i])
  temp2=sum(a[i:n])
  ans=min(ans,abs(temp1-temp2))
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
temp=sum(a)
temp1=a[0]
ans=abs(temp-temp1*2)
for i in range(1,n-1):
  temp1=temp1+a[i]
  ans=min(ans,abs(temp-temp1*2))
print(ans)
### BUGGY CODE ###

n,k,c=map(int, input().split())
s=str(input())

l=[]
r=[]
i=0
j=n-1
while len(l)<k:
    if s[i]=='x':
        i+=1
    if s[i]=='o':
        l.append(i+1)
        i+=c+1
while len(r)<k:
    if s[j]=='x':
        j-=1
    if s[j]=='o':
        r.insert(0,j+1)
        j-=c+1
"""
ここまでで、lには「最速でその日に仕事ができる」
rには「遅くともその日までには仕事しないといけない」
というリストができます。
print(l)
print(r)
"""
for _ in range(len(l)):
    if l[_]==r[_]:
        print(l[_])

### FIXED CODE ###

import sys
n,k,c=map(int, input().split())
s=str(input())

l=[0]*n
r=[0]*n
i=0
j=n-1
cnt=0
while i<n:
    if s[i]=='x':
        i+=1
    if s[i]=='o':
        l[i]=1
        i+=c+1
        cnt+=1
#前から働いていって、必要以上の数働ける形の場合、必須となる日はありません。
if cnt>k:
    sys.exit()
    
while j>=0:
    if s[j]=='x':
        j-=1
    if s[j]=='o':
        r[j]=1
        j-=c+1
"""
ここまでで、lには「最速でその日に仕事ができる」
rには「遅くともその日までには仕事しないといけない」
というリストができます。

print(l)
print(r)
"""
for _ in range(len(l)):
    if l[_] and r[_]:
        print(_+1)
### BUGGY CODE ###

a, b, x = map(int, input().split())
s = 0
for i in range(b-a+1): #aからbの中で最初にxで割り切れる数を探す
    if a % x == 0:
        break
    elif a % x != 0:
            a = a + 1
while (a+x*s) <= b:
    s = s + 1
print(s)

### FIXED CODE ###

a, b, x = map(int, input().split())
#b以下で小さくかつbに最も近いxの倍数 x*i (x*i=0を含める)
i = b // x
#aより小さくかつaに最も近いxの倍数 x*j (x*j=0を含める)
j = (a-1) // x
print(i-j)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from math import ceil
N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0], reverse=True)

ans = 0
for i,xh in enumerate(XH):
    X = xh[0]
    H = xh[1]
    if H > 0:
        num = ceil(H/A)
        for j in range(i,N):
            if XH[j][0] >= X-2*D:
                XH[j][1] -= A*num
            else:
                break
        ans += num
print(ans)


### FIXED CODE ###

#https://atcoder.jp/contests/abc153/submissions/9750027

import sys
input = sys.stdin.readline
from math import ceil
from collections import deque
N,D,A = map(int, input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])
#X,H = map(list, zip(*XH))
q = deque()
d = 0
ans = 0

for x,h in XH:
    while q and q[0][0] < x:    #今見ている座標が既にそれまでの爆弾範囲から外れていたら
        d -= q.popleft()[1]
    h -= d
    if h > 0:
        num = ceil(h/A)
        ans += num
        q.append((x+2*D, num*A))    #(末端, そこまででの爆弾の威力)
        d += num*A
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000) 
 

N,M = map(int,input().split())
a = [list(map(int, input().split())) for _ in range(N-1)]
b = [list(map(int, input().split())) for _ in range(M)]

ans=[0]*N
trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])

for i in b:
    ans[i[0]-1] += i[1]


def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000) 
input=sys.stdin.readline

N,M = map(int,input().split())
ans=[0]*N
a = [list(map(int, input().split())) for _ in range(N-1)]

for _ in range(M):
    e,f = list(map(int, input().split()))
    ans[e-1] += f

trees = {}
for word in a:
    trees.setdefault(word[0], []).append(word[1])
    trees.setdefault(word[1], []).append(word[0])
    

def sumup(ne,parent):
    global ans
    if ne in trees:    
        for k in trees[ne]:
            if k != parent:
                ans[k-1] += ans[ne-1]
                sumup(k,ne)

sumup(1,0)
for i in ans:
    print(i)
### BUGGY CODE ###

a,b,n = map(int,input().split())
max = 0
s = int(b/a)
f = n+1
if b < n:
    f = b+1
for i in range(s,f):
    buf = a*(i%b)-(a*i)%b 
    if buf > max:
        max = buf

print(int(max/b))

### FIXED CODE ###

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

def f(x):
    return int(a*x/b)-a*int(x/b)

w=min(n,b-1) 
ma=f(w)
print(ma)
### BUGGY CODE ###

n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n

def unite(x, y):
  global clusterI
  CX = clusterI[x]
  CY = clusterI[y]
  if CX != CY:
    if CX < CY:
      CX, CY = CY, CX
    clusterN[CX] += clusterN[CY]
    clusterI = [CX if clusterI[i] == CY else clusterI[i] for i in range(n)]

for _ in range(m):
  a, b = map(int, input().split())
  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):
  a, b = map(int, input().split())
  if clusterI[a-1] == clusterI[b-1]:
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[clusterI[i]] - 1 for i in range(n)]
print(*out)

### FIXED CODE ###

n, m, k = map(int, input().split())
clusterN = [1] * n
clusterI = list(range(n))
out = [0] * n
def generateC(x):
  if clusterI[x] != x:
    minI = generateC(clusterI[x])
    clusterI[x] = minI
    return minI
  else:
    return x

def unite(x, y):
  CX = generateC(x)
  CY = generateC(y)
  if CX != CY:
    if CX > CY:
      CX, CY = CY, CX
      x, y = y, x
    clusterN[CX] += clusterN[CY]
    clusterI[CY] = CX
    generateC(y)
    

for _ in range(m):
  a, b = map(int, input().split())

  unite(a-1, b-1)
  out[a-1] -= 1
  out[b-1] -= 1

for _ in range(k):

  a, b = map(int, input().split())
  if generateC(a-1) == generateC(b-1):
    out[a-1] -= 1
    out[b-1] -= 1
out = [out[i] + clusterN[generateC(i)] - 1 for i in range(n)]
print(*out)
### BUGGY CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))

event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop

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

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

dp = [10 ** 9] * n
dp[0] = 0

a = min(n, k)
for i in range(1, n):
    dp[i] = min(dp[i], dp[i-1] + abs(h[i] - h[i-1]))
    
    for j in range(2, a+1):
        dp[i] = min(dp[i], dp[i-j] + abs(h[i] - h[i-j]))

print(dp[-1])

### FIXED CODE ###

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

dp = [10 ** 9] * n
dp[0] = 0

for i in range(1, n):
    j = max(0, i - k)
    hi = h[i]
    dp[i] = min(dpj + abs(hi - hj) for dpj, hj in zip(dp[j:i], h[j:i]))

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

n, a, b = map(int, input().split())
if n == 2 and a == 1 and b==2:
    print(0)
    exit()

def nCr_mod_p(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = n + 1  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p), 0! = 1! = 1
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p), 0! = 1! = 1
inv = [0, 1]  # inv[n] = n^(-1) mod p, 0! = 1　だけど便宜上inv[0]=0にしてる

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


ans = 2**n - 1- nCr_mod_p(n, a, p) - nCr_mod_p(n, b, p)
if ans < 0:
    print(0)
else:
    print(ans%p)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
mod = p = 10**9+7
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

n, a, b = map(int, input().split())
nCa= 1
nCb= 1
for i in range(b):
    nCb = (nCb%p * (n-i)%p)%p
    nCb = nCb * mod_inv(i+1, p)
    if i+1 == a:
        nCa = nCb

ans = 2**n - 1- nCa%p - nCb%p
if ans < 0:
    print(0)
else:
    print(int(ans%p))