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

import sys,bisect
input = sys.stdin.readline

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


res = 0

for i in range(1,30):
    tank = []
    for eb in b:
        tank.append(eb - ((eb>>i)<<i))
    tank.sort()

    cnt = 0

    for elt in a:
        e = elt - ((elt >> i) << i)

        cnt += bisect.bisect_left(tank, (1<<i)-e ) - bisect.bisect_left(tank, (1<<(i-1))-e)
        cnt += bisect.bisect_left(tank, (1<<(i+1))-e ) - bisect.bisect_left(tank, 3*pow(2,i-1)-e)
    
    if cnt%2 != 0:
        res += 1<<(i-1)

print(res)


### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline


def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))


    res = 0
    p = 0

    for i in range(1,30):
        p += 1<<(i-1)
        A = []
        B = []

        for j in range(n):
            A.append(a[j]&p)
            B.append(b[j]&p)
        A.sort()
        B.sort()

        cnt = 0

        q2 = p+1
        q1 = q2>>1
        q3 = q2<<1

        k1,k2,k3,k4 = 0,0,0,0

        for j in range(n-1,-1,-1):
            while k1 < n and A[j]+B[k1] < q1:
                k1 += 1
            while k2 < n and A[j]+B[k2] < q2:
                k2 += 1
            while k3 < n and A[j]+B[k3] < 3*q1:
                k3 += 1
            while k4 < n and A[j]+B[k4] < q3:
                k4 += 1
            cnt += k4 + k2 - k1 - k3

        
        if cnt%2 != 0:
            res += 1<<(i-1)

    print(res)


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

def main():
    S = str(input())
    S += "Z"
    N = len(S)
    for i in range(N-1):
        if S[i] == "B" and S[i+1] == "C":
            S = S[:i]+"DE"+S[(i+2):]
    S = S.replace("E","")
    left = 0
    right = 0
    count = 0
    rep = 0
    ar = 0
    N = len(S)
    while right <= N-1:
        if S[right] == "A":
            right += 1
        elif S[right] == "D":
            count += 1
            rep += right-left
            right += 1
        else:
            ar += rep-(count*(count-1)//2)
            rep = 0
            count = 0
            right += 1
            left = right

    print(ar)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    S = input().replace("BC","D")
    ans = count = 0
    for i in S:
        if i == "A":
            count += 1
        elif i == "D":
            ans += count
        else:
            count = 0

    print(ans)

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

N,M = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
count = 0
for i in range(N-1):
    if ar[i] + ar[i+1] > M:
        while ar[i] + ar[i+1] > M:
            if ar[i+1] == 0:
                ar[i] -= 1
                count += 1
            else:
                ar[i+1] -= 1
                count += 1
print(count)

### FIXED CODE ###

n,m = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
a = sum(ar)
for i in range(n-1):
    if ar[i] + ar[i+1] > m:
        b = (ar[i] + ar[i+1]) - m
        if ar[i+1] >= b:
            ar[i+1] -= b 
        else:
            ar[i] -= b - ar[i+1]
            ar[i+1] = 0
print(a - sum(ar))
### BUGGY CODE ###

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

graph_1 = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            if j != 0 and grid[i][j - 1] == '.':
                graph_1[i][j] = graph_1[i][j - 1] + 1
            else:
                graph_1[i][j] = 1

for i in range(H):
    for j in reversed(range(W - 1)):
        if grid[i][j + 1] == '.' and grid[i][j] == '.':
            graph_1[i][j] = graph_1[i][j + 1]

graph_2 = [[0] * W for _ in range(H)]
for j in range(W):
    for i in range(H):
        if grid[i][j] == '.':
            if i != 0 and grid[i - 1][j] == '.':
                graph_2[i][j] = graph_2[i - 1][j] + 1
            else:
                graph_2[i][j] = 1

for j in range(W):
    for i in reversed(range(H - 1)):
        if grid[i + 1][j] == '.' and grid[i][j] == '.':
            graph_2[i][j] = graph_2[i + 1][j]

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, graph_1[i][j] + graph_2[i][j] - 1)
        
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

graph_1 = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            if j != 0 and grid[i][j - 1] == '.':
                graph_1[i][j] = graph_1[i][j - 1] + 1
            else:
                graph_1[i][j] = 1

