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

s = input()
if s[-1] == "?":
    pre = [1 if i<10 else 0 for i in range(13)]
else:
    pre = [0 for i in range(13)]
    pre[int(s[-1])] = 1
n = 10**9 + 7
for i in range(1, len(s)):
    t = 10**i % 13
    if s[-1*i-1] == "?":
        c = pre.copy()
        for j in range(1,10):
            te = t*j % 13
            for k in range(13):
                c[k] = (c[k] + pre[(13+k-te)%13]) % n
        pre = c.copy()
    else:
        te = int(s[-1*i-1])*t % 13
        pre = pre[13-te:]+pre[:13-te]
print(pre[5]%n)

### FIXED CODE ###

s = input()
pre = [1]+[0]*12
n = 10**9 + 7
tem = [[i*j%13 for i in range(10)] for j in range(13)]
t = 1
for i in range(len(s)):
    if s[-1*i-1] > "9":
        pre = [sum([pre[k-i] for i in tem[t]])%n for k in range(13)]      
    else:
        te = int(s[-1*i-1])*t % 13
        pre = [pre[i-te] for i in range(13)]
    t = t*10 % 13
print(pre[5])
### BUGGY CODE ###

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

dp = [float('inf')] * (N)
dp[0] = 0

for i in range(1, N):
    min_from = max(0, i - K)

    temp = float('inf')
    for j in range(min_from, i):
        temp = min(temp, dp[j] + abs(H[i] - H[j]))
    dp[i] =temp

print(dp[N-1])

### FIXED CODE ###

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

dp = [float('inf')] * (N)
dp[0] = 0

for i in range(1, N):
    min_from = max(0, i - K)

    temp = float('inf')
    for j in range(min_from, i):
        temp = min(temp, dp[j] + abs(H[i] - H[j]))
    dp[i] =temp

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

import sys
input = sys.stdin.readline

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))

stack = [0]
visited = []
ans = [0]*n
while stack:
    node = stack.pop()
    visited.append(node)
    for child in graph[node]:
        if child[0] not in visited:
            stack.append(child[0])
            if child[1]%2 == 0:
                ans[child[0]] = ans[node]
            else:
                ans[child[0]] = (ans[node]+1)%2

[print(ans[i]) for i in range(n)]


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]

graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))

stack = [0]
ans = [-1]*n
ans[0] = 0
while stack:
    node = stack.pop()
    for child in graph[node]:
        if ans[child[0]]!=-1:
            continue
        
        stack.append(child[0])
        if child[1]%2 == 0:
            ans[child[0]] = ans[node]
        else:
            ans[child[0]] = (ans[node]+1)%2

for a in ans:
    print(a)
### BUGGY CODE ###

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

def binary_search(func, array):
    left,right=0,len(array)-1
    y_left, y_right = func(array[left]), func(array[right])
    while True:
        middle = (left+right)//2
        y_middle = func(array[middle])
        if y_left==y_middle: left=middle
        else: right=middle
        if right-left==1:break

    return left

SUM = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    l1,l2=L[i],L[j]
    if L[-1]<l1+l2:
      k = N-1
    else:
      k = binary_search(lambda x: x<l1+l2, L)
    SUM += max(0,k-j)

print(SUM)

### FIXED CODE ###

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

def binary_search(func, array, left=0):
    right=len(array)-1
    y_left, y_right = func(array[left]), func(array[right])
    if y_left==False:return 0
    while True:
        middle = (left+right)//2
        y_middle = func(array[middle])
        if y_left==y_middle: left=middle
        else: right=middle
        if right-left==1:break

    return left

SUM = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    l = L[i]+L[j]
    if L[-1]<l:
      k = N-1
    else:
      k = binary_search(lambda x: x<l, L, j+1)
    SUM += max(0,k-j)

print(SUM)
### BUGGY CODE ###

arr = input().split()
n = int(arr[0])
m = int(arr[1])

a = [0] * m
b = [0] * m

for i in range(m):
    tmp = input().split()
    a[i] = int(tmp[0])
    b[i] = int(tmp[1])

mat = [[0] * n for i in range(n)]

for i in range(m):
    mat[a[i]-1][b[i]-1] = 1
    mat[b[i]-1][a[i]-1] = 1

path = []
for i in range(n):
    if mat[0][i] == 1:
        path.append(i)

flag = False
for i in range(len(path)):
        if mat[path[i]][n-1] == 1: 
            flag = True
            break

