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

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 頂点Nが負の閉路に含まれていないかチェックする
    for i in range(N):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                # 検出した負閉路はすぐに-INFにする
                res[dest] = -INF
                if dest == N-1:
                    # 該当していたら空リストを返却
                    return []
    # 問題なければ頂点リストを返却
    return res

N, M, P = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    # Pは最後に請求される、だけど、ようは動く度に支払ってると思ってもいい
    edges.append((a-1, b-1, -c+P))

res = bellman_ford(N, edges, 0)
if not len(res):
    print(-1)
else:
    # 正負を直す
    ans = -res[N-1]
    # スコアがマイナスなら0
    print(max(0, ans))


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def bellman_ford(N: int, edges: list, src: int) -> list:
    """ ベルマンフォード(頂点数, 辺集合(0-indexed), 始点) """

    # 頂点[ある始点からの最短距離] (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [INF] * N
    res[src] = 0
    # 各辺によるコストの置き換えを頂点数N-1回繰り返す
    for i in range(N-1):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
    # 負の閉路(いくらでもコストを減らせてしまう場所)がないかチェックする
    for i in range(N):
        for src, dest, cost in edges:
            if res[dest] > res[src] + cost:
                res[dest] = res[src] + cost
                if dest == N-1:
                    # 頂点Nがそれに該当していたら空リストを返却
                    return []
    # 問題なければ頂点リストを返却
    return res

N, M, P = MAP()
edges = []
for i in range(M):
    a, b, c = MAP()
    # Pは最後に請求される、だけど、ようは動く度に支払ってると思ってもいい
    edges.append((a-1, b-1, -c+P))

res = bellman_ford(N, edges, 0)
if not len(res):
    print(-1)
else:
    # 正負を直す
    ans = -res[N-1]
    # スコアがマイナスなら0
    print(max(0, ans))
### BUGGY CODE ###

n = int(input())
ans = 0

for j in range(1, n+1):
    if j == 1:
        ans += 1
    else:
        dnum = 2
        s = int(j ** 0.5)
        for i in range(2, s+1):
            if j % i == 0:
                if i == j // i:
                    dnum += 1
                else:
                    dnum += 2
        ans += j * dnum
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0

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

N,M,P=map(int,input().split())
ways=[[] for _ in range(N)]
Rways=[[] for _ in range(N)]

for i in range(M):
  A,B,C=map(int,input().split())
  ways[A-1].append([B-1,C-P])
  Rways[B-1].append(A-1)
  
  
visited=[-float("inf")]*N
visited[0]=0

blacklist=[True]*N
blacklist[-1]=False

for c in range(M):
  for i in range(N):
    if blacklist[i]==True:
      continue
    for to in Rways[i]:
      blacklist[to]=False

for c in range(M+1):
  flag=False
  for i in range(N):
    debit=visited[i]
    if debit==-float("inf"):
      continue
    for to,cost in ways[i]:
      if visited[to]<debit+cost and not blacklist[to]:
        visited[to]=debit+cost
        flag=True
        
  if not flag:
    break
  if c==M:
    print(-1)
    exit()
      
ans=visited[-1]
if ans==-float("inf"):
  print(-1)
else:
  print(max(ans,0))
  
  


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

N,M,P=map(int,input().split())
ways=[[] for _ in range(N)]
Rways=[[] for _ in range(N)]

for i in range(M):
  A,B,C=map(int,input().split())
  ways[A-1].append([B-1,C-P])
  Rways[B-1].append(A-1)
  
  
visited=[-float("inf")]*N
visited[0]=0

blacklist=[True]*N
blacklist[-1]=False
"""
for c in range(M):
  for i in range(N):
    if blacklist[i]==True:
      continue
    for to in Rways[i]:
      blacklist[to]=False
"""
def b_update(nord):
  global blacklist
  for to in Rways[nord]:
    if blacklist[to]==True:
      blacklist[to]=False
      b_update(to)
      
b_update(N-1)

for c in range(N):
  flag=False
  for i in range(N):
    debit=visited[i]
    if debit==-float("inf"):
      continue
    for to,cost in ways[i]:
      if visited[to]<debit+cost and not blacklist[to]:
        visited[to]=debit+cost
        flag=True
        
  if not flag:
    break
  if c==N-1:
    print(-1)
    exit()
      