for i in range(H):
    for j in reversed(range(W - 1)):
        if grid[i][j + 1] == '.' and grid[i][j] == '.':
            graph_1[i][j] = graph_1[i][j + 1]

graph_2 = [[0] * W for _ in range(H)]
for j in range(W):
    for i in range(H):
        if grid[i][j] == '.':
            if i != 0 and grid[i - 1][j] == '.':
                graph_2[i][j] = graph_2[i - 1][j] + 1
            else:
                graph_2[i][j] = 1

for j in range(W):
    for i in reversed(range(H - 1)):
        if grid[i + 1][j] == '.' and grid[i][j] == '.':
            graph_2[i][j] = graph_2[i + 1][j]

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, graph_1[i][j] + graph_2[i][j] - 1)
        
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
L_r = []
L_g = []
L_b = []
ans = 0
for i in range(N):
    if S[i] == "R":
        L_r.append(i)
    elif S[i] == "G":
        L_g.append(i)
    else:
        L_b.append(i)
m = max(len(L_r),len(L_g),len(L_b))
if len(L_r) == m:
    for x in L_g:
        for y in L_b:
            ans += m
            if 2*x - y in L_r:
                ans -= 1
            if 2*y - x in L_r:
                ans -= 1
            if (x + y) % 2 == 0 and (x + y) // 2 in L_r:
                ans -= 1
elif len(L_g) == m:
    for x in L_r:
        for y in L_b:
            ans += m
            if 2*x - y in L_g:
                ans -= 1
            if 2*y - x in L_g:
                ans -= 1
            if (x + y) % 2 == 0 and (x + y) // 2 in L_g:
                ans -= 1
else:
    for x in L_r:
        for y in L_g:
            ans += m
            if 2*x - y in L_b:
                ans -= 1
            if 2*y - x in L_b:
                ans -= 1
            if (x + y) % 2 == 0 and (x + y) // 2 in L_b:
                ans -= 1
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input())
ans = 0
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans += r*g*b
m = 0
if N >= 3:
  for i in range(N-2):
    for j in range(i+1,N-1):
      k = 2*j-i
      if  k < N and S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        m += 1
print(ans-m)
### BUGGY CODE ###

N=int(input())
S=input()
#print(S[1])
cnt=0
for k in range(1,N+1):
  for j in range(1,k):
    for i in range(1,j):
      if S[i-1]!=S[j-1] and S[i-1]!=S[k-1] and S[j-1]!=S[k-1] and (j-i)!=(k-j):
        cnt += 1
        #print(i,j,k,j-i,k-j, S[i-1],S[j-1],S[k-1])
print(cnt)

### FIXED CODE ###

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

r=S.count('R')
g=S.count('G')
b=S.count('B')
al_num=r*g*b

#全体からj-i=k-jの場合を引く
sub=0
for i in range(0,N):
  for j in range(i+1,N):
    if S[i]==S[j]:
      continue

    k = 2*j -i
    #i,j,kは等差数列なのでkは決まる, k>=Nは不適なのでスキップ
    if k>=N or S[k]==S[i] or S[k]==S[j]:
      continue
    
    sub += 1
print(al_num - sub)
# O(N^2)
### BUGGY CODE ###

#!/usr/bin/env python3
# import itertools
# import numpy as np

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

mod = 998244353

dp = [[0]*(s+1) for _ in range(n+1)]

dp[0][0] = 1

for i in range(0, n):
    for j in range(0, s+1):
        dp[i+1][j] += dp[i][j]*2 % mod

        if j+a[i] <= s:
            dp[i + 1][j + a[i]] += dp[i][j] % mod


print(dp[n][s] % mod)


### FIXED CODE ###

#!/usr/bin/env python3
# import itertools
# import numpy as np

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

mod = 998244353

dp = [[0]*(s+1) for _ in range(n+1)]

dp[0][0] = 1

for i in range(0, n):
    for j in range(0, s+1):
        dp[i+1][j] += dp[i][j]*2 % mod

        if j+a[i] <= s:
            dp[i + 1][j + a[i]] += dp[i][j] % mod


print(dp[n][s] % mod)
### BUGGY CODE ###

from collections import Counter
import sys

# input = lambda : sys.stdin.readline().rstrip()

S = input()
n = len(S)

M = []

