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

S = input()
N = len(S)
INF = N+1
nex = [[INF]*26 for _ in range(N+1)]
for i,c in enumerate(S[::-1]):
    ic = ord(c) - ord('a')
    for j in range(26):
        nex[N-i-1][j] = N-i-1 if j==ic else nex[N-i][j]

dp = [N] * (N+3)
dp[INF] = dp[INF+1] = 0
for i in range(N,-1,-1):
    tmp = INF
    for j in range(26):
        tmp = min(tmp, dp[nex[i][j]+1]+1)
        if tmp == 1: break
    dp[i] = tmp

ans = []
i = 0
for v in range(dp[0]-1,-1,-1):
    for j in range(26):
        if dp[nex[i][j]+1] != v: continue
        ans.append(chr(j + ord('a')))
        i = nex[i][j]+1
        break

print(''.join(ans))

### FIXED CODE ###

S = input()
N = len(S)
INF = N+1
nex = [[INF]*26 for _ in range(N+1)]
for i,c in enumerate(S[::-1]):
    ic = ord(c) - ord('a')
    for j in range(26):
        nex[N-i-1][j] = N-i-1 if j==ic else nex[N-i][j]

dp = [N] * (N+3)
dp[INF] = dp[INF+1] = 0
for i in range(N,-1,-1):
    tmp = INF
    for j in range(26):
        tmp = min(tmp, dp[nex[i][j]+1]+1)
        if tmp == 1: break
    dp[i] = tmp

ans = []
i = 0
for v in range(dp[0]-1,-1,-1):
    for j in range(26):
        if dp[nex[i][j]+1] != v: continue
        ans.append(chr(j + ord('a')))
        i = nex[i][j]+1
        break

print(''.join(ans))
### BUGGY CODE ###

N = int(input())
a = []
a = list(map(int,input().split()))
index = 0
count = 0
searchNum = 1
for j in range(N+1):
    if searchNum ==1:
        if not searchNum in a:
            searchNum = N +1
            break
    if not searchNum in a[index:]:
        searchNum -= 1
        break
    else:
        index = a[index:].index(searchNum)
        searchNum += 1
        continue

print(int(N -searchNum))


### FIXED CODE ###

N = int(input())
a = []
a = list(map(int,input().split()))
index = 0
count = 0
searchNum = 1
if not 1 in a:
    count = -1
else:
    for j in range(N):

        if a[j] ==searchNum:
            searchNum += 1
            continue
        else:
            count +=1
print(count)
### BUGGY CODE ###

S=input()
nagasa=len(S)
R_flag=0
L_flag=0
j=0
n=0
ans=[0 for i in range(nagasa)]
 
for i in range(nagasa):
  now=S[i]
  if now=="R":
    R_flag=1
    j=i
    n=0
    while(R_flag==1):

      if S[j+n]=="L" or nagasa-1==j+n:
        R_flag=0
        break
      
      else:
        n+=1
 
    if n%2==0:
      ans[j+n]+=1
    
    elif n%2==1 and S[j+n]=="R" and nagasa-1==j+n:
      ans[j+n]+=1
    elif n%2==1:
      ans[j+n-1]+=1

 
  else:
    L_flag=1
    j=i
    n=0
    while(L_flag==1):

      if S[j-n]=="R" or j-n==0:
        L_flag=0
        break

      else:
        n+=1
 
    if n%2==1 and S[j-n]=="L" and j-n==0: 
      ans[j-n]+=1
 
    elif n%2==1:
      ans[j-n+1]+=1
 
    elif n%2==0:
      ans[j-n]+=1

 
print(*ans)

### FIXED CODE ###

s=input()
n=len(s)
ans=[0 for i in range(n)]
r=0
l=0

for i in range(n):
  if s[i]=="R":
    r+=1
  else:
    plus=r//2
    ans[i]+=plus
    ans[i-1]+=(r-plus)
    r=0