ans=visited[-1]
if ans==-float("inf"):
  print(-1)
else:
  print(max(ans,0))
### BUGGY CODE ###

import numpy as np

S = input()
s = len(S)
shift = 10**100
K = shift.bit_length()

ini_ad = np.array([1 if i == "R" else -1 for i in S])

def db(A:list, k:int):
    dv = np.array([[0]*s for _ in range(k+1)])
    dv[0] = A
    for kk in range(1,k+1):
        for n in range(s):
            dv[kk][n] = dv[kk-1][dv[kk-1][n]]
    return dv[k]

a = list(range(s))+ini_ad
for i in range(1,K):
    if (shift >> i)&1:
        a = db(a, i)
ans = [0]*s
for j in a:
    ans[j]+=1
print(*ans)

### FIXED CODE ###

LOG = 18

def main():
    S = input()
    N = len(S)
    to = []
    for _ in range(LOG):
        l = [0]*N
        to.append(l)
        
    for i in range(N):
        to[0][i] = i + 1 if S[i] == "R" else i -1
    
    for i in range(1, LOG):
        for j in range(N):
            to[i][j] = to[i-1][to[i-1][j]]
            
    ans = [0]*N
    for j in range(N):
        ans[to[LOG-1][j]] += 1
        
    print(*ans)
    return

main()
### BUGGY CODE ###

#単純な全探索-->TLE-->Cの配列を扱うときに工夫
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

lst = []
for i in A:
    for j in B:
        lst += [i + j]

lst.sort(reverse = True)
C.sort(reverse = True)

ans = []
for i in range(min(K, len(lst))):
    for j in range(min(K, len(C))):
        ans += [lst[i]+C[j]]

ans.sort(reverse = True)
for i in range(K):
    print (ans[i])


### FIXED CODE ###

#単純な全探索-->TLE-->Cの配列を扱うときに工夫
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

lst = []
for i in A:
    for j in B:
        lst += [i + j]

lst.sort(reverse = True)
C.sort(reverse = True)

ans = []
for i in range(min(K, len(lst))):
    for j in range(min(K, len(C))):
        ans += [lst[i]+C[j]]

ans.sort(reverse = True)
for i in range(K):
    print (ans[i])
### BUGGY CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 1
  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  #print(dp)
  print(dp[length][target])
  
solve(N, S, A)

### FIXED CODE ###

N, S = map(int, input().split())
A = map(int, input().split())
 
def solve(length, target, nums):
  
  dp = [[0]*(target+1) for i in range(length+1)]
  dp[0][0] = 1
  for i, n in enumerate(nums):
    for j, comb_num in enumerate(dp[i]):
      sub = j - n
      dp[i + 1][j] += comb_num * 2
      #print(i, j, sub, dp[i])
      if sub >= 0:
        dp[i + 1][j] += dp[i][sub]
      dp[i + 1][j] %= 998244353
  #print(dp)
  print(dp[length][target])
  
solve(N, S, A)
### BUGGY CODE ###

def upperbound(nums, value):
    low = 0
    high = len(nums)
    while low < high:
        mid = (low + high) >> 1
        if value > nums[mid]:
            low = mid + 1
        else:
            high = mid
    return low


n = int(input())
ar = list(map(int, input().split()))
ar.sort()
total = 0
for i in range(n):
    for j in range(i + 1, n):
        sum2edge = ar[i] + ar[j]
        index = upperbound(ar, sum2edge)
        if index > j:
            total += (index - j - 1)
print(total)

### FIXED CODE ###

