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

#!/usr/bin/env python3
from collections import Counter

def main():
    S = input()
    N = len(S)
    T = [0] * (N+1)
    
    for i in range(N-1,-1,-1):
        T[i] = (T[i+1] + int(S[i]) * (10**(N-i))) % 2019
    l = Counter(T)
    ans = 0
    for v in l.values():
        ans += v * (v-1) // 2
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter

def main():
    S = input()
    N = len(S)
    T = [0] * (N+1)
    
    for i in range(N-1,-1,-1):
        T[i] = (T[i+1] + int(S[i]) * pow(10,N-i,2019)) % 2019
    l = Counter(T)
    ans = 0
    for v in l.values():
        ans += v * (v-1) // 2
    print(ans)

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

import heapq

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()))

sums = []
for ai in a:
    for bi in b:
        for ci in c:
            heapq.heappush(sums, -(ai + bi + ci))

cnt = 0
while (cnt < k):
    print(-heapq.heappop(sums))
    cnt += 1


### FIXED CODE ###

import heapq

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()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

cnt = 0
q = []
arg = (0, 0, 0)
visited = {}
visited[arg] = True
heapq.heappush(q, (-(a[arg[0]] + b[arg[1]] + c[arg[2]]),) + arg)

while cnt < k:
    score, ia, ib, ic = heapq.heappop(q)
    print(-score)
    cnt += 1
    arg_a = (ia + 1, ib, ic)
    arg_b = (ia, ib + 1, ic)
    arg_c = (ia, ib, ic + 1)
    if arg_a[0] <= x - 1 and arg_a not in visited:
        heapq.heappush(
            q, (-(a[arg_a[0]] + b[arg_a[1]] + c[arg_a[2]]),) + arg_a)
        visited[arg_a] = True
    if arg_b[1] <= y - 1 and arg_b not in visited:
        heapq.heappush(
            q, (-(a[arg_b[0]] + b[arg_b[1]] + c[arg_b[2]]),) + arg_b)
        visited[arg_b] = True
    if arg_c[2] <= z - 1 and arg_c not in visited:
        heapq.heappush(
            q, (-(a[arg_c[0]] + b[arg_c[1]] + c[arg_c[2]]),) + arg_c)
        visited[arg_c] = True
### BUGGY CODE ###

import heapq
from collections import deque
from functools import lru_cache

N,K = map(int,input().split())
lim = min(N,K)
V = list(map(int,input().split()))
D = V.copy()
have = []
heapq.heapify(have)

#@lru_cache(maxsize = None)
def recur(d,h,n):
  if n == lim:
    #print(h)
    return sum(h)
  else:
    a = d[0]
    b = d[-1]
    ha = h.copy()
    hb = h.copy()
    heapq.heappush(ha,a)
    heapq.heappush(hb,b)
    reta = recur(d[1:],ha,n + 1)
    retb = recur(d[:-1],hb,n + 1)
    if len(h) == 0:
      return max(reta,retb)
    else:
      heapq.heappop(h)
      retc = recur(d,h,n + 1)
      return max(reta,retb,retc)
    
print(max(recur(D,have,0),0))

### FIXED CODE ###

import heapq
from collections import deque
from functools import lru_cache

N,K = map(int,input().split())
V = list(map(int,input().split()))
ans = 0

for l in range(0,K + 1):
  for r in range(0,K - l + 1):
    d = K - r - l
    tmp = 0
    have = []
    if l + r > N:
      continue
    for i in range(0,l):
      tmp += V[i]
      have.append(V[i])
    for j in range(N - r,N):
      tmp += V[j]
      have.append(V[j])
    h = len(have)
    #print(have)
    have = sorted(have)
    for k in range(0,d):
      #print(have,sum(have))
      if k >= h:
        break
      if have[k] > 0:
        break
      tmp -= have[k]
    ans = max(tmp,ans)
    
print(ans)
### BUGGY CODE ###

n=int(input())
mod=(10**9)+7
ans=1
for i in range(1,n+1):
    ans*=i