for i in range(len(S)):
    m = int(S[i:n]) % 2019
    # print(S[i:n], m)
    M.append(m)

M.append(0)  # S[n:n] = ""が抜けるので、付け加える

c = Counter(M)

sum = 0
for i in c.values():
    sum += i * (i - 1) / 2

print(int(sum))

### FIXED CODE ###

from collections import Counter
import sys

# input = lambda : sys.stdin.readline().rstrip()

S = input()
n = len(S)

M = []
m = 0

for i in range(len(S)-1,-1, -1):
    
    m = (pow(10, n-i, 2019) * int(S[i]) + m) % 2019
    M.append(m)
    
    # print(S[i:n], m)

M.append(0)  # S[n:n] = "" = 0 が抜けるので、付け加える

c = Counter(M)

sum = 0
for i in c.values():
    sum += i * (i - 1) / 2

print(int(sum))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import itertools

def main():
    N = int(input())
    L = [int(x) for x in input().split()]
    ans = 0
    for a, b, c in itertools.combinations(L, 3):
        if a < b + c and b < a + c and c < a + b:
            ans += 1

    print(ans)



    

if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
input = sys.stdin.readline
import itertools
import bisect

def main():
    N = int(input())
    L = [int(x) for x in input().split()]
    ans = 0
    L_sorted = sorted(L)
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            a = L_sorted[i]
            b = L_sorted[j]
            l = bisect.bisect_left(L_sorted, max(a - b, b - a), lo=j + 1)
            r = bisect.bisect_left(L_sorted, a + b, lo=j + 1)
            ans += r - l

    print(ans)



    

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

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

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

    divisors.sort()
    return divisors

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

n = k()