def findnumberofTriangles(arr): 
  
    # Sort array and initialize count as 0 
    n = len(arr) 
    arr.sort() 
    count = 0
  
    # Fix the first element. We need to run till n-3 as 
    # the other two elements are selected from arr[i+1...n-1] 
    for i in range(0,n-2): 
  
        # Initialize index of the rightmost third element 
        k = i + 2
  
        # Fix the second element 
        for j in range(i+1,n): 
  
            # Find the rightmost element which is smaller 
            # than the sum of two fixed elements 
            # The important thing to note here is, we use 
            # the previous value of k. If value of arr[i] + 
            # arr[j-1] was greater than arr[k], then arr[i] + 
            # arr[j] must be greater than k, because the array 
            # is sorted. 
            while (k < n and arr[i] + arr[j] > arr[k]): 
                k += 1
  
            # Total number of possible triangles that can be 
            # formed with the two fixed elements is k - j - 1. 
            # The two fixed elements are arr[i] and arr[j]. All 
            # elements between arr[j+1] to arr[k-1] can form a 
            # triangle with arr[i] and arr[j]. One is subtracted 
            # from k because k is incremented one extra in above 
            # while loop. k will always be greater than j. If j 
            # becomes equal to k, then above loop will increment k, 
            # because arr[k] + arr[i] is always greater than arr[k] 
            if(k>j): 
                count += k - j - 1
  
    return count 

n = int(input())
ar = list(map(int, input().split()))
print(findnumberofTriangles(ar))
### BUGGY CODE ###

R,G,B,N = map(int, input().split())
index = 0
ans = 0
for_sort = [R,G,B]
for_sort.sort()
r = for_sort[2]
g = for_sort[1]
b = for_sort[0]
while N >= r*index:
  middle = N - r*index
  index += 1
  index2 = 0
  while middle >= g*index2:
    end = middle - g*index2
    index2 += 1
    if end % b == 0:
      ans += 1
print(ans)    

### FIXED CODE ###

R,G,B,N = map(int, input().split())
index = 0
ans = 0
for_sort = [R,G,B]
for_sort.sort()
r = for_sort[2]
g = for_sort[1]
b = for_sort[0]
while N >=0:
  mid = N
  N -= r
  while mid >= 0:
    if mid % b == 0:
      ans += 1
    mid -= g
      
print(ans)
### BUGGY CODE ###

x, y, z, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
c = [int(_) for _ in input().split()]
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab = sorted(ab)[::-1][:k]
abc = []
for i in range(min(k, x*y)):
    for j in range(z):
        abc.append(ab[i] + c[j])
abc.sort(reverse=True)
for i in range(k):
    print(abc[i])

### FIXED CODE ###

x, y, z, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]
c = [int(_) for _ in input().split()]
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse=True)
abc = []
for i in range(min(k, x*y)):
    for j in range(z):
        abc.append(ab[i] + c[j])
abc.sort(reverse=True)
for i in range(k):
    print(abc[i])
### BUGGY CODE ###

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

### FIXED CODE ###

import collections
count = int(input())
su_list = list(map(int, input().split()))
c = collections.Counter(su_list)
for i in range(1, count + 1):
    print(c[i])
### BUGGY CODE ###

N = int(input())
edge_list = [list(map(int, input().split())) for i in range(N-1)]
colors = [[0 for j in range(N)] for i in range(N)]
reached = [False for i in range(N)]
edges = [[False for i in range(N)] for j in range(N)]
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    edges[a][b] = True
    edges[b][a] = True

color_num = 0
for i in range(N):
    if sum(edges[i]) > color_num:
        color_num = sum(edges[i])


color_stack = [[]]
node_stack = [0]
while len(node_stack) > 0:
    current = node_stack.pop()
    reached[current] = True
    used_colors = color_stack.pop()
    nodes = [i for i in range(len(edges[current])) if edges[current][i] and not reached[i]]
    can_color = [i+1 for i in range(color_num)]
    for color in used_colors:
        can_color.remove(color)
    for node in nodes:
        color = can_color.pop()
        node_stack.insert(0, node)
        color_stack.insert(0, [color])
        colors[current][node] = color
        colors[node][current] = color

print(color_num)
for edge in edge_list:
    a = edge[0] - 1
    b = edge[1] - 1
    print(colors[a][b])



### FIXED CODE ###

from collections import deque
from functools import reduce

n = int(input())
colors = [0]*(n-1)
mat = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1

    mat[a].append((i, b))
    mat[b].append((i, a))

q = deque()
max_len = reduce(lambda a, x:max(a, len(x)), mat, 0)
q.append(0)
while len(q) > 0:
    current = q.popleft()

    used_colors = set([colors[p[0]] for p in mat[current] if colors[p[0]] > 0])
    col = 1

    for p in mat[current]:
        if colors[p[0]] > 0:
            continue
        while col in used_colors:
            col += 1
        colors[p[0]] = col
        col += 1
        q.append(p[1])