print(ans%mod)


### FIXED CODE ###

n=int(input())
mod=(10**9)+7
import math
a=math.factorial(n)
# ans=1
# for i in range(1,n+1):
#     ans*=i
print(a%mod)
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    l = list(map(str,input().split()))
    if l[0] == "1":
        s = s[::-1]
    elif l[1] == "1":
        s = l[2]+s
    elif l[1]=="2":
        s = s + l[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
Q = [list(map(str, input().split())) for _ in range(q)]

t = ''
for qi in Q:
  if int(qi[0]) == 1:
    s, t = t, s
  else:
    if int(qi[1])  == 1:
      t += qi[2]
    else:
      s += qi[2]
      
t = t[::-1]
t += s
print(t)
### BUGGY CODE ###

a,b,n=map(int,input().split())
'''
lst=[]
for i in range(n+1):
    now=int(a*i/b)-a*int(i/b)
    lst.append(now)
print(max(lst))
'''
now=0
if n>=b:
    if n//b>=500000:
        ans=int(a*(n-1)/b)-a*int((n-1)/b)
        ans2=int(a*n/b)-a*int(n/b)
        for i in range(0,n//b+1,10):
            ans3=int(a*(i*b-1)/b)-a*int((i*b-1)/b)
            now=max(now,ans3)
        print(max(ans,ans2,now))
        exit()
    ans=int(a*(n-1)/b)-a*int((n-1)/b)
    ans2=int(a*n/b)-a*int(n/b)
    for i in range(n//b+1):
        ans3=int(a*(i*b-1)/b)-a*int((i*b-1)/b)
        now=max(now,ans3)
    print(max(ans,ans2,now))

else:
    ans=int(a*(n)/b)-a*int((n)/b)
    print(max(ans,0))

### FIXED CODE ###

a,b,n=map(int,input().split())
def ans(x):
    return int(a*x/b)
print(ans(min(n,b-1)))
### BUGGY CODE ###

n = int(input())
X = list(map(int,input().split()))
medIndex=int((n-1)/2)
for i in range(n) :
  Y = X[:]
  Y.pop(i)
  Y.sort()
  print(Y[medIndex])

### FIXED CODE ###

n = int(input())
X = list(map(int,input().split()))
medIndex = int((n-1)/2)
Z = sorted(X[:])
c1 = Z[int(n/2-1)]
c2 = Z[int(n/2)]
for i in range(n) :
  if (X[i] <= c1) :
    print(c2)
  else :
    print(c1)
### BUGGY CODE ###

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

B = []

for i in A:
    B.append(str(i))
    B = list(reversed(B))
print(" ".join(B))

### FIXED CODE ###

n = int(input())

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

B = []
C = []

for i in range(n):
    if i % 2 == 0:
        B.append(str(A[i]))
    else:
        C.append(str(A[i]))

if n % 2 == 0:
    s = " ".join(list(reversed(C)))
    t = " ".join(B)
    print(s + " " + t)
else:
    s = " ".join(list(reversed(B)))
    t = " ".join(C)
    print(s + " " + t)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
quests = []
for _ in range(q):
    quests.append(tuple(map(int, input().split())))

check = []
for i in range(len(s)-1):
    temp = s[i:i+2]
    if temp == "AC":
        check.append(i)

for quest in quests:
    cnt = 0
    begin = quest[0]-1
    end = quest[1]-1
    for c in check:
        if begin <= c and (c+1) <= end:
            cnt += 1
    
    print(cnt)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
quests = []
for _ in range(q):
    quests.append(tuple(map(int, input().split())))

check = []
for i in range(len(s)-1):
    temp = s[i:i+2]
    if temp == "AC":
        check.append(i)

check_begin = [0 for i in range(len(s))]
check_num = 0
for i in range(len(s)):
    if check_num != len(check) and (check[check_num]+1) == i :
        check_num += 1
    check_begin[i] = check_num

#print(check_begin)

check_end = [len(check)-i for i in check_begin]

for quest in quests:
    begin = quest[0]-1
    end = quest[1]-1
    cnt = len(check) - check_begin[begin] - check_end[end]
    print(cnt)
### BUGGY CODE ###

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

for i in range(m[1]):
    a[a.index(max(a))] = a[a.index(max(a))]//2

print(sum(a))

### FIXED CODE ###

import heapq

m = list(map(int,input().split()))
a = list(map(int,input().split()))
for i in range(len(a)):
  a[i] = a[i]*-1

heapq.heapify(a)

for i in range(m[1]):
     k= heapq.heappop(a)
     heapq.heappush(a, -(-k//2))

print(sum(a)*-1)
### BUGGY CODE ###

from collections import deque
def bfs(succs, preds, start, colors):
    saisyoku = {}
    queue = deque([start])
    while queue:
        v = queue.popleft()
        color_v = colors.copy()
        for u in preds[v]:
            color_v.remove(saisyoku[preds[v][u]])
        for w in succs[v]:
            saisyoku[succs[v][w]] = color_v.pop(0)
            queue.append(w)
    return saisyoku

n = int(input())
vertices = range(1, n+1)
edges = [list(map(int, input().split())) for _ in range(n-1)]
jisu = {v: 0 for v in vertices}
succs = {v: {} for v in vertices}
preds = {v: {} for v in vertices}
for i, (u, v) in enumerate(edges):
  succs[u][v] = i
  preds[v][u] = i
  jisu[u] += 1
  jisu[v] += 1
#print(succs)
#print(preds)
color_num = max(jisu.values())
print(color_num)
colors = list(range(1, color_num+1))
saisyoku = bfs(succs, preds, 1, colors)
for _, c in sorted(saisyoku.items()):
    print(c)

### FIXED CODE ###

from collections import deque
def bfs(succs, preds, start):
    saisyoku = {}
    queue = deque([start])
    used = 0
    while queue:
        v = queue.popleft()
        for u in preds[v]:
            used = saisyoku[preds[v][u]]
        c = 1
        for w in succs[v]:
            if used and c == used:
                c += 1
            saisyoku[succs[v][w]] = c
            queue.append(w)
            c += 1
    return saisyoku
  
n = int(input())
vertices = range(1, n+1)
edges = [list(map(int, input().split())) for _ in range(n-1)]
jisu = {v: 0 for v in vertices}
succs = {v: {} for v in vertices}
preds = {v: {} for v in vertices}
for i, (u, v) in enumerate(edges):
  succs[u][v] = i
  preds[v][u] = i
  jisu[u] += 1
  jisu[v] += 1
colors = max(jisu.values())
print(colors)
saisyoku = bfs(succs, preds, 1)
for _, c in sorted(saisyoku.items()):
    print(c)
### BUGGY CODE ###

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


D = [0]*(10**6+1)
for i in A:
    # ダブってる値は2以上に
    D[i] += 1
U = []
for i in A:
    # 一つしかないものを選ぶ
    if D[i] == 1:
        U.append(i)

T = [False]*(10**6+1)
for i in A:
    # iの2以上の倍数の値はTrueに
    for j in range(i*2, 10**6+1, i):
        T[j] = True

# TがFalseかつDが1の数を数える
ans = 0
for i in U:
    if T[i] == False:
        ans += 1

print(ans)

### FIXED CODE ###

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

cnt = [0] * ((10 ** 6) + 1)

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0] * ((10 ** 6) + 1)

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0
        
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

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

a = input()
b = input()

aa = len(a)

bb = len(b)

dp = [[0]*(bb+1) for i in range(aa+1)]

for i in range(aa):
	for j in range(bb):
		if a[i] == b[j]:
			dp[i+1][j+1] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

ans = ""

while aa > 0 and bb > 0:
	if a[aa-1] == b[bb-1]:
		aa -= 1
		bb -= 1
		ans += a[aa]
	elif dp[aa][bb-1] > dp[aa-1][bb]:
		bb -= 1
	else:
		aa -= 1
print(ans[::-1])

### FIXED CODE ###

a = input()
b = input()

aa = len(a)

bb = len(b)

dp = [[0]*(bb+1) for i in range(aa+1)]

for i in range(aa):
	for j in range(bb):
		if a[i] == b[j]:
			dp[i+1][j+1] = dp[i][j] + 1
		else:
			dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

ans = ""

while aa > 0 and bb > 0:
	if a[aa-1] == b[bb-1]:
		aa -= 1
		bb -= 1
		ans += a[aa]
	elif dp[aa][bb-1] > dp[aa-1][bb]:
		bb -= 1
	else:
		aa -= 1
print(ans[::-1])
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
p_list = [True for i in range(n)]
for i in range(1,n):
    for j in range(i):
        if p[i] > p[j]:
            p_list[i] = False
            break
print(p_list.count(True))

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
q = p[0]
count = 1
for i in range(1,n):
    if q > p[i]:
        count += 1
    q = min(q, p[i])
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = 10**9+7
s = 0
for i in range(n-1):
  c = 0
  for j in range(i+1,n):
    c += a[j]
  s += a[i] * c
print(s % b)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = 0
c = sum(a)
for i in range(n-1):
  c -= a[i]
  s += a[i] * c
print(s % (10**9+7))
### BUGGY CODE ###

n, m = map(int, input().split())
joblist = []
for _ in range(n):
    a, b = map(int, input().split())
    joblist.append([a, b])
joblist.sort(reverse=True)
ans = 0
jobable = []
for i in range(1, m+1):
    for j in range(n):
        if joblist:
            if joblist[-1][0] == i:
                jobable.append(joblist[-1][1])
                joblist.pop()
            else:
                break
        else:
            break
    if jobable:
        k = max(jobable)
        ans += k
        jobable.remove(k)
print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
work = [0]*n
for i in range(n):
  work[i] = list(map(int, input().split()))

work.sort()
k = 0
workable = []
heapq.heapify(workable)
ans = 0
for i in range(m):
  while k < n:
    if work[k][0] <= i+1:
      heapq.heappush(workable, -work[k][1])
      k += 1
    else:
      break
  if workable:
    ans += -heapq.heappop(workable)
print(ans)
### BUGGY CODE ###

import math
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            f = math.gcd(a,b)
            g = math.gcd(f,c)
            sumval += g
print(sumval)

### FIXED CODE ###

import math
K = int(input())
sumval = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        f = math.gcd(a,b)
        for c in range(1, K+1):
            g = math.gcd(f,c)
            sumval += g
print(sumval)
### BUGGY CODE ###

n=int(input())
a=[0]+list(map(int,input().split()))+[0]
for i in range(1,n+1):
  data=a[:i]+a[i+1:]
  ans=0
  for j in range(n):
    ans+=abs(data[j]-data[j+1])
  print(ans)

### FIXED CODE ###

n=int(input())
a=[0]+list(map(int,input().split()))+[0]
data=[]
for i in range(n+1):
  data.append(abs(a[i]-a[i+1]))
s=sum(data)
for i in range(n):
  print(s-data[i]-data[i+1]+abs(a[i]-a[i+2]))
### BUGGY CODE ###

s=input()
n=int(s)
m=len(s)
if n<2019:
    print(0)
    exit()
from collections import Counter
c=Counter()
for i in range(m+1):
    c[(n%(pow(10,i)))%2019]+=1

ll=c.most_common()
ans=0
for i,j in ll:
    if j>=2:
        ans+=j*(j-1)//2
    else:
        break
print(ans)


### FIXED CODE ###

s=[int(j) for j in input()][::-1]
c=[0]*2019
tmp=0
c[0]+=1
t=1
import numpy as np
for i in s:
    tmp+=t*i
    c[tmp%2019]+=1
    t=t*10%2019
c=np.array(c)
ans=c*(c-1)//2
print(ans.sum())
### BUGGY CODE ###

def input_from_console():
    r, g, b, n = map(int, input().split())

    return r, g, b, n


def main():
    r, g, b, n = input_from_console()
    counter = 0
    r, g, b = sorted([r, g, b], reverse=True)
    # print(r,g,b)
    for i1 in reversed(range(int(n / r) + 1)):
        n1 = n - r * i1
        for i2 in reversed(range(int(n1 / g) + 1)):
            n2 = n1 - g * i2
            # print(n2, i1, i2)
            if r * i1 + g * i2 + b * (n - i1 - i2) < n2:
                break
            for i3 in reversed(range(int(n2 / b) + 1)):
                # print(i1, i2, i3, r * i1 + g * i2 + b * i3)
                n_new = r * i1 + g * i2 + b * i3
                if r * i1 + g * i2 + b * i3 == n:
                    counter += 1
                    break
                elif n_new < n:
                    break

    print(counter)


if __name__ == "__main__":
    main()

### FIXED CODE ###


def input_from_console():
    r, g, b, n = map(int, input().split())

    return r, g, b, n


def main():
    r, g, b, n = input_from_console()
    counter = 0
    r, g, b = sorted([r, g, b], reverse=True)
    for i1 in reversed(range(int(n / r) + 1)):
        n1 = n - r * i1
        for i2 in reversed(range(int(n1 / g) + 1)):
            n2 = n1 - g * i2
            if n2 % b == 0:
                counter += 1
    print(counter)


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

from collections import Counter
import math

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

if N == set(A):
    for _ in range(N):
        print(0)

c2 = math.factorial(2)
umemory = {}
dmemory = {}
memory = {}

count = Counter(A)

for k, v in count.items():
    umemory[k] = 0 if v < 2 else math.factorial(v) // (math.factorial(v - 2) * c2)
    dmemory[k] = 0 if v < 3 else math.factorial(v-1) // (math.factorial(v - 3) * c2)

for k in range(0, N):
    a = A[k]
    if a in memory:
        result = memory[a]
    else:
        memory[a] = sum(map(lambda kv: kv[1], filter(lambda kv: kv[0] != a, umemory.items())))
        memory[a] += dmemory[a]
        result = memory[a]
    print(result)

### FIXED CODE ###

from collections import Counter
import math

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

c = Counter(A)

all_ans = 0
for n in c.values():
    if n <= 1:
        continue
    all_ans += math.factorial(n)//(math.factorial(n-2)*math.factorial(2))

for n in A:
    print(all_ans - (c[n]-1))
### BUGGY CODE ###

s=input()
n=len(s)
a=0
b=1
M=10**9+7
for i in range(n):
  if'0'<s[i]:
    a=(a+b*pow(3,n-i-1,M))%M
    b*=2
print((a+b)%M)

### FIXED CODE ###

def main():
  s=input()
  n=len(s)
  a,b,M=0,1,10**9+7
  p=[1]
  for i in range(n-1):
    p.append(p[i]*3%M)
  for i,t in enumerate(map(int,s)):
    if t:
      a=(a+b*p[~i])%M
      b=b*2%M
  print((a+b)%M)
main()
### BUGGY CODE ###

import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

mod = 1000000007

"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    N , M = map(int, sys.stdin.readline().split())
    A = [int(sys.stdin.readline()) for _ in range(M)]
    L = [0] * (N + 1)
    L[0] = 1
    if 1 not in A:
        L[1] = 1
    for i in range(2, N + 1):
        if i not in A:
            L[i] = L[i - 1] + L[i - 2]
    print(L[N] % mod)



### FIXED CODE ###

# n=int(input())
# a,b=map(int, input().split())
# c=list(map(int, input().split()))
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a=100
# b=0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋めのときの出力
# 000100-0.987654

import numpy as np
import math
import copy
import itertools

mod  = 1000000007

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

broken = [0 for _ in range(N + 2)]

for i in range(M):
    n = int(input())
    broken[n] = True

dp = [0 for _ in range(N + 2)]
dp[N] = 1
for i in range(0, N)[::-1]:
    if broken[i]:
        dp[i] = 0
        continue
    dp[i] = (dp[i + 1] + dp[i + 2]) % mod

print(dp[0])
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))

MOD = 10 ** 9 + 7

dp0 = [[0] * 2005 for _ in range(2005)]
dp1 = [[0] * 2005 for _ in range(2005)]

dp0[0][0] = 1
for i in range(N + 1):
    for j in range(M + 1):
        dp0[i + 1][j] += dp0[i][j]
        dp1[i][j] += dp0[i][j]
        dp1[i][j + 1] += dp1[i][j]
        if i < N and j < M and S[i] == T[j]:
            dp0[i + 1][j + 1] += dp1[i][j]
        dp0[i][j] %= MOD
        dp1[i][j] %= MOD
        
ans = dp1[N][M]
print (ans)



### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    S = list(map(int, input().split()))
    T = list(map(int, input().split()))

    MOD = 10 ** 9 + 7

    dp0 = [[0] * 2005 for _ in range(2005)]
    dp1 = [[0] * 2005 for _ in range(2005)]

    dp0[0][0] = 1
    for i in range(N + 1):
        for j in range(M + 1):
            dp0[i + 1][j] += dp0[i][j]
            dp1[i][j] += dp0[i][j]
            dp1[i][j] %= MOD
            dp1[i][j + 1] += dp1[i][j]
            if i < N and j < M and S[i] == T[j]:
                dp0[i + 1][j + 1] += dp1[i][j]
            dp1[i][j] %= MOD
            dp0[i + 1][j] %= MOD
            dp1[i][j + 1] %= MOD
            dp0[i + 1][j + 1] %= MOD

    ans = dp1[N][M] % MOD
    print (ans)
    return 

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

import collections
N=int(input())
s=[]
for _ in range(N):
    s.append(str(collections.Counter(sorted(list(input())))))

print(int(sum(list(map(lambda x: x*(x-1)/2*1, list(collections.Counter(s).values()))))))

### FIXED CODE ###

import collections
N=int(input())
s=["".join(sorted(input())) for _ in range(N)]
print(int(sum(list(map(lambda x: x*(x-1)/2*1, collections.Counter(s).values())))))
### BUGGY CODE ###

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), 400)

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))