if flag == True:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
    


### FIXED CODE ###

arr = input().split()
n = int(arr[0])
m = int(arr[1])

x = []
y = []

for i in range(m):
    a,b = map(int, input().split())
    if a == 1:
        x.append(b)
    if b == n:
        y.append(a)

if len(set(x+y)) < len(x) + len(y):
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf') for _ in range(n)]
dp[0] = 0
for i in range(n):
  for j in range(1, min(i, k)+1):
    dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[i])
print(dp[-1])

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.array([0 for _ in range(n)])
dp[0] = 0
for i in range(1, n):
  j = max(0, i-k)
  dp[i] = min(dp[j:i] + np.abs(h[i]-h[j:i]))

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

N,Q = (int(X) for X in input().split())
S = input()
AIndex = [Ind for Ind,Str in enumerate(S) if S[Ind:Ind+2]=='AC']
if len(AIndex)==0:
    print('\n'.join(['0']*Q))
else:
    CIndex = [X+1 for X in AIndex]
    for T in range(0,Q):
        L,R = (int(X) for X in input().split())
        if (L-1)>AIndex[-1] or (R-1)<CIndex[0]: print('0')
        else: print(sum([(L-1)<=X and (R-1)>=Y for X,Y in zip(AIndex,CIndex)]))

### FIXED CODE ###

N,Q = (int(X) for X in input().split())
S = input()
T = [0]*(N+1)
for I in range(0,N):
     T[I+1] = T[I] + (S[I:I+2]=='AC')
for J in range(0,Q):
    L,R = (int(X)-1 for X in input().split())
    print(T[R]-T[L])
### BUGGY CODE ###

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

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

q = [0]
ans = [-1] * N
while(len(q) > 0):
    now = q.pop(0)

    for i in node[now]:
        if ans[i] == -1:
            q.append(i)
            ans[i] = now


print("Yes")
for i in range(1, N):
    print(ans[i] + 1)



### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())

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

q = deque([0])
ans = [-1] * N
while(len(q) > 0):
    now = q.popleft()

    for i in node[now]:
        if ans[i] == -1:
            q.append(i)
            ans[i] = now


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

n = int(input())
vote_ls = []
vote_num = [0]*n
for i in range(n):
    aaa = input()
    if aaa in vote_ls:
        #print("a")
        vote_num[vote_ls.index(aaa)]+=1
    else:
        vote_ls.append(aaa)
        vote_num[vote_ls.index(aaa)]+=1
#print(vote_num)
sub_ls = []
max_vote = max(vote_num)
for i in range(n):
    if vote_num[i] == max_vote:
        sub_ls.append(vote_ls[i])
sub_ls.sort()
for i in range(len(sub_ls)):
    print(sub_ls[i])


### FIXED CODE ###

n = int(input())
vote_ls = {}
#vote_num = [0]*n
for i in range(n):
    aaa = input()
    if aaa in vote_ls.keys():
        vote_ls[aaa]+=1
    else:
        vote_ls[aaa] = 1
#print(vote_ls)
sub_ls = []
'''
max_vote = max(vote_)
for i in range(n):
    if vote_num[i] == max_vote:
        sub_ls.append(vote_ls[i])
sub_ls.sort()
for i in range(len(sub_ls)):
    print(sub_ls[i])
'''
sorted = sorted(vote_ls.items(), key=lambda x:x[1])
sub_ls.append(sorted[-1])
for i in range(len(sorted)-2,-1,-1):
    if sorted[i][1] == sorted[-1][1]:
        sub_ls.append(sorted[i])
    else:
        break
#print(sub_ls)
sub_ls.sort()
for i in range(len(sub_ls)):
    print(sub_ls[i][0])
### BUGGY CODE ###


R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        # k=0, horizontal and vertical transitions are allowed
        dp[i][j][0] = max(dp[i][j - 1][0], dp[i - 1][j][0], dp[i - 1][j][1],
                          dp[i - 1][j][2], dp[i - 1][j][3])

        # k=1~3, horizontal transition and picking up are allowed
        dp[i][j][3] = max(dp[i][j - 1][3], dp[i][j - 1][2] + items[i][j],
                          dp[i][j][2] + items[i][j])

        dp[i][j][2] = max(dp[i][j - 1][2], dp[i][j - 1][1] + items[i][j],
                          dp[i][j][1] + items[i][j])

        dp[i][j][1] = max(dp[i][j - 1][1], dp[i][j - 1][0] + items[i][j],
                          dp[i][j][0] + items[i][j])