print(max_len)
for col in colors:
    print(col)
### BUGGY CODE ###

# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal2 = []
goal1 = []
for i in range(M):
    if A[i][1] == N:
        goal2.append(A[i][0])
    elif A[i][0] == 1:
        goal1.append(A[i][1])
    else:
        pass

for k in range(len(goal1)):
    if goal1[k] in goal2:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


### FIXED CODE ###

# C - Cat Snuke and a Voyage
N,M = map(int, input().split())
A = [list(map(int, input().split())) for i in range(M)]
goal2 = []
goal1 = []
for i in range(M):
    if A[i][1] == N:
        goal2.append(A[i][0])
    elif A[i][0] == 1:
        goal1.append(A[i][1])
    else:
        pass

if len(set(goal1)&set(goal2)) != 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0
    p = [[pow(j, i, mod) for j in range(401)] for i in range(401)]

    for a, b in zip(A, B):
        q = [sum(p[i][a:b+1]) % mod for i in range(c+1)]
        dp = [sum([dp[i-j]*q[j] for j in range(i+1)]) %
              mod for i in range(c+1)]
    ans += dp[-1]
    print(ans % mod)


main()


### FIXED CODE ###

def main():
    mod = 10**9+7
    n, c = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    dp = [0]*(c+1)
    dp[0] = 1
    ans = 0

    p = [[0]*(401) for _ in [0]*401]  # p[i][j]でj^i
    for i in range(401):
        for j in range(401):
            p[i][j] = pow(j, i, mod)

    for a, b in zip(A, B):
        dp2 = [0]*(c+1)
        q = [0]*(c+1)
        for i in range(c+1):
            q[i] = sum(p[i][a:b+1]) % mod
        for i in range(c+1):
            temp = 0
            for j in range(i+1):
                temp += dp[i-j]*q[j]
            dp2[i] = temp % mod
        dp = dp2
    ans += dp[-1]
    print(ans % mod)


main()
### BUGGY CODE ###

#「辺」彩色
#最大次数で可
#構成はset()使って色管理
#Adいらない
n = int(input())
#Ad = [set() for i in range(n)]
Deg = [0]*n
E = []
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    #Ad[ai].add(bi)
    #Ad[bi].add(ai)
    Deg[ai]+=1
    Deg[bi]+=1
    E.append((ai,bi))

cl = max(Deg)
Deg2 = [set(range(cl)) for i in range(n)]
print(cl)
for ai,bi in E:
    c = 0
    while c  not in Deg2[ai] or c not in Deg2[bi]:
        c+=1
    print(c+1)
    Deg2[ai].remove(c)
    Deg2[bi].remove(c)
    


### FIXED CODE ###


n = int(input())
Ad = [[] for _ in range(n)]
Deg = [0]*n
E = {}
E2 =[]
for i in range(n-1):
    ai,bi = map(int, input().split( ))
    ai-=1
    bi-=1
    Ad[ai].append(bi)
    Ad[bi].append(ai)
    Deg[ai] += 1
    Deg[bi] += 1
    E[(ai,bi)]=-1
    E[(bi,ai)]=-1
    E2.append((ai,bi))
mx = max(Deg)
print(mx)
E[(0,0)] = -1#後の都合
P =[-1]*n#parent
from collections import deque
Q = deque()
Q.append(0)
P[0] = 0

while Q:
    v = Q.popleft()
    for u in Ad[v]:
        if P[u]<0:
            P[u] = v
            Q.append(u)

Q = deque()
cnt = 1
for v in Ad[0]:
    E[(0,v)]=cnt
    E[(v,0)]=cnt
    cnt+=1
    Q.append(v)

while Q:
    v = Q.popleft()
    cnt = 1
    for u in Ad[v]:
        if E[(u,v)]<0:
            if cnt==E[(v,P[v])]:
                cnt +=1
            E[(u,v)] = cnt
            E[(v,u)] = cnt
            cnt+=1
            Q.append(u)
for i in range(n-1):
    print(E[E2[i]])
### BUGGY CODE ###

# 解説を参考に作成
# #6716052を参考