for i in range(1,n):
  a = len(make_divisors(i))
  if a % 2 != 0:
    ans += 2*(a//2) + 1
  else:
    ans += 2*(a//2)

print(ans)

### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

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

    divisors.sort()
    return divisors

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

n = k()

for i in range(1,n):
  for j in range(n//i,0,-1):
    if 1<=i*j<=n-1:
      cnt += 1
      continue

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

s = list(input())
n = len(s)

mod = 10**9+7
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    flag = 1 if s[i]=='?' else 0 #?だったら1
    if flag==1:
        for a in range(10):#i+1桁目の数字(0-9)
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j]#i桁目の余りの10倍とi桁目を足して余りをだす
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
            
print(dp[n][5]%mod)

### FIXED CODE ###

s = list(input())
n = len(s)

mod = 10**9+7
dp = [[0]*13 for i in range(n+1)]
dp[0][0] = 1

for i in range(n):
    flag = 1 if s[i]=='?' else 0 #?だったら1
    if flag==1:
        for a in range(10):#i+1桁目の数字(0-9)
            for j in range(13): #あまり(0-12)
                dp[i+1][(j*10+a)%13] += dp[i][j] #i桁目の余りの10倍とi桁目を足して余りをだす
    else:
        for j in range(13):
            a = int(s[i])
            dp[i+1][(j*10+a)%13] += dp[i][j]
    for j in range(13):
        dp[i+1][j]%=10**9+7
        
print(dp[n][5])
### BUGGY CODE ###

s = input()
while True:
  l = len(s)
  s = s.replace('ST', '')
  if l == len(s):
    break
print(len(s))


### FIXED CODE ###

s = input()
S = 0
T = 0
for i in range(len(s)):
  if s[i] == 'S':
    S += 1
  else:
    if S > 0:
      S -= 1
    else:
      T += 1
print(T * 2)
### BUGGY CODE ###

N, K = map(int, input().split())
XY = [list(map(int, input().split())) for _ in range(N)]
XY.sort()

def count(x_min, x_max, y_min, y_max, i, j):
    cnt = 0
    for m in range(i, j + 1):
        if x_min <= XY[m][0] <= x_max and y_min <= XY[m][1] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N - 1):
    for j in range(i + 1, N):
        for k in range(N):
            for l in range(N):
                if XY[k][1] < XY[l][1] and j - i + 1 >= K:
                    if count(XY[i][0], XY[j][0], XY[k][1], XY[l][1], i, j) >= K:
                        # print ('A')
                        ans = min(ans, (XY[j][0] - XY[i][0]) * (XY[l][1] - XY[k][1]))
print (ans)


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

a,b,c,d  = map(int,input().split())
count = 0

for i in range(a,b+1):
    if i%c!=0 and i%d!=0:
        count = count+1
    else:
        pass
print(count)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
u = b - a + 1
from fractions import gcd
cd = c*d//gcd(c,d)
n_c = b//c - (a-1)//c
n_d = b//d - (a-1)//d
n_cd =b//cd - (a-1)//cd
print(int(u - n_c - n_d + n_cd))
### BUGGY CODE ###

N=int(input())
S=input()
#初めて出てきたときのインデックスをめも
memo=[[-1]*10 for _ in range(10)]
ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        si=int(S[i])
        sj=int(S[j])
        if memo[si][sj]==-1:
            memo[si][sj]=0
            ans+=len(set(S[j+1:]))
print(ans)


### FIXED CODE ###

N=int(input())
S=input()
#初めて出てきたときのインデックスをめも
lmemo=[-1]*10
rmemo=[-1]*10
for i in range(N-2):
    ls=int(S[i])
    rs=int(S[-(i+1)])
    if lmemo[ls]==-1:
        lmemo[ls]=i
    if rmemo[rs]==-1:
        rmemo[rs]=N-(i+1)
ans=0
#print(lmemo,rmemo)
for l in lmemo:
    for r in rmemo:
        if l+1<r and l>=0 and r>=0:
            ans+=len(set(S[l+1:r]))


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

# input here
_INPUT = """\
10 2
4
5
"""
"""
K = int(input())
H, W, K = map(int, input().split())
a = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(N)]
p = tuple(map(int,input().split()))
"""
def main():
    N, M = map(int, input().split())
    a = [int(input()) for i in range(M)]

    #動的計画法問題
    dp = [0] * (10**5+1)
    dp[0] = 1
    if 1 not in a:
        dp[1] = 1

    for i in range(2,N+1):
        if (i-1 in a)&(i-2 in a):
            print(0)
            quit()

        if i-1 in a:
            dp[i] = dp[i-2]
        elif i-2 in a:
            dp[i] = dp[i-1]
        else:
            dp[i] = dp[i-1] + dp[i-2]

    print(dp[N]%(10**9+7)) 




            
if __name__ == '__main__':
    import io
    import sys
    import math
    import itertools
    from collections import deque

    # sys.stdin = io.StringIO(_INPUT)
    main()

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

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

n, m = map(int, input().split())
for i in reversed(range(m // n + 1)):
  if m % i == 0:
    print(i)
    exit()

### FIXED CODE ###

def f():
  n, m = map(int, input().split())
  for i in range(m//n+1)[::-1]:
    if m%i==0:return i
print(f())
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
from functools import reduce
from operator import mul


def two(a,ans):
    if a%2==0:
        return two(a//2,ans+1)
    else:
        return ans

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

ans1=0
#ans2=0
p=reduce(mul,A)
ans1=two(p,ans1)
#for i in range(N):
#    ans2=two(A[i],ans2)
print(ans1)

### FIXED CODE ###

from functools import reduce
from operator import mul

def two(a,ans):
    if a%2==0:
        return two(a//2,ans+1)
    else:
        return ans

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

#ans1=0
ans2=0
#p=reduce(mul,A)
#ans1=two(p,ans1)
for i in range(N):
    ans2=two(A[i],ans2)
print(ans2)
### BUGGY CODE ###

s = input()
count = int(input())
flg = False
for i in range(count):
    tfc = input().split()
    if tfc[0] == "1":
        flg = not flg
    elif tfc[0] == "2":
        if (not flg and tfc[1] == "1") or (flg and tfc[1] == "2"):
            s = tfc[2] + s
        elif (flg and tfc[1] == "1") or (not flg and tfc[1] == "2"):
            s = s + tfc[2]

if flg:
  s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
count = int(input())
flg = False
top = ""
for i in range(count):
    tfc = input().split()
    if tfc[0] == "1":
        flg = not flg
    elif tfc[0] == "2":
        if (not flg and tfc[1] == "1") or (flg and tfc[1] == "2"):
            top = top + tfc[2]
        elif (flg and tfc[1] == "1") or (not flg and tfc[1] == "2"):
            s = s + tfc[2]

if flg:
    s = s[::-1] + top
else:
    s = top[::-1] + s 
print(s)
### BUGGY CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1)) % mod

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        leftpatt, rightpatt = mult(leftA, leftQ, mod), mult(rightC, rightQ, mod)
        leftQ += (1 if S[i] == "?" else 0)
        count += leftpatt * rightpatt
        count %= mod
    else:
        leftA += (1 if S[i] == "A" else 0)
        rightC -= (1 if S[i] == "C" else 0)
print(count)

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)
### BUGGY CODE ###

from collections import Counter

N=int(input())
L=[]
for i in range(N):
    si=input()
    ci=Counter(si)
    L.append(ci)


ans=0

for i in range(N):
    for j in range(1,N-i):
        # print('i:{0} j:{1} L{2}:{3} L{4}:{5} TF:{6}'.format(i,j,i,L[i],i+j,L[i+j],L[i]==L[i+j]))
        if L[i]==L[i+j]:
            ans+=1
        else:
            pass

print(ans)

### FIXED CODE ###

from collections import Counter

N=int(input())
dic={}

ans=0

for i in range(N):
    si=input()
    # ci=Counter(si)
    # c=sorted(ci.elements())
    # c=sorted(Counter(si).elements())
    sorted_s=''.join(sorted(Counter(si).elements()))
    if sorted_s in dic:
        ans+=dic[sorted_s]
        dic[sorted_s]+=1
    else:
        dic[sorted_s]=1
print(ans)
### BUGGY CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[4040404040000000]
for i in range(len(a)):
    m+=a[i]
    mins=min(s)
    s.append(abs(sum(a)-m*2))
    if mins<s[i]:
        break
print(min(s))

### FIXED CODE ###

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

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

inf = 10 ** 4 + 1
dp = [inf] * N
dp[0] = 0
dp[1] = abs(h[1]- h[0])
for i in range(2, N):
    H = h[i]
    dp[i] = min( [dp[j] + abs(h[j] - H) for j in range(max(0, i-K),i)])
print(dp[N-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

s = input()
stop = 0
while stop == 0:
    ls = list(s)
    for i in range(len(ls)-1):
        if ls[i] == "S" and ls[i+1] == "T":
            ls[i], ls[i+1] = "", ""
    new_s = "".join(ls)
    if s == new_s:
        stop = 1
    else:
        s = new_s 
print(len(s))

### FIXED CODE ###

s = input()

del_list = [] 
l = 0
pointer = 0
for i,v in enumerate(s):
    if v == "S":
        del_list.append([i,-1])
        l += 1
    else:
        if l != 0 and pointer != l:
            del_list[pointer][1]  = i
            pointer += 1


rems = 0
delpair = 0
for i in del_list:
    if i[1] == -1:
        rems += 1
    else:
        delpair += 1

remt = s.count("T") - delpair
print(remt+rems)
### BUGGY CODE ###

N = int(input())

LL = []
for count in range(N):
    LL.append(str(input()))
LLCount = []
for count in range(N):
    LLCount.append(LL.count(LL[count]))

LLS = []
ss = max(LLCount)

for count in range(N):
    if LLCount[count] == ss:
        LLS.append(LL[count])

ans = list(dict.fromkeys(LLS))
ans.sort()
for aa in ans:
    print(aa)


### FIXED CODE ###

N= int(input())

dict = {}
for count in range(N):
    tcount = 0
    S= str(input())
    
    if S in dict.keys():
        tcount = dict[S] + 1
        dict.pop(S)
        dict[S] = tcount
    else:
        dict[S] = 1

maxval = max(dict.values())

keys = [k for k, val in dict.items() if val == maxval]
keys.sort()

for count in range(len(keys)):
    print(keys[count])
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))

ans = 0
for i in range(n - 1):
    if a_list[i] == 0:
        continue
    for j in range(i + 1, n):
        ans += a_list[i] * a_list[j]
        if ans > 10 ** 9 + 6:
            ans = ans % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))
ans = 0
total = 0
mod = 10 ** 9 + 7
for i in range(n):
    total += a_list[i]
    if total >= mod:
        total = total % mod

for i in range(n - 1):
    total -= a_list[i]
    if total < 0:
        total += mod
    ans += a_list[i] * total
    if ans >= mod:
        ans = ans % mod
print(ans)