for i in range(n-1,-1,-1):
  if s[i]=="L":
    l+=1
  else:
    plus=l//2
    ans[i]+=plus
    ans[i+1]+=l-plus
    l=0
print(*ans)
### BUGGY CODE ###

n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    a = l[i]
    for j in range(i+1, n-1):
        b = l[j]
        p = a + b
        if p > l[-1]:
            ans += sum([m for m in range(1, n - j)])
            break
        for k in range(j+1, n):
            if p > l[k]: ans += 1
            else: break
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = [int(i) for i in input().split()]
l.sort()
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = tuple(map(int, input().split()))
CA = []
cumsum = 0
for a in A:
    cumsum += a
    CA.append(cumsum)

mindiff = CA[-1]
for c in range(1,N-2):
    # left side
    p = 0
    q = CA[-1]
    for i in range(0, c):
        pi = CA[i]
        qi = CA[c] - CA[i]
        if abs(pi- qi) <= abs(p - q):
            p = pi; q = qi
        else:
            break

    # right side
    r = 0
    s = CA[-1]
    for i in range(c+1, N):
        ri = CA[i] - CA[c]
        si = CA[-1] - CA[i]
        if abs(ri- si) <= abs(r - s):
            r = ri; s = si
        else:
            break
    
    mindiff = min(mindiff, max([p, q, r, s]) - min([p, q, r, s]))
print(mindiff)

### FIXED CODE ###

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

from itertools import accumulate
CA = list(accumulate(A))

mindiff = CA[-1]
left = 0
right = 2
for c in range(1,N-1):
    # left side
    p = CA[left]
    q = CA[c] - CA[left]
    while True:
        pi = CA[left+1]
        qi = CA[c] - CA[left+1]
        if abs(pi- qi) >= abs(p - q):
            break
        p = pi; q = qi
        left += 1

    # right side
    r = CA[right] - CA[c]
    s = CA[-1] - CA[right]
    while True:
        ri = CA[right+1] - CA[c]
        si = CA[-1] - CA[right+1]
        if abs(ri- si) >= abs(r - s):
            break
        r = ri; s = si
        right += 1

    mindiff = min(mindiff, max(p, q, r, s) - min(p, q, r, s))
print(mindiff)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0

s_x = sl[::2]
s_y = sl[1::2]

answersx={}
answersy={}
def search(pos, kk,tgt, sl, answers):
    if kk== len(sl):
        ans=pos == tgt
        answers[pos,kk] = ans
    else:
        lng=sl[kk]
        minus=search(pos-lng,kk+1,tgt,sl,answers)
        plus=search(pos+lng,kk+1,tgt,sl,answers)
        ans = minus or plus
    answers[pos,kk] = ans
    return ans


