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

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    S = S[::-1]
    for i in range(l):
        if S[i] == '?':
            for ques in range(10):
                k = (ques * mul) % 13
                for j in range(13):
                    dp[i+1][(j+k)%13] += dp[i][j]
        else:
            k = (int(S[i]) * mul) % 13
            for j in range(13):
                dp[i+1][(j+k)%13] += dp[i][j]

        mul *= 10
    # print(dp[-1])
    print(dp[-1][5] % MOD)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def SMI(): return input().split()
def SLI(): return list(input())

def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')

# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    S = SLI()
    l = len(S)
    MOD = 1000000007
    dp = [[0]*13 for _ in range(l+1)]
    dp[0][0] = 1
    mul = 1
    for i in range(l):
        s = S[-(i + 1)]
        if s == '?':
            for q in range(10):
                for j in range(13):
                    dp[i+1][(q*mul + j)%13] += dp[i][j]
                    dp[i+1][(q*mul + j)%13] %= MOD
        else:
            for j in range(13):
                k = int(s)
                dp[i+1][(k*mul + j)%13] += dp[i][j]
                dp[i+1][(k*mul + j)%13] %= MOD

        mul = mul * 10 % 13
    # print(dp[-1])
    print(dp[-1][5] % MOD)

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

def rle(t):
    tmp2, num, ans = t[0], 1, []
    for i in range(1, len(t)):
        if tmp2 == t[i]:
            num += 1
        else:
            ans.append([tmp2, num])
            tmp2 = t[i]
            num = 1
    ans.append([tmp2, num])
    return ans


S = input()

s = list(map(str, S))
l = rle(S)
count = 0
while True:
    count2 = 0
    for j in range(len(s) - 1):
        if s[j] == 'B' and s[j+1] == 'W':
            s[j] = 'W'
            s[j+1] = 'B'
            count += 1
            count2 += 1
    if count2 == 0:
        break
print(count)


### FIXED CODE ###

def rle(t):
    tmp2, num, ans = t[0], 1, []
    for i in range(1, len(t)):
        if tmp2 == t[i]:
            num += 1
        else:
            ans.append([tmp2, num])
            tmp2 = t[i]
            num = 1
    ans.append([tmp2, num])
    return ans


S = input()

s = list(map(str, S))
l = rle(S)
now = [[], [], []]
for i in range(len(S)):
    if S[i] == 'B':
        now[0].append(i)
for j in range(len(now[0])):
    now[1].append(len(S) - len(now[0]) + j)
    now[2].append(now[1][j] - now[0][j])
print(sum(now[2]))
### BUGGY CODE ###

import numpy as np
a = int(input())
num = np.array(list(map(int,input().split())))
for i in range(1,a+1):
    print(len(num[num==i]))

### FIXED CODE ###

import collections
a = int(input())
num = list(map(int,input().split()))
c = collections.Counter(num)
list(map(lambda x: print(c[x]), range(1,a+1)))
### BUGGY CODE ###

N=int(input())
P=list(map(int, input().split()))
X=[0]+list(map(int, input().split()))
ko=[[] for _ in range(N+1)]
for i, p in enumerate(P, 2):
  ko[p].append(i)
  
def f(p):
  n=len(ko[p])
  if n==0:
    return X[p], 0
  
  dp=[[float('inf')]*5001 for _ in range(n+1)]
  dp[0][0]=0
  for i, c in enumerate(ko[p], 1):
    a, b=f(c)
    for j in range(a, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-a]+b)
    for j in range(b, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-b]+a)
      
  out=min(dp[-1][:X[p]+1])
  if out==float('inf'):
    print('IMPOSSIBLE')
    exit()
  elif out>X[p]:
    return out, X[p]
  else:
    return X[p], out
  
print('POSSIBLE') if min(f(1))<=X[1] else print('IMPOSSIBLE')

### FIXED CODE ###

N=int(input())
P=list(map(int, input().split()))
X=[0]+list(map(int, input().split()))
ko=[[] for _ in range(N+1)]
for i, p in enumerate(P, 2):
  ko[p].append(i)
  