print(max(dp[-1][-1]))


### FIXED CODE ###


R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

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

n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
 
if sum(a) < sum(b):
    print('-1')
    exit()
 
count = 0
sabun = [(i, a[i]-b[i]) for i, _ in enumerate(a) if a[i]<b[i]]
husoku = sum([x[1] for x in sabun])
a_sorted = sorted(a)
while husoku < 0:
    ma = a_sorted[-1]
    a_sorted = a_sorted[:-1]
    mai = a.index(ma)
    husoku += ma - b[mai]
    a[mai] = b[mai]
    count += 1
 
print(len(sabun) + count)   

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
 
if sum(a) < sum(b):
    print('-1')
    exit()
 
count = 0
sabun = [a[i]-b[i] for i, _ in enumerate(a)]
husoku = sum([x for x in sabun if x<0])
sabun.sort(reverse=True)

for i in sabun:
    if husoku >= 0:
        break
    husoku += i
    count += 1
 
print(len([x for x in sabun if x<0]) + count)
### BUGGY CODE ###

from sys import stdin
import fractions
 
 
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
 
res = []
 
 
for i in range(N):
    B = A[:]
    del B[i]
    gcd_num = B[0]
    for j in range(1, N-1):
        gcd_num = fractions.gcd(gcd_num, B[j])
    res.append(gcd_num)
        
 
 
print(max(res))

### FIXED CODE ###

from sys import stdin
import fractions

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
# インデックスを直感で使えるように先頭にダミーを入れる
A = [0] + A

"""
L(i) := A_1, A_2, ..., A_i-1 の最大公約数
R(i) := A_i, A_i+1, ..., A_N の最大公約数
Aiを書き換えることにした場合の最大公約数をM_iとすると
M_i = gcd(L(i), R(i+1))

ただし L(0)=0, R(N+1)=0
"""

L = [0 for _ in range(N+1)]
R = [0 for _ in range(N+2)]

for i in range(N):
    L[i+1] = fractions.gcd(L[i], A[i])


for i in range(N, 0, -1):
    R[i] = fractions.gcd(R[i+1], A[i])

M = []

for i in range(1, N+1):
    M_i = fractions.gcd(L[i], R[i+1])
    M.append(M_i) 

print(max(M))
### BUGGY CODE ###

import itertools
 
line=input()
n,k=map(int,line.split())
s=set(list(range(n+1)))
sums=list()
while k!=(n+2):
     koko=list()
     sub=list(itertools.combinations(s,k))
     #print(sub)
     for val in sub:
          soso=0
          for i in val:
               soso=(soso%((10**9)+7))+((i+0.2424)%((10**9)+7))
               #soso=(soso%((10**9)+7))
          if soso not in sums:
               sums.append(soso)
               #soso=(soso%((10**9)+7))
          
               
          
     
     
     
     k+=1
#jojo=(%((10**9)+7))
print((len(sums)))

### FIXED CODE ###

line=input()
n,k=map(int,line.split())
sums=0
while k!=(n+2):
     if k==1:
          mini=0
     if k>=2:
          mini=(((k)*(k-1))/2)#%((10**9)+7)
     maxi=( (((n+1)*(n)) - ((n+1-k)*(n-k)) )/2  )#%((10**9)+7)
     sums+=(maxi-mini+1)
     sums=sums%((10**9)+7)
     k+=1
print(int(sums))
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

N = I()

ans = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            ans += math.gcd(math.gcd(a, b), c)

print(ans)


### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

from functools import lru_cache

@lru_cache(maxsize=INF)
def ggcd(a, b):
    return math.gcd(a, b)

K = I()

h = [0] * 201
for a in range(1, K+1):
    for b in range(1, K+1):
        h[ggcd(min(a,b), max(a,b))] += 1

ans = 0
for c in range(1, K+1):
    for i, ab in enumerate(h):
        if ab != 0:
            ans += ggcd(min(c,i), max(c,i)) * ab

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

n = int(input())

nc_lst = [i for i in range(1, n)]
count = 0

for i in range(len(nc_lst)):
    nc = nc_lst[i]
    for j in range(1, nc + 1):
        if nc // j == nc / j:
            count += 1
print(count)

### FIXED CODE ###

n = int(input())

answer = 0
for i in range(1, n):
    answer += (n - 1) // i
