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

import numpy as np

N = int(input())
A = np.array(list(map(int, input().split(' '))))
num_sum = 0
remove_array = np.array([], int)
for i in range(N):
    c1 = np.count_nonzero(A == i + 1)
    c2 = np.count_nonzero(A == A[i])
    if c2 <= 1:
        remove_array = np.append(remove_array, 0)
    else:
        remove_array = np.append(remove_array, c2 - 1)
    num_sum += int(c1 * (c1 - 1) / 2)
for i in range(N):
    print(num_sum - remove_array[i])


### FIXED CODE ###

'''
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split(' '))))
num_sum = 0
remove_array = np.array([], int)
for i in range(N):
    c1 = np.count_nonzero(A == i + 1)
    c2 = np.count_nonzero(A == A[i])
    if c2 <= 1:
        remove_array = np.append(remove_array, 0)
    else:
        remove_array = np.append(remove_array, c2 - 1)
    num_sum += int(c1 * (c1 - 1) / 2)
print(*(num_sum - remove_array), sep='\n')
'''
import collections
N = int(input())
A = list(map(int, input().split()))
cnt = collections.Counter(A)
total = 0
for key in cnt.keys():
    total += cnt[key] * (cnt[key] - 1) // 2
for i in range(N):
    tmp = total
    tmp -= cnt[A[i]] * (cnt[A[i]] - 1) // 2
    tmp += (cnt[A[i]] - 1) * (cnt[A[i]] - 2) // 2
    print(tmp)
### BUGGY CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

def main_chk():
    N=int(input())
    C=input()

    chk = N - 1
    cnt = 0

    for i in range(N):
        if C[i] == 'W':
            for x in range(N-i):
                if C[chk-x] == 'R':
                    chk = chk - x
                    break
            if chk <= i:
                break
            else:
                cnt = cnt + 1
                chk = chk - 1

    print(cnt)

main_chk()


### FIXED CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re

def main_chk():
    N=int(input())
    C=input()

    chk = N - 1
    cnt = 0

    for i in range(N):
        if C[i] == 'W':
            p = chk
            chk = i
            for x in range(N-i):
                if C[p-x] == 'R':
                    chk = p - x
                    break
            if chk <= i:
                break
            else:
                cnt = cnt + 1
                chk = chk - 1
                if chk <= i + 1:
                    break

    print(cnt)

main_chk()
### BUGGY CODE ###

import copy
import sys

sys.setrecursionlimit(200000000)

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

dicts={}
def dfs(index, string, values, N, root):
    temp=[]
    if index == N:
        dicts[" ".join(list(map(str,string)))] = root
        return None
    
    length = len(string)+1
    
    for i in values:

        if i > index:
            break
        temp_str = copy.deepcopy(string)
        temp_root = copy.deepcopy(root)
        temp_str.insert(i-1,i)
        temp_root.append(i)
        
        dfs(index+1, temp_str, values, N, temp_root)
        

        

dfs(1,[], values, N+1, [])

output = " ".join(list(map(str,a)))

if output in dicts:
    for i in dicts[output]:
        print(i)
else:
    print(-1)

### FIXED CODE ###

import copy

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


root=[]
string = copy.deepcopy(a)
while len(string)!=0:
    temp=[]
    for i,s in enumerate(string):
        if i+1 == s:
            temp.append(i+1)
    if len(temp)==0:
        break
    
    if temp[0]==1 and len(temp)==1:
        string.pop(0)
        root.append(1)
    else:
        if 1 in temp:
            temp.remove(1)
        root.append(temp[-1])
        string.pop(temp[-1]-1)
        
if len(string)!=0:
    print(-1)
else:
    for i in root[::-1]:
        print(i)
### BUGGY CODE ###

(n,q),*t=[map(int,t.split())for t in open(0)]
s=[0]
d=s*n
f=s+[1]*n
e=[[]for _ in d]
for a,b in t[:-q]:e[a-1]+=b-1,;e[b-1]+=a-1,
for p,x in t[-q:]:d[p-1]+=x
while s:
 v=s.pop()
 for w in e[v]:
  if f[w]:f[w]=0;d[w]+=d[v];s+=w,