### FIXED CODE ###

n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))
### BUGGY CODE ###

mod = 10 ** 9 + 7
S = input()[::-1]
W = [1, 10, 9, 12, 3, 4]

dp = [[0] * 13 for _ in range(len(S))]

for i, s in enumerate(S):
    if i == 0:
        if s == "?":
            for j in range(10):
                dp[0][j] = 1
        else:
            dp[0][int(s)] = 1
        continue

    w = W[i % 6]
    if s == "?":
        for n in range(10):
            for j in range(13):
                r = (j + n * w) % 13
                dp[i][r] = (dp[i][r] + dp[i - 1][j]) % mod

    else:
        n = int(s)
        for j in range(13):
            r = (j + n * w) % 13
            dp[i][r] = (dp[i][r] + dp[i - 1][j]) % mod

print(dp[len(S) - 1][5])


### FIXED CODE ###


mod = 10 ** 9 + 7
S = input()[::-1]
W = [1, 10, 9, 12, 3, 4]

dp = [[0] * 13 for _ in range(len(S))]

for i, s in enumerate(S):
    if i == 0:
        if s == "?":
            for j in range(10):
                dp[0][j] = 1
        else:
            dp[0][int(s)] = 1
        continue

    w = W[i % 6]
    if s == "?":
        for n in range(10):
            r = (n * w) % 13
            for j in range(13):
                dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

    else:
        n = int(s)
        r = (n * w) % 13
        for j in range(13):
            dp[i][(j + r) % 13] = (dp[i][(j + r) % 13] + dp[i - 1][j]) % mod

print(dp[len(S) - 1][5])