print(answer)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = (cnt + [1 for _ in range(n - sum(cnt))])[::-1]
nxt = cnt[:]

for _ in range(k - 1):
	cnt = [sum([x * nxt[i] % mod for x in cnt[:(len(cnt) - i)]])  for i in range(len(cnt))]
print(sum(cnt) % mod)


### FIXED CODE ###

import numpy as np
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

m = n ** 0.5
cnt = [n // i - n // (i + 1) for i in range(1, int(m) + 1)] 
cnt = np.array((cnt + [1 for _ in range(n - sum(cnt))])[::-1])
nxt = cnt[:]
for _ in range(k - 1):
	cnt = nxt * np.cumsum(cnt)[::-1] % mod

print(sum(cnt) % mod)
### BUGGY CODE ###

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


def is_acgt(s):
    if s=='A' or s=='C' or s=='G' or s=='T':
        return 1
    else: return 0


n, q = map(int, raw_input().split())
s = raw_input()

x = [raw_input() for i in range(q)]

for d in x:
    r = d.split(' ')
    ss = s[int(r[0])-1:int(r[1])]
    print ss.count('AC')

### FIXED CODE ###

#!/usr/bin/env python3
N, Q = map(int, input().split())
S = input()
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append([l,r])

A = [0]

cnt = 0
for i in range(1, len(S)):
    if S[i-1:i+1] == 'AC':
        cnt += 1
    A.append(cnt)

for l, r in LR:
    print(A[r-1] - A[l-1])
### BUGGY CODE ###

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

ans = float("inf")
E = S.count("E")
W = S.count("W")
for i, v in enumerate(S):
    left = S[:i]
    left_E = left.count("E")
    left_W = left.count("W")
    if v == "E":
        right_E = E - left_E - 1
    else:
        right_E = E - left_E
    ans = min(ans, left_W + right_E)


print(ans)

### FIXED CODE ###

import numpy as np
N = int(input())
S = str(input())

E = np.cumsum([1 if s == "E" else 0 for s in S])
W = np.cumsum([1 if s == "W" else 0 for s in S])

ans = float("inf")
for i, v in enumerate(S):
    if v == "E":
        ans = min(ans, (E[-1] - E[i]) + W[i])
    else:
        ans = min(ans, (E[-1] - E[i]) + W[i] - 1)
    

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

S = str(input())

def del_cube(s, i):
    s = s[:i] + s[i+2:]
    return s

s = S
while True:
    flag = True
    for i in range(len(s) - 1):
        if s[i] == '0' and s[i+1] == '1' or s[i] == '1' and s[i+1] == '0':
            flag = False
            s = del_cube(s, i)
            break
            
    if flag == True:
        break
        
print(len(S) - len(s))


### FIXED CODE ###

S = str(input())

s = S

zero = s.count('0')
one = s.count('1')

zero_one_diff = max(zero, one) - min(zero, one)
print(len(s) - zero_one_diff)
### BUGGY CODE ###

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

M = [list(map(lambda x:0 if x == "#" else -1, input())) for _ in range(H)]

def set(i, j, x):
    if x < 0 or M[i][j] == 0:
        return
    x += 1
    if M[i][j] < 0:
        M[i][j] = x
    else:
        M[i][j] = min(M[i][j], x)

for i in range(H):
    for j in range(W):
        if j > 0:
            set(i, j, M[i][j-1])
        if i > 0:
            set(i, j, M[i-1][j])

for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        if j < W-1:
            set(i, j, M[i][j+1])
        if i < H-1:
            set(i, j, M[i+1][j])

print(max(y for x in M for y in x))


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

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

from itertools import accumulate
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
print(*An)


### FIXED CODE ###

from itertools import accumulate
import sys
N, K = map(int, input().split())
An = list(map(int, input().split()))

for cnt in range(K):
    tmp = [0]*(N+1)
    for i in range(N):
        power = An[i]
        left = max(0, i-power)
        right = min(N, i+power+1)
        tmp[left] += 1
        tmp[right] -= 1
    An = list(accumulate(tmp))[:-1]
    if cnt > 40:
        An = [N]*N
        print(*An)
        sys.exit()
print(*An)
### BUGGY CODE ###

from math import factorial
def H(x, y):
    return factorial(x + y - 1) // (factorial(x - 1) * factorial(y))
n, m = list(map(int, input().split()))
p = 2
prime_factorization = []
while p * p <= m:
    count = 0
    while m % p == 0:
        m //= p
        count += 1
    if count > 0:
        prime_factorization.append(count)
    p += 1
if m > 1:
    prime_factorization.append(1)
ans = 1
for r in prime_factorization:
    ans *= H(n, r)
print(ans % 1000000007)

### FIXED CODE ###

def C(x, y):
    z = 1
    for i in range(x, x-y, -1):
        z *= i
    for i in range(y, 1, -1):
        z //= i
    return z
def H(x, y):
    return C(x+y-1, y)
n, m = list(map(int, input().split()))
p = 2
prime_factorization = []
while p * p <= m:
    count = 0
    while m % p == 0:
        m //= p
        count += 1
    if count > 0:
        prime_factorization.append(count)
    p += 1
if m > 1:
    prime_factorization.append(1)
ans = 1
for r in prime_factorization:
    ans *= H(n, r)
print(ans % 1000000007)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input())-1)
i=0
seen=[]
out=0
while i!=1:
  out+=1
  i=a[i]
  if i in seen:
    out=-1
    break
  seen.append(i)
