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

def ncr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] //= pivot
                denominator[k] //= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
    return int(result)
  
n, a, b = map(int, input().split())
whole_sum = (2 ** n) - 1
mod = 10 ** 9 + 7

whole_sum -= ncr(n, a)
whole_sum -= ncr(n, b)

print(whole_sum % mod)


### FIXED CODE ###

#D 復習
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
whole_sum = pow(2, n, mod) - 1

def combinations_mod(n, k, mod):
    X, Y = 1, 1
    for i in range(1, k+1):
        X = (X * (n-i+1))%mod
    for j in range(1, k+1):
        Y = (Y*j)%mod
    result = X * (pow(Y, mod-2, mod))
    return result%mod

whole_sum -= combinations_mod(n, a, mod)
whole_sum -= combinations_mod(n, b, mod)

print(whole_sum % mod)
### BUGGY CODE ###

from collections import defaultdict

N, M, K = map(int, input().split())
F = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(M)]
B = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(K)]


class DisjointSet():
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


d = DisjointSet(N)
friends = defaultdict(list)
for Ai, Bi in F:
    d.unite(Ai, Bi)
    friends[Ai].append(Bi)
    friends[Bi].append(Ai)
group = defaultdict(int)
for i in range(N):
    group[d.find(i)] |= 1 << i
blocking = defaultdict(int)
for Ci, Di in B:
    blocking[Ci] |= 1 << Di
    blocking[Di] |= 1 << Ci

ans = [0] * N
for i in range(N):
    bit_g = group[d.find(i)] & ~blocking[i]
    while bit_g:
        ans[i] += bit_g & 1
        bit_g >>= 1
    ans[i] -= len(friends[i]) + 1
print(' '.join(list(map(str, ans))))


### FIXED CODE ###

from collections import defaultdict

N, M, K = map(int, input().split())
F = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(M)]
B = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(K)]


class DisjointSet():
    def __init__(self, n):
        self.root = [-1] * n

    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.root[self.find(x)]


d = DisjointSet(N)
friends = defaultdict(int)
for Ai, Bi in F:
    d.unite(Ai, Bi)
    friends[Ai] += 1
    friends[Bi] += 1
blocking = defaultdict(list)
for Ci, Di in B:
    blocking[Ci].append(Di)
    blocking[Di].append(Ci)

ans = [0] * N
for i in range(N):
    ans[i] = d.size(i) - friends[i] - 1
    for b in blocking[i]:
        if d.same(i, b):
            ans[i] -= 1
print(' '.join(list(map(str, ans))))
### BUGGY CODE ###

a,b = map(int,input().split())
import math 
import fractions
def is_prime(n):
	if n == 1: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

#ユークリッドの互除法
gc = fractions.gcd(a,b)
if gc == 1:
	print(1)
	exit()


cout = 1 #1がfalse判定される
for i in range(1,gc+1):
	if a % i == 0 and b % i == 0:
		if is_prime(i):
			cout+= 1
print(cout)

### FIXED CODE ###

import fractions
a,b = map(int,input().split())
"""素因数分解"""
def factrize(n):
	b = 2
	fct = []
	while b*b <= n:
		while n % b == 0:
			n //= b
			#もし素因数を重複させたくないならここを加えてfct.append(b)を消す
			
			if not b in fct:
				fct.append(b)
			
			
		b = b+1
	if n > 1:
		fct.append(n)
	return fct #リストが帰る

gc = fractions.gcd(a,b)

ans = factrize(gc)
print(len(ans)+1)
### BUGGY CODE ###

n,m = map(int,input().split())
l = [list(map(int,input().split())) for i in range(n)]
ans = [0]*(m+1)

l.sort(key = lambda x: x[1],reverse=True)

for i in range(n):
    a,b = l[i]
    for j in range(a,m+1):
        if ans[j] == 0:
            ans[j] = b
            break
print(sum(ans))




### FIXED CODE ###

def main():
    import heapq
    n,m = map(int,input().split())
    l = [list(map(int,input().split())) for i in range(n)]
    l.sort()
    q = []
    ans = 0
    now = 0
    for i in range(1,m+1):
        for j in range(now,n):
            if l[j][0] <= i:
                heapq.heappush(q,-l[j][1])
                now = j+1 
            else:
                now = j
                break
        if q:
            ans -= heapq.heappop(q)
       
    print(ans)

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

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

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M)[:: -1]:
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, i):
                isNess[j] = True
            break