def f(p):
  n=len(ko[p])
  if n==0:
    return X[p], 0
  
  dp=[[float('inf')]*5001 for _ in range(n+1)]
  dp[0][0]=0
  for i, c in enumerate(ko[p], 1):
    a, b=f(c)
    for j in range(a, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-a]+b)
    for j in range(b, 5001):
      dp[i][j]=min(dp[i][j], dp[i-1][j-b]+a)
      
  out=min(dp[-1][:X[p]+1])
  if out==float('inf'):
    print('IMPOSSIBLE')
    exit()
  elif out>X[p]:
    return out, X[p]
  else:
    return X[p], out
  
print('POSSIBLE') if min(f(1))<=X[1] else print('IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())
ls = [sorted(list(input())) for i in range(N)]

hoge = 0
for i in range(N):
    hoge+=ls[i:N].count(ls[i])-1
print(hoge)

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input().rstrip())) for _ in range(N)]

memo = {}
for x in s:
    if x not in memo:
        memo[x] = 1
    else:
        memo[x] += 1

print(sum(x*(x-1)//2 for x in memo.values()))
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort(reverse=True)
    u = 2 *  A[0]
    l = 0
    k = []
    jj = 0
    while True:
        jj += 1
        m = (u + l)//2
        t = 0
        s = N
        p = 0
        for i in range(N):
            for j in reversed(range(s)):
                if A[i] + A[j] >= m:
                    if A[i] + A[j] == m:
                        p += 1
                    k.append(j)
                    t += j+1
                    s = j+1
                    break
        if (t >= M and t - p <= M) or t == M:
            break
        elif t > M:
            l = m
        else:
            u = m
        k = []
    r = 0   
    s = N
    B = []
    tmp = 0
    for i in A:
        tmp += i
        B.append(tmp)
    for i in range(len(k)):
        r += (k[i]+1) * A[i] + B[k[i]]
    return r - (t - M) * m
    
print(main())
    


### FIXED CODE ###

import bisect
def judge(k, N, A):
    t = 0
    for i in A:
        j = bisect.bisect_left(A, k - i)
        t += N - j
    return t
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    t = A[-1] * 2
    b = 0
    X = None
    while t - b > 1:
        m = (t + b)//2
        i = judge(m, N, A)
        if i == M:
            X = m
            break
        if i > M:
            ip = judge(m + 1, N, A)
            if ip == M:
                X = m + 1
                break
            if ip < M:
                X = m
                break
            b = m + 1
        if i < M:
            im = judge(m - 1, N, A)
            if im >= M:
                X = m - 1
                break
            t = m - 1
    if X is None:
        X = b
    B = []
    tmp = 0
    for i in reversed(range(N)):
        tmp += A[i]
        B.append(tmp)
    B.reverse()
    r = 0
    tot = 0
    for i in reversed(range(N)):
        j = bisect.bisect_left(A, X - A[i])
        tot += N - j
        if j == N:
            break
        r += A[i] * (N - j) + B[j]
    return r - (tot - M) * X
print(main())
### BUGGY CODE ###

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

    divisors.sort()
    return len(divisors)

n = int(input())

ans = 0
for i in range(1, n+1):
    ans += i * make_divisors(i)
    
print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
for x in range(1, n+1):
    y = n // x
    ans += y * (y+1) * x // 2
    
print(ans)
### BUGGY CODE ###

import math
N = int(input())
for i in range(1,N+1):
    ans = 0
    cnt = 0
    for x in range(1,int(math.sqrt(i))+1):
        for y in range(1,x+1):
            for z in range(1,y+1):
                if((x**2 + y**2 + z**2 + x*y + y*z + z*x) == i):
                    if(x*y*z == 1):
                        ans += 1
                    else:
                        cnt += 1
                    break
    ans += cnt*3
    print(ans)


### FIXED CODE ###

import math
N = int(input())
ans_list = [0 for i in range(N+1)]
for x in range(1,int(math.sqrt(N))+1):
    for y in range(1,int(math.sqrt(N))+1):
        for z in range(1,int(math.sqrt(N))+1):
            f = x**2 +y**2 +z**2 +x*y +y*z + z*x
            if(f<=N):
                ans_list[f] += 1

for i in range(1,N+1):
    print(ans_list[i])
### BUGGY CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      t = 0
      cou += 1
      break
    r += 1
    
              
print(cou)

### FIXED CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

A = [0 for _ in range(N)]
friend = [[] for _ in range(N)]
block = [[] for _ in range(N)]
answer = [[] for _ in range(N)]

for a, b in AB:
  friend[a-1].append(b)
  friend[b-1].append(a)

for c, d in CD:
  block[c-1].append(d)
  block[d-1].append(c)

def search(root, fs, check):
  for f in fs:
    if check[f-1] != 0 or f == root:
      continue
    else:
      check[f-1] = 1
    search(root, friend[f-1], check)
    if f not in block[root-1] and f not in friend[root-1] and f != root:
      if f not in answer[root-1]:
        answer[root-1].append(f)

for i in range(N):
  search(i+1, friend[i], [0 for _ in range(N)])

for i in range(N):
  A[i] = len(answer[i])

print(' '.join(map(str, A)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

par = [n+1 for n in range(N)]
rank = [0 for _ in range(N)]
size = [1 for _ in range(N)]

# 木の根を求める
def find(x):
  if par[x-1] != x:
    par[x-1] = find(par[x-1])
  return par[x-1]
# x, y の属する集合を併合
def unite(x, y):
  rx = find(x)
  ry = find(y)
  if rx == ry:
    return
  if rank[rx-1] < rank[ry-1]:
    rx, ry = ry, rx
  par[ry-1] = rx
  size[rx-1] += size[ry-1]
  if rank[rx-1] == rank[ry-1]:
    rank[rx-1] += 1
# x, y が同じ集合に属するか否か
def same(x, y):
  return find(x) == find(y)
def getsize(x):
  return size[find(x)-1]

friends = [0 for _ in range(N)]
for A, B in AB:
  unite(A, B)
  friends[A-1] += 1
  friends[B-1] += 1

ans = [0 for _ in range(N)]

for n in range(N):
  ans[n] = getsize(n+1) - friends[n] -1

for C, D in CD:
  if same(C, D):
    ans[C-1] -= 1
    ans[D-1] -= 1
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
s = 0
MOD = 10**9 + 7
while len(a) != 1:
    firstnum = a.pop()
    for i in a:
        b = (firstnum * i)%MOD
        s += b
s %= MOD
print(s)

### FIXED CODE ###

n = int(input())
mod = 10**9 + 7
a = [int(x)%mod for x in input().split()]
allsum = sum(a)
s = 0
for i in range(n):
    allsum = allsum -a[i]
    s += a[i]*allsum
print(s%mod)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
CB = [0]*(M)
for i in range(M):
    b, c = map(int, input().split())
    CB[i] = (c, b)

A.sort()
CB = list(reversed(sorted(CB)))

ind = 0
for i in range(M):
    (c, b) = CB[i]
    for _ in range(b):
        if ind >= N:
            break
        if A[ind] < c:
            A[ind] = c
            ind += 1
print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
CB = [0]*(M)
for i in range(M):
    b, c = map(int, input().split())
    CB[i] = (c, b)

A.sort()
CB = list(reversed(sorted(CB)))

ind = 0
for i in range(M):
    (c, b) = CB[i]
    for _ in range(b):
        if ind >= N:
            break
        if A[ind] < c:
            A[ind] = c
            ind += 1
        else:
            break
    if ind >= N:
        break

print(sum(A))
### BUGGY CODE ###

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

for i in range(1, N+1):
    print(A.count(i))


### FIXED CODE ###

from sys import stdin
import collections

def main():
    readline = stdin.readline
    N = int(input())
    A = list(map(int, readline().split()))
    listN = list(range(1, N+1))    
    c = collections.Counter(A)
    
    for i in listN:
        print(c[i])
main()
### BUGGY CODE ###

from itertools import accumulate


def mod_max(loop, mod):
    if mod == 0:
        return 0
    return max(max(accumulate((loop[i:] + loop[:i])[:mod])) for i in range(len(loop)))


def main():
    n, k = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(loop)

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = sum(loop)
        ans = max(mod_max(loop, min(loop_len, k)), ans)
        if loop_num > 0:
            ans = max(loop_sum * loop_num + mod_max(loop, loop_mod), ans)
            ans = max(loop_sum * (loop_num - 1) + mod_max(loop, loop_len), ans)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def mod_max(loop, mod):
    if mod == 0:
        return 0
    loop_len = len(loop)
    mm = min(loop)
    for start in range(loop_len):
        current_sum = 0
        for i in range(mod):
            current_sum += loop[(start + i) % loop_len]
            mm = max(current_sum, mm)
    return mm


def main():
    n, k = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    c = [int(i) for i in input().split()]

    seen = set()
    loop_list = []
    for start in range(n):
        v = start
        loop = []
        while v not in seen:
            seen.add(v)
            loop.append(c[v])
            v = p[v]
        seen.add(v)
        if loop:
            loop_list.append(loop)

    ans = min(c)
    for loop in loop_list:
        loop_len = len(loop)
        loop_num = k // loop_len
        loop_mod = k % loop_len
        loop_sum = sum(loop)
        ans = max(mod_max(loop, min(loop_len, k)), ans)
        if loop_num > 0:
            ans = max(loop_sum * loop_num + mod_max(loop, loop_mod), ans)
            ans = max(loop_sum * (loop_num - 1) + mod_max(loop, loop_len), ans)
    print(ans)


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

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())

    l = []
    for i in range(1, math.floor(math.sqrt(n))):
        l.append(i)

    l_list = list(itertools.combinations_with_replacement(l, 3))

    ans_list = []
    for j in range(len(l_list)):
        x = l_list[j][0]
        y = l_list[j][1]
        z = l_list[j][2]
        ans = x**2 + y**2 + z**2 + x*y + y*z + z*x
        ans_list.append((ans, [x, y, z]))
    
    # print(ans_list)

    for i in range(1, n+1):
        count = 0
        for j in range(len(ans_list)):
            if ans_list[j][0] == i and ans_list[j][1][0] == ans_list[j][1][1]and ans_list[j][1][2] == ans_list[j][1][1]:
                count += 1
            elif ans_list[j][0] == i:
                count += 3
            if ans_list[j][0] > i**2:
                break

        print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())
    l = [0]*(n+1)
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                temp = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if temp <= n:
                    l[temp] += 1

    for i in range(1, n+1):
        print(l[i])


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

def Z(s):
    ls = len(s)
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and s[j] == s[i+j]:
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    for i in range(ls):
        lcp[i] = min(lcp[i],i)
    return max(lcp)

n = int(input())
s = input()
print(max(Z(s[i:]) for i in range(n)))

### FIXED CODE ###

def Z(s,ls):
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and s[j] == s[i+j]:
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    for i in range(ls):
        lcp[i] = min(lcp[i],i)
    return max(lcp)

n = int(input())
s = list(map(ord,list(input())))
print(max(Z(s[i:],n-i) for i in range(n)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,a,b=map(int,input().split())

    if(a+b>n+1):
        print(-1)
        return
    if(a*b<n):
        print(-1)
        return

    # a*b=n のとき
    A=[]
    for i in range(a):
        for j in range(b,0,-1):
            A.append(i*b+j)

    d=a*b-n
    m=0
    for i in range(1,a):
        k=min(b-1,d)
        d-=k
        m+=k
        for j in range(i*b,(i+1)*b):
            if(j>=(i+1)*b-k): A[j]=None
            else: A[j]-=m

    ans=[a for a in A if(a is not None)]
    print(*ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n,a,b=map(int,input().split())
    if(a+b>n+1):
        print(-1)
        return
    if(a*b<n):
        print(-1)
        return

    ans=list(range(b,0,-1))
    now=b
    d=a*b-n
    for _ in range(a-1):
        k=min(d,b-1)
        d-=k
        next=now+(b-k)
        for i in range(next,now,-1):
            ans.append(i)
        now=next

    print(*ans)
resolve()
### BUGGY CODE ###

N,X,Y=map(int,input().split())

d=[[0 for _ in range(N)] for _ in range(N)]
ans=[0]*N
for i in range(N):
    for j in range(i+1,N):
        d[i][j]=min(abs(i-j),abs(X-1-i)+abs(Y-1-j)+1,abs(X-1-j)+abs(Y-1-i)+1)
        ans[d[i][j]-1]+=1

for o in range(N-1):
    print(ans[o])

### FIXED CODE ###

N,X,Y=map(int,input().split())

d=[[0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(i+1,N):
        d[i][j]=min(abs(i-j),abs(X-1-i)+abs(Y-1-j)+1,abs(X-1-j)+abs(Y-1-i)+1)

ans=[0 for _ in range(N)]
for k in range(N):
    for l in range(k+1,N):
        if d[k][l]<N:
            ans[d[k][l]]+=1
    
for o in range(N-1):
    print(ans[o+1])
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
for i in range(1,n+1):
    print(L.count(i))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = tuple(map(int, input().split()))
All = Counter(a)
for i in range(1,n+1):
    try:
        print(All[i])
    except:
        print(0)
### BUGGY CODE ###

n,k = map(int,input().split())
H = list(map(int,input().split()))
dp = [0]*n

if n <= k:
    print(abs(H[0]-H[-1]))
else:
    for i in range(1,k+1):
        dp[i] = abs(H[i]-H[0])
    for i in range(k+1,n):
        res = abs(H[i]-H[i-k])+dp[i-k]
        for j in range(1,k):
            res = min(res,abs(H[i]-H[i-j])+dp[i-j])
        dp[i] = res
    print(dp[n-1]) 

### FIXED CODE ###

n,k = map(int,input().split())
H = list(map(int,input().split()))
dp = [0]*n

if n <= k:
    print(abs(H[0]-H[-1]))
else:
    for i in range(1,k+1):
        dp[i] = abs(H[i]-H[0])
    for i in range(k+1,n):
        res = abs(H[i]-H[i-k])+dp[i-k]
        for j in range(1,k):
            res = min(res,abs(H[i]-H[i-j])+dp[i-j])
        dp[i] = res
    print(dp[n-1])
### BUGGY CODE ###

# coding: utf-8
import math

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(r)*math.factorial(n - r))

ans = 0
mod = 10**9+7

tmp = 0
for i in range(n):
    tmp += combinations_count(n, i+1)
an = combinations_count(n, a)
bn = combinations_count(n, b)
ans = (tmp - an - bn) % mod
print(ans)


### FIXED CODE ###

# coding: utf-8
from functools import reduce

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

def nCr(n, r):
    r = min(n-r, r)
    if r == 0: return 1
    numer = reduce(lambda x, y: x * y % mod, range(n, n - r, -1))
    denom = reduce(lambda x, y: x * y % mod, range(1, r + 1))
    return numer * pow(denom, mod - 2, mod) % mod

mod = 10 ** 9 + 7

tnmo = pow(2, n, mod) - 1
an = nCr(n, a)
bn = nCr(n, b)
ans = (tnmo - an - bn) % mod

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

import sys

N = int(input())

s = [None] * N
l, c, r = 0, N//2, N-1

while True:
    for i in (l, c, r):
        if s[i] == None:
            print(i, flush=True)
            s[i] = input()
            if s[i] == 'Vacant':
                sys.exit()
    if s[l] != s[c]:
        r = c
        c = (l + r) // 2
    else:
        l = c
        c = (l + r) // 2


### FIXED CODE ###

N = int(input())

s = [None] * N
l, c, r = 0, N//2, N-1

while True:
    for i in (l, c, r):
        if s[i] == None:
            print(i, flush=True)
            s[i] = input()
            if s[i] == 'Vacant':
                exit()
    if ((c-l)%2==0 and s[l]!=s[c]) or ((c-l)%2 and s[l]==s[c]):
        r = c
        c = (l + r) // 2
    else:
        l = c
        c = (l + r) // 2
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
l = [0] * 10000001
for i in A:
    l[i] += 1
s = 0
for i in l:
    s += i * (i - 1) // 2
for a in A:
    a = l[a]
    print(s - (a * (a - 1) // 2) + ((a - 1) * (a - 2) // 2))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
l = [0] * 10000001
for i in A:
    l[i] += 1
s = 0
for i in range(N + 1):
    i = l[i]
    s += i * (i - 1) // 2
for a in A:
    a = l[a]
    print(s - (a * (a - 1) // 2) + ((a - 1) * (a - 2) // 2))