print(out)

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input())-1)
i=0

out=0
kai=0
while i!=1:
  kai+=1
  out+=1
  i=a[i]
  if kai>n:
    out=-1
    break

print(out)
### BUGGY CODE ###

n=int(input())
s=str(input())
ans=0
for i in range(0,1000):
  temp=[]
  temp.append(i//100)
  temp.append((i-(i//100)*100)//10)
  temp.append(i%10)
  cnt=0
  k=0
  for j in range(0,n):
    if cnt==0 and temp[0]==int(s[j]):
      cnt=cnt+1
      k=j
      break
  for j in range(k+1,n):      
    if cnt==1 and temp[1]==int(s[j]):
      cnt=cnt+1
      k=j
  for j in range(k+1,n):
    if cnt==2 and temp[2]==int(s[j]):
      ans=ans+1
      break
print(ans)

### FIXED CODE ###

n=int(input())
s=str(input())
ans=0
i=0
while i<1000:
  temp=i//100
  cnt=0
  k=0
  for j in range(0,n):
    if temp==int(s[j]):
      cnt=cnt+1
      k=j
      break
  if cnt==0:
    i=i+100
  else:
    temp=(i-(i//100)*100)//10
    for j in range(k+1,n):      
      if temp==int(s[j]):
        cnt=cnt+1
        k=j
        break
    if cnt==1:
      i=i+10
    else:
      temp=i%10
      i=i+1
      for j in range(k+1,n):
        if temp==int(s[j]):
          ans=ans+1
          break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
As = list(map(int, input().split()))
for i in range(1,N):
    print(As.count(i))
print(0)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
N = int(input())
As = list(map(int, input().split()))
c = Counter(As)
for i in range(1,N):
    print(c[i])
print(0)
### BUGGY CODE ###

n = int(input())
d = sorted(list(map(int, input().split())))
m = int(input())
t = sorted(list(map(int, input().split())))

for i in t:
  if i in d:
    d.remove(i)
  else:
    print("NO")
    exit()

print("YES")

### FIXED CODE ###

n = int(input())

ht = {}

for i in input().split():
  ht[i] = ht.get(i, 0) + 1

m = int(input())

for i in input().split():
  if i not in ht or ht[i] == 0:
    print("NO")
    exit()
  else:
    ht[i] -= 1

print("YES")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    ans += a.count(i+1)*(a.count(i+1)-1)//2
for j in range(n):
    ansout = ans
    ansout -= a.count(a[j]) -1
    print(ansout)

### FIXED CODE ###

import numpy as np
def main():
    from collections import Counter
    n = int(input())
    a = tuple(map(int, input().split()))
    ans = 0
    c = Counter(a)
    for i in range(n):
        ans += c[i+1]*(c[i+1]-1)//2
    for j in range(n):
        print(ans - c[a[j]] + 1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import Counter as counter

N = int(input())
char_counts = [counter(input()) for i in range(N)]
match_count = 0
for i, c in enumerate(char_counts):
  for j in range(i+1, N, 1):
    if char_counts[j] == c:
      match_count += 1
print(match_count)

### FIXED CODE ###

N = int(input())
dic = {}
count = 0
for _ in range(N):
  s = ''.join(sorted(input()))
  if s in dic.keys():
    count += dic[s]
    dic[s] += 1
  else:
    dic[s] = 1
print(count)