ans += sum(isNess)
print(N - ans)

### FIXED CODE ###

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

A = []
for a in _A:
    if a >= K:
        ans += 1
    else:
        A.append(a)

A.sort(reverse=True)
M = len(A)
isNess = [False] * M

accA = [0] * (M + 1)
for i in range(1, M + 1):
    accA[i] = accA[i - 1] + A[i - 1]

left = 0
for right in range(1, M):
    while accA[right] - accA[left] >= K:
        left += 1

    for i in range(right, M):
        if (accA[right] - accA[left]) + A[i] >= K:
            isNess[i] = True
            for j in range(left, right):
                isNess[j] = True

ans += sum(isNess)
print(N - ans)
### BUGGY CODE ###

n=int(input())
A=[int(input()) for i in range(n)]
L = [1]
crt=1
for i in range(n):
  crt = A[crt-1]
  if crt in L:
    print(-1)
    break
  if crt == 2:
    print(len(L))
    break
  L.append(crt)

### FIXED CODE ###

def main():
  n=int(input())
  A=[int(input()) for i in range(n)]
  crt=1
  cnt=0
  for i in range(n):
    cnt += 1
    crt = A[crt-1]
    if crt == 2:
      print(cnt)
      break
  else:
    print(-1)
main()
### BUGGY CODE ###

N = int(input())
A = input().split(" ")
B = input().split(" ")
C = input().split(" ")
m = 0

for n in range(N):
    A[n] = int(A[n])
    B[n] = int(B[n])
    C[n] = int(C[n])

for i in range(N):
    for j in range(N):
        for k in range(N):
            if A[i] < B[j] and B[j] < C[k]:
                m =  m + 1

print(m)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
A.sort()
B.sort()
C.sort()
C.reverse()
 
ans = 0
ai = 0
ci = N-1
for b in B:
    while ai < N and A[ai] < b:
        ai += 1
    while ci >= 0 and C[ci] <= b:
        ci -= 1
    ans += ai * (ci+1)
 
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            key = [i,j,k]
            search = 0
            for n in range(N):
                if int(S[n]) == key[search]:
                    search += 1
                    if search == 3:
                        ans += 1
                        break

print(ans)

### FIXED CODE ###

import bisect

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

X = []
for i in range(10):
    X.append([])
for i in range(N):
    X[int(S[i])].append(i)

ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            if len(X[i]) > 0:
                ind = bisect.bisect_left(X[j],X[i][0] + 1)
                if ind < len(X[j]):
                    ind = X[j][ind] + 1
                    ind = bisect.bisect_left(X[k],ind)
                    if ind < len(X[k]):
                        ans += 1
print(ans)
### BUGGY CODE ###

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

bb=[a[0]]

for k in range(1,len(a)):
    if k%2==0:
        bb.insert(0,a[k])
    else:
        bb.append(a[k])

if len(bb)%2==0:
    b=list(reversed(bb))
else:
    b=bb


print(" ".join([str(x) for x in b]))


### FIXED CODE ###

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

a.insert(0,-1)

m=len(a)-1
res=""

k=m
for i in range(int(m/2)+1):
    res+=str(a[k])+" "
    k-=2
    if k<=0:
        break

if m%2==0:
    s=1
else:
    s=2

if m>1:
    k=s
    for i in range(int(m/2)+1):
        res+=str(a[k])+" "
        k+=2
        if k>=m:
            break

print(res)
### BUGGY CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm,a)


ans = 0
for a in A:
    ans += lcm // a
    ans %= MOD
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

lcm = 1
for a in A:
    lcm = lcm // gcd(lcm,a) * a

ans = 0
for a in A:
    ans += lcm // a
ans %= MOD
print(ans)
### BUGGY CODE ###

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

Ls = sorted(Ls)
cnt = 0
for i in range(N):
    l1 = Ls[i]
    for j in range(i+1, N):
        l2 = Ls[j]
        cnt += len([l for l in Ls[j+1:] if l <(l1+l2)])
print(cnt)

### FIXED CODE ###

import bisect
N = int(input())
Ls = list(map(int, input().split()))
 
Ls = sorted(Ls)
cnt = 0
for i in range(N):
    l1 = Ls[i]
    for j in range(i+1, N):
        l2 = Ls[j]
        ind = bisect.bisect_left(Ls, l1 + l2)
        cnt += ind - j - 1