print(*d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v):
    for w in e[v]:
        if root[w]>=0:continue
        root[w]=v
        dfs(w)
def dfs2(v):
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        data[w]+=data[v]
        dfs2(w)
input=sys.stdin.readline
n,q=map(int,input().split())
e=[[]for _ in range(n)]
root=[0]+[-1]*(n-1)
data=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
    e[b-1]+=a-1,
#dfs(0)
for _ in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
f=[1]+[0]*(n-1)
dfs2(0)
print(*data)
### BUGGY CODE ###

n = int(input())
x = [int(x) for x in input().split()]

m = (n // 2) - 1
for i in range(n):
    l = x[:i] + x[i+1:]
    l.sort()
    print(l[m])

### FIXED CODE ###

n = int(input())
x = [int(x) for x in input().split()]

s = sorted(x)

for i in range(n):
    if x[i] <= s[n//2 - 1]:
        print(s[n//2])
    else:
        print(s[n//2 - 1])
### BUGGY CODE ###

# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())|	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import collections
def inpl(): return list(map(int, input().split()))

#### START
n = int(input())
a = list(map(int,input().split()))

b = []
for a_i in a:
  b.append(a_i)
  b.reverse()

print(*b, sep=" ")

### FIXED CODE ###

# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = map(int,input().split())|	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = list(map(int,input().split()))	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import collections
def inpl(): return list(map(int, input().split()))

#### START
n = int(input())
a = list(map(int,input().split()))

b = a[::2]
c = a[1::2]

if n%2 == 0:
  ans = list(reversed(c)) + b
  print(*ans, sep=" ")
else:
  ans = list(reversed(b)) + c
  print(*ans, sep=" ")
### BUGGY CODE ###

n = int(input())
s = list(input())
ans = 0
for i in range(len(s)-2):
         for j in range(i+1,len(s)-1):
                  for k in range(j+1,len(s)):
                           if (s[i] != s[j] and s[j] != s[k] and s[k] != s[i]) and (j - i != k - j):
                                    ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
s = list(input())
Rcount = 0
Gcount = 0
Bcount = 0
cnt = 0
for i in range(len(s)):
         if s[i] == "R":
                  Rcount += 1
         elif s[i] == "G":
                  Gcount += 1
         elif s[i] == "B":
                  Bcount += 1
RGB = Rcount * Gcount * Bcount
for i in range(1,(len(s)//2)+2):
         for j in range(len(s)):
                  if i * 2 + j >= len(s):
                           break
                  else:
                           if s[j] != s[j+i] and s[j+i] != s[j+i+i] and s[j+i+i] != s[j]:
                                    cnt += 1
print(RGB - cnt)
### BUGGY CODE ###

h, w = map(int, input().split(' '))
a1 = 0
for i in range(0, h + w):
    if(((h * w) % 2) == 1):
        a1 = ((h * w) // 2) + 1
    elif(((h * w) % 2) == 0):
        a1 = (h * w) // 2
print(a1)

### FIXED CODE ###

h, w = map(int, input().split(' '))
a1 = 0
if ((h == 1) or (w == 1)):
    a1 = 1
elif(((h * w) % 2) == 1):
    a1 = ((h * w) // 2) + 1
elif(((h * w) % 2) == 0):
    a1 = (h * w) // 2
print(a1)
### BUGGY CODE ###

from collections import deque
N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  B.append(A[i])
  B=list(reversed(B))
print(*B)

### FIXED CODE ###

from collections import deque
N=int(input())
A=list(map(int,input().split()))
l=[]
r=[]
for i in range(N):
  if i%2==0:
    r.append(A[i])
  else:
    l.append(A[i])
if N%2==0:
  print(*(list(reversed(l))+r))
else:
  print(*(list(reversed(r))+l))
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max(d)+1):
        if d.count(i) == 0:
            print(0)
            exit()
        ans *= pow(b, d.count(i))
        b = d.count(i)
    print(ans % 998244353)
else:
    print(0)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
max = 0
dd=[0]*10**5
for i in d:
    dd[i]+=1
    if(max<i):
        max=i
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
### BUGGY CODE ###

List = list(map(int,input().split()))
L = List[0]
R = List[1]
count_dict = {}
count_list = []
if R - L >= 2019:
    print(0)
else:
    for i in range(L,R):
        for j in range(i+1,R+1):
            count_dict[i,j]  = (i * j) % 2019

    for i in count_dict.values():
        count_list.append(i)

    sort_list = sorted(count_list)
    print(sort_list[0])


### FIXED CODE ###

List = list(map(int,input().split()))
L = List[0]
R = List[1]
count_list = []
if R - L >= 2019:
    print(0)
else:
    for i in range(L,R):
        for j in range(i+1,R+1):
            count_list.append((i * j) % 2019)

    sort_list = sorted(count_list)
    print(sort_list[0])
### BUGGY CODE ###

N,M=map(int,input().split())
keys=[]
inf=12*(10**5)+1
for i in range(M):
    a,b=map(int,input().split())
    c=sum([1<<(i-1) for i in list(map(int,input().split()))])
    keys.append((a,c))

#print(keys)

dp=[inf for j in range(2**N)]
dp[0]=0

for key in keys:
    for j in range(2**N):
        dp[j|key[1]]=min(dp[j|key[1]],dp[j]+key[0])
#    print(dp)

print(dp[2**N-1] if dp[2**N-1]!=inf else -1)

### FIXED CODE ###

N,M=map(int,input().split())
inf=12*(10**5)+1

dp=[inf for j in range(2**N)]
dp[0]=0

for i in range(M):
    a,b=map(int,input().split())
    c=sum([1<<(i-1) for i in list(map(int,input().split()))])
#    print(a,b,c)
    for j in range(2**N):
        dp[j|c]=min(dp[j|c],dp[j]+a)
#    print(dp)

print(dp[2**N-1] if dp[2**N-1]!=inf else -1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000) 
 

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 ###

import sys
input = sys.stdin.readline

h, w, m = map(int, input().split())
col = [0]*w
row = [0]*h
ypos = []
xpos = []
bomb = []

for i in range(m):
    H, W = map(lambda x: int(x) - 1, input().split())
    col[W] += 1
    row[H] += 1
    bomb.append((H, W))

maxcol = max(col)
maxrow = max(row)

xpos = [h for h, x in enumerate(col) if x == maxcol]
ypos = [w for w, y in enumerate(row) if y == maxrow]

ans = maxcol + maxrow - 1

for i in ypos:
    for j in xpos:
        if (i, j) not in bomb:
            ans += 1
            print(ans)
            exit()
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, m = map(int, input().split())
col = [0]*w
row = [0]*h
ypos = []
xpos = []
bomb = []

for i in range(m):
    H, W = map(lambda x: int(x) - 1, input().split())
    col[W] += 1
    row[H] += 1
    bomb.append((H, W))

maxcol = max(col)
maxrow = max(row)

xpos = [h for h, x in enumerate(col) if x == maxcol]
ypos = [w for w, y in enumerate(row) if y == maxrow]

ans = maxcol + maxrow - 1
bomb = set(bomb)

for i in ypos:
    for j in xpos:
        if (i, j) not in bomb:
            ans += 1
            print(ans)
            exit()
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)




def main():
    n = int(input())
    a_dic = {}
    i = 0
    count = 0
    for a in map(int, input().split()):
        a_dic[i] = a
        for j in range(i):
            if i - j == a + a_dic[j]:
                count += 1
        i += 1

    # for i in range(n):
    #     ai = a_dic[i]
    #     for j in range(i+1, n):
    #         # combi = (i,j)
    #         if j - i == ai + a_dic[j]:
    #             count += 1
    print(count)



main()

# sys.setrecursionlimit(1000000)
#
#
#
#
# def main():
#     n = int(input())
#     x_dic = {}
#     y_dic = {}
#     i = 0
#     for a in map(int, input().split()):
#         x_dic[i] = a + i
#         y_dic[i] = i - a
#
#         i += 1
#
#     count = 0
#     for i in range(n):
#         ai = a_dic[i]
#         for j in range(i+1, n):
#             # combi = (i,j)
#             if j - i == ai + a_dic[j]:
#                 count += 1
#     print(count)
#
#
#
# main()


### FIXED CODE ###

def is_ok(mid: int, target: int, ls: []):
    return target <= ls[mid]


def bi_search(target: int, ls: []):
    ng = -1
    ok = len(ls)

    cnt = 0
    while ok - ng > 1:
        mid = ng + int((ok - ng) / 2)
        cnt += 1
        if is_ok(mid, target, ls):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    n = int(input())
    l_dic = {}
    r_dic = {}
    i = 0
    for a in map(int, input().split()):
        ld = l_dic.setdefault(i + a, [])
        ld.append(i)
        rd = r_dic.setdefault(i - a, [])
        rd.append(i)
        i += 1

    count = 0
    for rk, rv_list in r_dic.items():
        if rk not in l_dic:
            continue
        lv_list = l_dic[rk]
        for rv in rv_list:
            ind = bi_search(rv, lv_list)
            if ind == len(lv_list):
                count += ind
            else:
                count += ind + 1
            # for lv in lv_list:
            #     if lv < rv:
            #         count += 1
            #     else:
            #         break

    print(count)


main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
edges = [[int(i) for i in input().split()] for _ in range(N-1)]
edge_col = [0]*(N-1)
cols = [set() for _ in range(N)]
gp = [[] for _ in range(N)]

for ind, (a, b) in enumerate(edges):
    gp[a-1].append((b-1, ind))
    gp[b-1].append((a-1, ind))

seen = set()
stk = [0]
max_col = 0
while stk:
    pt = stk.pop()
    if(pt in seen):
        continue
    seen.add(pt)
    for nxt, ind in gp[pt]:
        if(nxt in seen):
            continue
        col = 1
        while col in cols[pt]:
            col += 1
        max_col = max(col, max_col)
        edge_col[ind] = col
        cols[pt].add(col)
        cols[nxt].add(col)

        stk.append(nxt)

print(max_col)
for i in edge_col:
    print(i)


### FIXED CODE ###

N = int(input())
edges = [[] for _ in range(N)]
cnt_edges = [0]*N
colors = [0]*(N-1)
di = {}
A = []
K = 0
for i in range(N-1):
    a,b = [int(x) for x in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

    K=max(K,len(edges[a-1]),len(edges[b-1]))
    di[(a-1,b-1)] = i
    di[(b-1,a-1)] = i
    A.append((a-1,b-1))
#%%
#K = max(cnt_edges)

stk = [(0,0)]
seen = set()
while(stk):
    n,used_color = stk.pop()
    available_color = 1
    next_stk = []
    for next in edges[n]:
        if(next in seen):
            continue
        if(available_color == used_color):
            available_color += 1
        next_stk.append((next,available_color))
        i = di[(next,n)]
        colors[i] = available_color
        available_color += 1
    stk += next_stk
    seen.add(n)

print(K)
for col in colors:
    print(col)
### BUGGY CODE ###

from collections import deque

n, q = map(int, input().split( ))
Edg=[[] for i in range(n+1)]
##
for i in range(n-1):
    a, b = map(int, input().split( ))
    Edg[a].append(b)
Ans=[0 for i in range(n+1)]
P = [0 for i in range(n+1)]
for i in range(q):
    p, x = map(int, input().split( ))
    P[p]+=x
#print(*P)
Chld=[[] for i in range(n+1)]
for p in range(n+1):
    Task=deque()
    Task.append(p)
    while True:
        try:
            p_=Task.popleft()
            for child in Edg[p_]:
                Chld[p].append(child)
                Task.append(child)
        except:
            break
#print(Chld)
for p in range(n+1):
    tmp = P[p]
    Ans[p]+=tmp
    for c in Chld[p]:
            Ans[c]+=tmp

print(*Ans[1:])


### FIXED CODE ###

from collections import deque

n, q = map(int, input().split( ))
Edg=[[] for i in range(n+1)]
Done = [0 for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split( ))
    Edg[a].append(b)
    Edg[b].append(a)


Ans=[0 for i in range(n+1)]
Pls = [0 for i in range(n+1)]


for i in range(q):
    p, x = map(int, input().split( ))
    Pls[p]+=x

root=1

Task=deque()

Task.append(root)

while len(Task)>0:
    p_=Task.popleft()
    tmp = Pls[p_]
    Ans[p_]+=tmp
    Done[p_] = 1
    for child in Edg[p_]:
        if not Done[child]:
            Task.append(child)
            Pls[child]+=tmp


print(*Ans[1:])
### BUGGY CODE ###

# 初期入力
N = int(input())
A = list(map(int, input().split()))


x = [ A[i]^A[j] for i in range(N-1) for j in range(i+1,N) ]
kotae =sum(x) % (10**9 +7)
print(kotae)

### FIXED CODE ###

import numpy as np
mod=10**9+7
N=int(input())
A=np.array(list(map(int, input().split())))
ans=0
for i in range(60):
  b=np.count_nonzero(A>>i&1)
  ans+=(2**i)*b*(N-b)
  ans%=mod
  
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
    global n,k,xy
    z=[0]*n
    k_sub=0
    for i in range(n):
        if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
            z[i]=1
            k_sub+=1
            if k_sub>=k:return True
    return False

for i1 in range(n):
    i1_sub=n-i1
    x_sub1=x[i1][0]
    for l1 in range(i1_sub,1,-1):
        x_sub2=x[i1+l1-1][0]
        for i2 in range(n):
            ans_sub=inf
            i2_sub=n-i2
            y_sub1=y[i2][0]
            l,r=2,i2_sub
            if r<l:
                break
            while l+1<r:
                t=(l+r)//2
                y_sub2=y[i2+t-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    r=t
                else:
                    l=t
            y_sub2=y[i2+r-1][0]
            if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
            if l!=r:
                y_sub2=y[i2+l-1][0]
                if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### BUGGY CODE ###

from collections import Counter,defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

S = list(input())
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1

for i,s in enumerate(S):
    m = pow(10,(N-i-1),13)
    if s == '?':
        for d in range(10):
            for k in range(13):
                dp[i+1][(k+m*d)%13] += dp[i][k]
    else:
        d = int(s)
        for k in range(13):
            dp[i+1][(k+m*d)%13] += dp[i][k]

print(dp[-1][5]%mod)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

s = sys.stdin.readline()
n = len(s)-1
now = [0] * 13
now[0] = 1
for i in range(n)[::-1]:
    prev = now[::]
    now = [0] * 13
    c = n - i - 1#桁
    m = pow(10,c,13)
    if s[i] == '?':
        for k in range(10):
            l = (m*k) % 13
            for j in range(13):
                now[(j+l)%13] += prev[j]
                now[(j+l)%13] = now[(j+l)%13] % mod
    else:
        k = int(s[i])
        l = (m*k) % 13
        for j in range(13):
            now[(j+l)%13] = prev[j]
    # print(now)
print(now[5])
### BUGGY CODE ###

# -*- coding: UTF-8 -*-

n = int(input())
l = []

for i in range(n):
    l.append(sorted(str(input())))

p = 0

for i in range(n):
    for j in range(n - i - 1):
        if l[i] == l[i+j+1]:
            p += 1

print(p)


### FIXED CODE ###

# -*- coding: UTF-8 -*-

n = int(input())
l = []

for i in range(n):
    l.append("".join(sorted(str(input()))))

l.sort()

p = 0
s = 1
f = 0

for i in range(n-1):
    if l[i] == l[i+1] and i != n-2:
        s += 1
        f = 1

    elif l[i] != l[i+1] and f == 1:
        f = 0
        p += int(s * (s-1) / 2)
        s = 1

    elif l[i] == l[i+1] and i == n-2:
        s += 1
        f = 0
        p += int(s * (s-1) / 2)


print(p)