def solve():
    S = [-1 if i == '?' else int(i) for i in input()[::-1]]
    dp = [0] * 13
    mod = 10 ** 9 + 7

    if S[0] == -1:
        dp = [1 if i < 10 else 0 for i in range(13)]
    else:
        dp[int(S[0])] = 1
    # print(S)
    for i, s in enumerate(S[1:], 1):
        # print(dp)
        digit = pow(10, i, 13)
        next_dp = [0] * 13
        if s == -1:
            for j in range(10):
                x = (digit * j) % 13
                for k in range(13):
                    next_dp[(x + k) % 13] += dp[k]
            pass
        else:
            x = (digit * s) % 13
            for k in range(13):
                next_dp[(x + k) % 13] += dp[k]
        dp = [ndp % mod for ndp in next_dp]
    # print(dp)
    print(dp[5])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 解説を参考に作成
# #11254823を参考


def solve():
    S = input()
    mod = 10 ** 9 + 7

    '''
    桁数毎・余りの数字ごとのdpを作成するにあたり、mapを作る.
    たとえば新しい数字Yは前の数字Xの右側に新たに桁を作って
        Y = X(前の数字) * 10 + i(0 <= i <= 9)
    と表せる.
    この Y の余りは、
        Y % 13 = ((X % 13) * 10 + i) % 13
    と表せるので、10 * 13 のマップであらかじめ計算しておくことができる.
    このマップを以下で作っている.
        modmap[新しい桁の数字i][新しい余り(Y % 13 = k)] = 前の数字の時の余り(X % 13 = j)
    '''
    modmap = []
    for i in range(10):
        modmap.append([0] * 13)
        for j in range(13):
            k = (j * 10 + i) % 13
            modmap[i][k] = j

    # なぜ最初を1にするのか？
    # → Sの先頭に 0 を固定でつけても結果は変化しない. また付けた場合の最初の計算では余り0となる.
    # → どんなパターンでも共通の初期状態として使用できる.
    dp = [1] + [0] * 12
    for s in S:
        if s == '?':
            dp = [sum(dp[l] for l in modlist) % mod for modlist in zip(*modmap)]
        else:
            modlist = modmap[int(s)]
            dp = [dp[modlist[l]] % mod for l in range(13)]

    print(dp[5])


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

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    left = [[-1]*W for _ in range(H)]
    right = [[-1]*W for _ in range(H)]
    up = [[-1]*W for _ in range(H)]
    down = [[-1]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':        
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            
    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()

### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]

    left = [[-1]*W for _ in range(H)]
    right = [[-1]*W for _ in range(H)]
    up = [[-1]*W for _ in range(H)]
    down = [[-1]*W for _ in range(H)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if j == 0:
                    left[i][j] = 0
                else:
                    left[i][j] = left[i][j-1] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':        
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                if i == 0:
                    up[i][j] = 0
                else:
                    up[i][j] = up[i-1][j] + 1

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            
    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()
### BUGGY CODE ###

n=int(input())
s=[""]*n
st=set()
r=0
for ii in range(n):
  ss=list(input())
  ss.sort()
  ss="".join(ss)
  s[ii]=ss
  st.add(ss)

if len(st)==n:
  print(0)
  exit()
if len(st)==1:
  print((n*(n-1))//2)
  exit()

tp=[[""]*2 for ii in range(len(st))]
ii=0
for sss in st:
  tp[ii][0]=s.count(sss)
  tp[ii][1]=sss
  ii+=1
#tp.sort(reverse=True)

for jj in range(len(tp)):
  """
  if tp[jj][0]==1:
    print(r)
    exit()

  """
  r2=tp[jj][0]
  if r2>1:
    r+=(r2*(r2-1))//2      
    
print(r)

### FIXED CODE ###

n=int(input())
s=[""]*n
st=set()
d={}
for ii in range(n):
  ss=list(input())
  ss.sort()
  ss="".join(ss)
  if ss in st:
    d[ss]+=1
  else:
    d[ss]=1
    st.add(ss)

if len(st)==n:
  print(0)
  exit()
if len(st)==1:
  print((n*(n-1))//2)
  exit()

r=0
for sss in st:
  c=d[sss]
  if c>1:
    r+=(c*(c-1))//2
    
print(r)