print(cnt)
### BUGGY CODE ###

s = input()
N = int(input())
len_s = len(s)

sub_set = set()

for frm in range(len_s):
    for to in range(frm+1, len_s+1):
        sub_set.add(s[frm:to])
        

sub_list = list(sub_set)
sub_list.sort()

print(sub_list[N-1])

### FIXED CODE ###

def main():
    #0.input
    s = input()
    K = int(input())
    
    #1. make subset
    subset = set()
    for k in range(1, min(len(s)+1, K+1)):
        start = 0
        while start <= len(s)-k:
            subset.add(s[start:start+k])
            start += 1
    
    subset_list = sorted(list(subset))
    print(subset_list[K-1])

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

from collections import Counter
n=map(int, input().split())
*a,=map(int, input().split())
sa=Counter(a)

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ad=True

    for i in range(1,min(int(ai**(1/2)+7),ai)):
        if ai%i==0:
            if i in sa and i!=ai:
                ad=False
                break
            if i>1 and ai//i in sa:
                ad=False
                break
    if ad:
        ans+=1
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
*a,=map(int, input().split())
sa=Counter(a)

if 1 in sa:
    if sa[1]>1:
        print(0)
    else:
        print(1)
    exit()

# def fct(x):
#     f1=[1]
#     f2=[]
#     for i in range(2,min(int(x**(1/2)+7),x)):
#         if x%i==0:
#             f1.append(i)
#             f2.append(x//i)
#     return (set(f1+f2))
ans=0
for ai in sa:
    if sa[ai]>1:
        continue
    
    ans+=1
    if ai%2==0:
        for i in range(2,min(int(ai**(1/2)+7),ai)):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
    else:
        for i in range(3,min(int(ai**(1/2)+7),ai),2):
            if ai%i==0:
                if i in sa or ai//i in sa:
                    ans-=1
                    break
print(ans)
### BUGGY CODE ###

# encoding: utf-8
N, K = map(int, input().split())