print('Yes' if search(x0,1,x,s_x,answersx) and search(y0,0,y,s_y,answersy) else 'No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
s_x = sl[::2]
s_y = sl[1::2]
s_y=[0]+s_y
dpx=[set() for i in s_x]
dpy=[set() for i in s_y]
dpx[0].add(s_x[0])
dpy[0].add(0)
for i,l in enumerate(s_x):
    if i==0:continue
    ll=dpx[i]
    for xx in dpx[i-1]:
        ll.add(xx-l)
        ll.add(xx+l)
for i,l in enumerate(s_y):
    if i==0:continue
    ll=dpy[i]
    for yy in dpy[i-1]:
        ll.add(yy-l)
        ll.add(yy+l)
print('Yes' if x in dpx[-1] and y in dpy[-1] else 'No')
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    a,b,c=map(int, input().split())
    cnt=0
    if a+b>=c-1:
        print(b+c)
    else:
        while c>=1:
            c-=1
            if b>0:
                b-=1
                cnt+=2
            elif b==0 and a>0:
                a-=1
                cnt+=1
            elif b==0 and a==0:
                cnt+=1
                break
        if b>0:
            cnt+=b
        print(cnt)
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    a,b,c=map(int, input().split())
    cnt=0
    if a+b>=c-1:
        print(b+c)
    else:
        print(a+b+1+b)
resolve()
### BUGGY CODE ###

import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
S = 0
MOD = 1000000007

def xor(n):
    return n[0] ^ n[1]

import itertools
L = list(itertools.combinations(A, 2))
for i in L:
    S += xor(i)
      
print(S % MOD)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
MOD = 10 ** 9 + 7
ans = 0

for i in range(61):
    cnt = np.count_nonzero(A & 1)
    ans += (2 ** i) * cnt * (N - cnt)
    A >>= 1

print(ans % MOD)
### BUGGY CODE ###

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

for i in range(m):
    x, y = map(int, input().split())
    for j in range(x):
        a.append(y)

a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

n, m = map(int, input().split())
a = [(1, int(x)) for x in input().split()]

for i in range(m):
    x, y = map(int, input().split())
    a.append((x, y))

a.sort(key=lambda x:x[1], reverse=True)
res = 0

for j, k in a:
    while j > 0 and n > 0:
        res += k
        j -= 1
        n -= 1
print(res)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[32]:


N,Q=map(int,input().split())
S=input()

lr=[list(map(int,input().split())) for l in range(Q)]

for i in range(Q):
    t=S[lr[i][0]-1:lr[i][1]]
   # t=[S for j in range(lr[i][0],lr[i][1])]
   # print(t)
    print(t.count('AC'))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[4]:


N,Q=map(int,input().split())
S=input()
lr=[list(map(int,input().split())) for l in range(Q)]
ct=0
l=[0]*(N+1)
for i in range(0,len(S)-1):
    if S[i]=='A' and S[i+1]=='C':
        l[i+1]=1+l[i]
    else:
        l[i+1]=l[i]
for i in range(Q):
    print(l[lr[i][1]-1]-l[lr[i][0]-1])


# In[ ]:
### BUGGY CODE ###

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from math import comb
# def comb(n,r):
#     if r==2:
#         return n*(n-1)//2
#     else:
#         return n*(n-1)*(n-2)//6
n=n0()
s=s0()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=0
for i in range(1,(n-1)//2+1):
    for j in range(0,n-2*i):
        ans+=1
#         print(j,j+1,j+i*2)
        if s[j]==s[j+i]==s[j+2*i]:
            ans-=1
        elif s[j]==s[j+i] or s[j]==s[j+2*i] or s[j+i]==s[j+2*i]:
            ans-=1
            
ans+=comb(r,3)+comb(g,3)+comb(b,3)+comb(r,2)*(g+b)+comb(g,2)*(r+b)+comb(b,2)*(r+g)
print(comb(n,3)-ans)

### FIXED CODE ###

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

# from math import comb
def comb(n,r):
    if r==2:
        return n*(n-1)//2
    else:
        return n*(n-1)*(n-2)//6
n=n0()
s=s0()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=0
for i in range(1,(n-1)//2+1):
    for j in range(0,n-2*i):
        ans+=1
        if s[j]==s[j+i]==s[j+2*i]:
            ans-=1
        elif s[j]==s[j+i] or s[j]==s[j+2*i] or s[j+i]==s[j+2*i]:
            ans-=1
            
ans+=comb(r,3)+comb(g,3)+comb(b,3)+comb(r,2)*(g+b)+comb(g,2)*(r+b)+comb(b,2)*(r+g)
print(comb(n,3)-ans)
### BUGGY CODE ###

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

dp = [[0]*N for i in range(N)]

for i,a in enumerate(A) :
    dp[i][i] = a

for i in range(N-2, -1, -1) :
    for j in range(i+1, N) :
        left = A[i] - dp[i+1][j]
        right = A[j] - dp[i][j-1]
        dp[i][j] = max(left, right)

ans = dp[0][N-1]

print(ans)


### FIXED CODE ###

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

dp = [[0]*N for i in range(N)]

for i,a in enumerate(A) :
    dp[i][i] = a

for i in range(N-2, -1, -1) :
    for j in range(i+1, N) :
        left = A[i] - dp[i+1][j]
        right = A[j] - dp[i][j-1]
        dp[i][j] = max(left, right)

ans = dp[0][N-1]

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

n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
R = A.copy()
for i in range(m):
	b,c = map(int,input().split())
	cou = 0
	for i,_ in enumerate(R):
		if A[i] < c :
			A[i] = c
			cou += 1
		if cou == b:
			break
	A.sort()
print(sum(A))

### FIXED CODE ###


def test_function() :
	print(__name__) # __main__

#print("called :",test_function.__name__)
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
C=[]
for i in range(m):
	b,c = map(int,input().split())
	C.append((b,c))
C = sorted(C,key = lambda x:x[1])
before = 0

for b,c in C[::-1]:
	cou = 0  
	#print("[before]=",before)
	for i in range(len(A)-before):
		if A[before+i] < c :
			A[before+i] = c
			cou += 1
			#print("A=",A)
		else :
			before += i+1
			break
		if cou == b:
			before += i+1
			break
print(sum(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1

def dfs_aoki(cur: int, past: int, G, d: int):

    if elens[cur] == 1 and G[cur][0] == past:
        return d - 1, 0 if cur == u else -1

    ret = 0
    takahashi_d = -1

    for nx in G[cur]:
        if nx == past:
            continue

        depth, td = dfs_aoki(nx, cur, G, d + 1)
        if td >= 0:
            if td >= 0 and d <= td + 1:
                return depth, td
            takahashi_d = td + 1

        ret = max(ret, depth)

    return ret, takahashi_d

d, _ = dfs_aoki(v, -1, G, 0)
print(d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1
depths = [0] * N
dists = [0] * N


TAKAHASHI = [0] * N
AOKI = [0] * N

def dfs_aoki(cur: int, past: int, d: int):
    AOKI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_aoki(nx, cur, d + 1)

def dfs_takahashi(cur: int, past: int, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_takahashi(nx, cur, d + 1)

dfs_takahashi(u, -1, 0)
dfs_aoki(v, -1, 0)

ans = 0

for i in range(N):
    if TAKAHASHI[i] < AOKI[i]:
        ans = max(ans, AOKI[i] - 1)

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

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

mod = 10**9+7

ans = 0
for i in range(0,n-1):
    for j in range(i,n):
        ans += ( a[i] ^ a[j] ) % mod

print(ans% mod)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
c=0
for i in range(61):
  i=2**i
  t=sum(i&b and 1 for b in a)
  c=(c+t*(n-t)*i)%(10**9+7)
print(c)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = []
for _ in range(Q):
    A.append(int(input()))


if K > Q:
    for i in range(N):
        print('Yes')
else:
    for n in range(N):
        freq = A.count(n + 1)
        if K - Q + freq <= 0:
            print('No')
        else:
            print('Yes')





### FIXED CODE ###

N, K, Q = map(int, input().split())
index_list = [int(input()) - 1 for i in range(Q)]

zero_list = [0 for n in range(N)]

ori = K - Q
for i in range(Q):
    zero_list[index_list[i]] += 1
for i in range(N):
    zero_list[i] += ori
for i in range(N):
    if zero_list[i] > 0:
        print('Yes')
    else:
        print('No')

# shakayamiさんのコードを参考にしました
# for文が入れ子になると遅くなるから，出来るだけそうしない
### BUGGY CODE ###

from itertools import accumulate
import numpy as np
MOD = 10 ** 9 + 7


def cumprod(A, mod=MOD):
    L = len(A)
    Lsq = int(L ** 0.5 + 1)
    A = np.resize(A, Lsq ** 2).reshape((Lsq, Lsq))
    for i in range(1, Lsq):
        A[:, i] *= A[:, i - 1]
        A[:, i] %= mod
    for i in range(1, Lsq):
        A[i] *= A[i - 1][-1]
        A[i] %= mod
    return A.ravel()[:L]


def make_fact_and_inv(U, mod=MOD):
    """
    0~Nまでのサイズ(N+1)の階乗およびその逆元の配列を返す
    """
    tmp = np.arange(U, dtype=np.int64)
    tmp[0] = 1
    fact = cumprod(tmp, mod)
    tmp = np.arange(U, 0, -1, dtype=np.int64)
    tmp[0] = pow(int(fact[-1]), mod - 2, mod)
    inv = cumprod(tmp, mod)[::-1]
    return fact, inv


fact, inv = make_fact_and_inv(2 * 10 ** 6)


def nCr(n, r, mod=MOD):
    if r < 0 or r > n or n < 0:
        return 0
    return fact[n] * inv[r] % mod * inv[n - r] % mod


if __name__ == "__main__":
    N, K = map(int, input().split())

    ans = []
    for i in range(min(N - 1, K) + 1):
        val = nCr(N, i) * nCr(N - 1, i) % MOD
        ans.append(val)

    answer = 0
    while ans:
        answer = (answer + ans.pop()) % MOD
    print(answer)


### FIXED CODE ###

N, K = map(int, input().split())
mod = 10 ** 9 + 7

K = min(K, N - 1)

fact = [1]
facinv = [1]
for i in range(1, N + 1):
    fact.append(fact[-1]*i % mod)


def nCr(n, r):
    num = fact[n]
    div = fact[r] * fact[n - r] % mod
    return num * pow(div, mod - 2, mod) % mod


move = [0] * (N + 1)
move[0] = 1
for i in range(1, N + 1):
    x = nCr(N, i) * nCr(N - 1, N - i - 1) % mod
    move[i] = x

for i in range(1, N):
    move[i] = (move[i - 1] + move[i]) % mod

ans = move[K]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
m = 1
c = 0
for i in range(1, int(min(A))+1):
    c = 1
    for j in range(N):
        if A[j] % i != 0:
            c = 0
            break
    if c == 1:
        m = max(i, m)
print(m)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
N = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)
a = A[0]
for i in range(1,N):
    a = gcd(a,A[i])
print(a)
### BUGGY CODE ###

# C
import functools
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)

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

for i in range(n):
    values = a[:i] + a[i+1:]
    res = functools.reduce(gcd, values)
    ans = max(ans, res)
print(ans)

### FIXED CODE ###

# C
import functools
# 3.4以前は math の gcd が対応していないので fractions のものを使う
# from fractions import gcd
def gcd(a,b):
    if a<b:a,b=b,a
    if a%b==0:return b
    return gcd(b,a%b)


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

gcd_left = [a[0]]
gcd_right = [a[-1]]
for i in range(1,n):
    if gcd_left[i-1] != 1:
        res = gcd(gcd_left[i-1], a[i])
    else:
        res = 1
    gcd_left.append(res)

for i in range(1,n):
    if gcd_right[i-1] != 1:
        res = gcd(gcd_right[i-1], a[-(i+1)])
    else:
        res = 1
    gcd_right.append(res)
gcd_right = gcd_right[::-1]


ans = 0
for i in range(n):
    if i == 0:
        res = gcd_right[1]
    elif i == n-1:
        res = gcd_left[-2]
    else:
        res = gcd(gcd_right[i+1], gcd_left[i-1])
    ans = max(res, ans)
print(ans)
### BUGGY CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()], reverse=True)
B = sorted([int(b) for b in input().split()], reverse=True)
C = sorted([int(c) for c in input().split()], reverse=True)
ans = 0

for i in range(N):
  for j in range(N):
    if A[i] >= B[j]:
      break
    for k in range(N):
      if B[j] >= C[k]:
        break
      else:
        ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
A = sorted([int(a) for a in input().split()])
B = [int(b) for b in input().split()]
C = sorted([int(c) for c in input().split()])
ans = 0

import bisect
for i in range(N):
  b = B[i]
  end_A = bisect.bisect_left(A, b)
  start_C = bisect.bisect_right(C, b)
  ans += end_A * (N - start_C)

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

N = int(input())
s = [str(input()) for i in range(N)]
#print(s)

for i in range(N):
  s[i] = sorted(s[i])

e = []
f = [0] * N
j = 0
ans = 0
for i in range(N):
  if s[i] not in e:
    e.append(s[i])
    f[j] = 1
    j += 1
  else:
    a = e.index(s[i])
    ans += f[a]
    f[a] += 1

print(ans)

### FIXED CODE ###

import time
N = int(input())
s = [str(input()) for i in range(N)]

j = 0
ans = 0
for i in range(N):
  s[i] = "".join(sorted(s[i]))
#print(s)

s = sorted(s)
tango = "yeeeh"
x = 0
#print(s)
for i in range(N):
  if s[i] == tango:
    x += 1
  else:
    ans += x * (x + 1) //2
    x = 0
  tango = s[i]
ans += x * (x + 1) //2

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

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcms = [A[0]]
[lcms.append(s*lcms[-1]//gcd(lcms[-1], s)) for s in A]
lcm = lcms[-1]

ans = np.sum([lcm*pow(s, mod-2, mod) % mod for s in A]) % mod

print(int(ans))

### FIXED CODE ###

from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

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

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

ex = [0]
for x in p:
    ex.append(ex[-1] + 1/x * (sum(list(range(1, x+1)))))

ans = 0
for i in range(k, n+1):
    ans = max(ans, ex[i] - ex[i-k])

print(ans)

### FIXED CODE ###

def main():

    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    ex = [0]
    for x in p:
        ex.append(ex[-1] + (x+1)/2)

    ans = 0
    for i in range(k, n+1):
        ans = max(ans, ex[i] - ex[i-k])

    print(ans)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

score = [0]*(n+1)

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


def down_tree(index, parent=-1):
    global score
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)
    return


down_tree(1)

for i in range(1,n+1):
    print(score[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

score = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))
### BUGGY CODE ###

# coding: utf-8
# hello worldと表示する
# coding: utf-8
# hello worldと表示する
# coding: utf-8
# hello worldと表示する
"""def comb2(n,r):
    if n == 0 or r == 0: 
        return 1
    return comb2(n-1,r-1)+comb2(n-1,r)
def fact(n):
    if n==0:
        return 1
    return n*fact(n-1)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]"""
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 result
#a = cmb(n,r)
ans=0    
N=int(input())
s=list(map(int,input().split()))
t=max(s)
for i in s:
    c=ncr(t,i)
#    c=fact(t)/(fact(i)*fact(t-i))
    if ans<c and t!=i:
        ans=c
        an=i
print(str(t)+" "+str(an))        


### FIXED CODE ###

N=int(input())
s=list(map(int,input().split()))
n=max(s)
s.remove(n)
q=n
for i in s:
    t=abs(n/2-i)
    if q>=t:
        q=t
        w=str(n)+" "+str(i)
print(w)
### BUGGY CODE ###

A, B, K = map(int, input().split())

for k in range(K):
  if(A != 0):
    A-=1
  elif(B > 0):
    B-=1
  else:
    break
print(A, B)

### FIXED CODE ###

A, B, K = map(int, input().split())

if(A - K >= 0):
  A -= K
else:
  if(B+(A-K) >= 0):
    B += A - K
    A = 0
  else:
    A = 0
    B = 0
print(A, B)
### BUGGY CODE ###

N = int(input())
Candidate = []

for i in range(N):
  S = input()
  letters = list(S)
  letters.sort()
  S = "".join(letters)
  Candidate.append(S)

Answer = []
for i in range(N):
  for k in range(N-i-1):
    if Candidate[i] == Candidate[i+k+1]:
      Answer.append([i,k])
print(len(Answer))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input())
dic={}
sum=0
for i in range(N):
    s=list(input())
    s.sort()
    s = "".join(s)
    if s in dic:
        sum+=dic[s]
        dic[s]+=1
    else:
        dic[s]=1
print(sum)