ans = 0
pqr = 3
while pqr * K <= 6 * N:
    for r in filter(lambda x: pqr - x > x, range(1, pqr)):
        pq = pqr - r
        if r * K > 2 * N: break
        for p in range(pq - r, (pq // 2) + 1):
            q = pq - p
            if p > q: break
            elif q * K > 2 * N: continue
            elif p * K > 2 * N: break
            elif (q + r - p) * K > 2 * N: continue
            elif (r + p - q) * K > 2 * N: continue
            elif (q + r - p) * K % 2: continue
            elif (r + p - q) * K % 2: continue
            # print(p, q, r)
            if p == q == r: ans += 1
            elif p < q < r: ans += 6
            else: ans += 3
    pqr += 1
    
print(ans)

### FIXED CODE ###

# encoding: utf-8
N, K = map(int, input().split())

ans = 0
for a in range(1, N + 1):
    # find a (a, b, c)
    # maybe TLE
    # for b in range(1, N + 1):
    #     if (a + b) % K == 0: break
    # for c in range(1, K + 1):
    #     # c and c + K returns same result
    #     if (b + c) % K == 0 and (a + c) % K == 0: break
    #     else: continue
    # else:
    #     continue # next a
    if (K - 2 * a) % K: continue
    b = K - (a % K)
    c = K - b            
    # b_min, c_min
    b_min = K - (K - b) % K
    c_min = K - (K - c) % K
    # b_max, c_max
    b_max = N - (N - b_min) % K
    c_max = N - (N - c_min) % K
    # add
    # print(a, b, c, (b_min, b_max), (c_min, c_max))
    ans += ((b_max - b_min) // K + 1) * ((c_max - c_min) // K + 1)

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

#べき乗関数powを使った逆元の計算
def modinv2(a,m):
    return pow(a,m-2,m)

X,Y = map(int,input().split())

X,Y = min(X,Y),max(X,Y)

if (X+Y)%3 != 0 or X*2-Y < 0:
    ans = 0
else:
    a = (2*X-Y)//3
    b = (2*Y-X)//3
    m = 10**9+7
    ans = 1
    for i in range(1,a+b+1):
        ans = ans*i%m
    for i in range(1,a+1):
        ans = ans*modinv2(i,m)%m
    for i in range(1,b+1):
        ans = ans*modinv2(i,m)%m
print(ans)


### FIXED CODE ###

X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(A):
        ans = ans*(A+B-i)%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)
for i in range(m):
	a[0] = a[0]//2
	a.sort(reverse=True)
print(sum(a))

### FIXED CODE ###

import bisect
n,m = map(int,input().split())
a = list(map(int,input().split()))
while m != 0:
    a.sort()
    where = bisect.bisect_left(a,a[-1]//2)
    where = abs(where-(n+1))
    for i in range(1,min(where,m+1)):
        a[-i] = a[-i]//2
        m = m-1
print(sum(a))
### BUGGY CODE ###

n=int(input())
s=str(input())
r=[]
g=[]
b=[]
for i in range(n):
  if s[i]=='R':
    r.append(i)
  elif s[i]=='G':
    g.append(i)
  else:
    b.append(i)
ans=0
for l in r:
  for m in g:
    for k in b:
      if l!=m and m!=k and k!=m and abs(m-l)!=abs(k-m) and abs(k-l)!=abs(k-m) and abs(k-l)!=abs(l-m):
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=str(input())
if n<=2:
    print(0)
    exit()
r=s.count('R')
g=s.count('G')
b=s.count('B')
ans=r*g*b
for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i>n-1:
            break
        if s[i]!=s[j] and s[j]!=s[2*j-i] and s[i]!=s[2*j-i]:
            ans-=1
print(ans)
### BUGGY CODE ###

k = int(input())
n = len(input())
p = 10**9 + 7
fct, inv = [1], [1]
a, b = 1, 1
for i in range(1, n + k + 1):
    a = (a * i) % p
    b = (b * pow(i, p - 2, p)) % p
    fct.append(a)
    inv.append(b)
ans = 0
for i in range(k + 1):
    c = fct[i + n - 1] * inv[i] * inv[n - 1]
    ans += pow(25, i, p) * pow(26, k - i, p) * c
    ans %= p
print(ans)


### FIXED CODE ###

k = int(input())
n = len(input())
p = 10**9 + 7
a = 1
fct = [a]
for i in range(1, n + k + 1):
    a = (a * i) % p
    fct.append(a)
b = pow(fct[-1], p - 2, p)
inv = [b]
for i in range(1, n + k + 1)[::-1]:
    b = (b * i) % p
    inv.append(b)
inv.reverse()
ans = 0
pow25, pow26 = [1], [1]
for i in range(1, k + 1):
    pow25.append((pow25[-1] * 25) % p)
    pow26.append((pow26[-1] * 26) % p)
for i in range(k + 1):
    c = fct[i + n - 1] * inv[i] * inv[n - 1]
    ans += pow25[i] * pow26[k - i] * c
    ans %= p
print(ans)
### BUGGY CODE ###

from collections import deque

def bfs(H,W,S):
    qu = deque([(0,0,1)])
    while(len(qu) != 0):
        p,q,r = qu.popleft()
        S[p][q] = '#'
        for d in [(-1,0), (0,-1), (1,0), (0,1)]:
            s = p+d[0]
            t = q+d[1]
            if (s < 0 or t < 0 or s >= H or t >= W):
                continue
            if (s == (H-1) and t == (W-1)):
                return r+1
            if S[s][t] == '.':
                qu.append((s,t,r+1))
    return -1

H, W = list(map(int, input().split()))
S = []

cnt = 0
for i in range(H):
    a = input()
    tmp = []
    for i in a:
        if (i == '.'):
            cnt += 1
        tmp.append(i)
    S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
    print(cnt - step)
else:
    print(step)

### FIXED CODE ###

from collections import deque

def bfs(H,W,S):
	V = [[False for i in range(W)] for j in range(H)]
	qu = deque([(0,0,1)])
	V[0][0] = True
	while(qu):
		p,q,r = qu.popleft()
		S[p][q] = '#'
		for d in [(-1,0), (0,-1), (1,0), (0,1)]:
			s = p+d[0]
			t = q+d[1]
			if s < 0 or t < 0 or s >= H or t >= W:
				continue
			if s == (H-1) and t == (W-1) and S[s][t] == '.':
				return r+1
			if S[s][t] == '.' and V[s][t] == False:
				V[s][t] = True
				qu.append((s,t,r+1))
	return -1

H, W = list(map(int, input().split()))
S = []
cnt = 0
for i in range(H):
	a = str(input())
	tmp = []
	for i in a:
		if (i == '.'):
			cnt += 1
		tmp.append(i)
	S.append(tmp)

step = bfs(H, W, S)

if (step != -1):
	print(cnt - step)
else:
	print(step)
### BUGGY CODE ###

n=input()
a=list(map(int,input().split()))
ans=1
for i in a:
  ans*=i
if ans>10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import sys

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


def multiple(l):
    ans = 1
    if 0 in l:
        return 0
    for i in l:
        if ans * i > 10 ** 18:
            return -1
        else:
            ans *= i
    return ans


print(multiple(a))
### BUGGY CODE ###

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

#for i in a:
#i=0
b=[0]*n
r=0
#while i<=n:
for i in range(n):
    r=a[i]
    A=a.count(a[i]+1)
    M=a.count(a[i])
    C=a.count(a[i]-1)

    b[i]=A+M+C

print(max(b))

### FIXED CODE ###

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

#for i in a:
#i=0
b=[0]*(10**5+10)
r=0
#while i<=n:
for i in a:
    b[i]+=1
    b[i+1]+=1
    b[i+2]+=1

print(max(b))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
mod = 998244353

def solve():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    DP = [[0 for _ in range(S + 1)] for i in range(N)]
    DP[0][0] = 2
    if A[0] <= S: DP[0][A[0]] = 1
    ans = 0
    for i, a in enumerate(A[1:]):
        for s in range(S + 1):
            if DP[i][s] > 0:
                DP[i+1][s] += (DP[i][s] * 2) % mod
                DP[i+1][s] %= mod
                if s + a <= S:
                    DP[i+1][s+a] += DP[i][s]
                    DP[i+1][s+a] %= mod         
    print(DP[N-1][S])
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
mod = 998244353

def solve():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    DP = [[0 for _ in range(S + 1)] for i in range(N)]
    DP[0][0] = 2
    if A[0] <= S: DP[0][A[0]] = 1
    ans = 0
    for i, a in enumerate(A[1:]):
        for s in range(S + 1):
            if DP[i][s] > 0:
                DP[i+1][s] += (DP[i][s] * 2) % mod
                DP[i+1][s] %= mod
                if s + a <= S:
                    DP[i+1][s+a] += DP[i][s]
                    DP[i+1][s+a] %= mod         
    print(DP[N-1][S])
    #print(DP)

    return 0

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

S=[]
n = int(input())
for i in range(n):
    s=sorted(input())
    S.append(s)
cnt=0
for j in range (len(S)):
    for p in range(j+1,len(S)):
        if S[j]==S[p]:
            if j!=p:
                cnt+=1
print(cnt)
        

### FIXED CODE ###

S=[]
n = int(input())
for i in range(n):
    s=''.join(sorted(input()))
    S.append(s)
import collections
from scipy.special import comb
a=0
Sd=list(set(S))
c = collections.Counter(S)
for p in  range(len(Sd)):
    if c[Sd[p]] >=2:
        a  += comb(c[Sd[p]], 2, exact=True)
print(a)
### BUGGY CODE ###

from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

while b != 0:
    a, b = b, a % b

c = 1
lim = a // 2
n = 0
i = 2
while a > 1 and i <= lim:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        c += 1
    i += 1
if a > 1:
    c += 1

print(c)


### FIXED CODE ###

from sys import stdin

a, b = [int(x) for x in stdin.readline().split()]

while b != 0:
    a, b = b, a % b

c = 1
lim = a ** 0.5 + 10
n = 0
i = 2
while a > 1 and i <= lim:
    n = 0
    while a % i == 0:
        a //= i
        n += 1
    if n > 0:
        c += 1
    i += 1
if a > 1:
    c += 1

print(c)
### BUGGY CODE ###

import collections

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

q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    tmp = 0
    if visited[i] == 0:
        visited[i] = 1
        tmp += 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    visited[k] = 1
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(max(ans,1))

### FIXED CODE ###

import collections

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

q = collections.deque()
visited = [0 for i in range(n)]

ans = 0
for i in range(n):
    tmp = 0
    if visited[i] == 0:
        visited[i] = 1
        tmp += 1
        for j in friend[i]:
            if visited[j] == 0:
                visited[j] = 1
                tmp += 1
                q.append(j)
        while q:
            s = q.pop()
            for k in friend[s]:
                if visited[k] == 0:
                    visited[k] = 1
                    tmp += 1
                    q.append(k)
    ans = max(ans,tmp)

print(max(ans,1))