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

import numpy as np

# n = int(input())

# l = np.array(list(map(int,input().split())))

n = 200
l = np.array([3 for i in range(n)])

l.sort()
# def num(first,second,third):
#     if l[first] < l[second] + l[third]:
#         dp[first] += 1
#         if third > 0:
#             num(first,second,third-1)
#         else:
#             # print(first,second,third)
#             return 
#     else:
#         # print(first,second,third)
#         return second, third





dp = np.array([0]*n)

for i in range(n-1,1,-1):
    for j in range(i-1,0,-1):
        # print(i,j)
        # num(i,j,j-1)
        for k in range(j-1,-1,-1):
            
            if l[i] < l[j] + l[k]:
                dp[i] += 1
            else:
                second = j
                third = k
                break
        else:
            second = j
            third = k
        if second == third + 1:
            break
    # print(i)
print(np.sum(dp))

### FIXED CODE ###

import numpy as np
n = int(input())

l = np.array(list(map(int,input().split())))

l.sort()
l = l[::-1]
ans = 0
for i in range(n-2):
    j = i+1
    k = n-1
    while j < k:
        if l[i] < l[j] + l[k]:
            ans += k - j
            j += 1
        else:
            k -= 1
print(ans)
### BUGGY CODE ###

import math

n = int(input())

for i in range(1, n + 1):
    cnt = 0
    t = math.floor(i - (i ** 0.5)) + 1
    for j in range(1, t):
        for k in range(1, t):
            for l in range(1, t):
                if ((j ** 2) + (k ** 2) + (l ** 2) + (j * k) + (k * l) + (l * j)) == i:
                    cnt += 1
                elif ((j ** 2) + (k ** 2) + (l ** 2) + (j * k) + (k * l) + (l * j)) > i:
                    break
                else:
                    pass
    print(cnt)

### FIXED CODE ###

n = int(input())
ans = [0] * 10000

for i in range(1, 101):
    for j in range(1, 101):
        for k in range(1, 101):
            m = ((i ** 2) + (j ** 2) + (k ** 2) + (i * j) + (j * k) + (k * i))
            if m < 10001:
                ans[m-1] += 1

for i in range(n):
    print(ans[i])
### BUGGY CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]
p = [0 for _ in range(n)]

if k>q:
    for i in range(1,n+1):
        print('Yes')
    exit()
else:
    for i in range(n):
        p[i]=a.count(i+1)
        if k+p[i]-q>0:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

n,k,q = map(int, input().split())
a = [int(input()) for _ in range(q)]

p = [k-q]*(n)
for i in a:
    p[i-1] +=1

for i in range(n):
    if p[i]>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
p = [int(i) for i in input().split()]
count = 0
for i in range(n):
    if p[i] <= (min(p[0:i]) if i != 0 else p[0]):
        count += 1
print(count)

### FIXED CODE ###

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

# coding: utf-8
# Your code here!

SIZE=10000; MOD=10**9+7 #ここを変更する

inv = [0]*(SIZE+1)# inv[j] = j^{-1} mod MOD
fac = [0]*(SIZE+1)# fac[j] = j! mod MOD
finv = [0]*(SIZE+1)# finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE+1):
    inv[i] = MOD -(MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0

import sys
sys.setrecursionlimit(10**7)

n=int(input())
s=input()


memo = [[0]*(i+1) for i in range(n+1)]
 
def dp(r,l):
    if r-l<=2:
        memo[r][l] = 1
        return 1
    if memo[r][l] > 0:
        return memo[r][l]
    
    res = 0
    pt = l
    now = "<"
    while pt <= r-1:
        if pt < r-1 and s[pt] == "<":
            now = "<"
        else:
            if now  == "<":
#                print(pt,r,l)
                res += dp(r,pt+1) * dp(pt,l) * choose(r-l-1, pt-l)
                res %= MOD
            now = ">"    
        pt += 1

    
    memo[r][l] = res
    return res
 
dp(n,0)
#print(memo)
print(memo[n][0])







### FIXED CODE ###

# coding: utf-8
# Your code here!
n=int(input())
s=input()
MOD = 10**9+7

dp = [1]*n

for i,c in enumerate(s):
    if c == "<":
        ssum = sum(dp[1:n-i])
        ssum %= MOD
        for j in range(n-i-1):
            dp[j] = ssum
            ssum -= dp[j+1]
            ssum %= MOD

    else:
        ssum = dp[0]
        for j in range(n-i-1):
            dp[j] = ssum
            ssum += dp[j+1]
            ssum %= MOD

#    print(dp)


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

line = input().split()
num = int(line[0]) + 1
sum = 0
for x in range(num):
    for y in range(num):
        leave = int(line[1]) -(x + y)
        if leave >= 0 and leave <= num - 1:
            sum += 1
print(sum)                

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
           for y in range(k+1):
               if -1 < s-x-y < k+1:
                   ans += 1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

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

ans = 0
while len(A) > 1:
    pow2 = 1 << (len(bin(A[-1])) - 2)
    idx = bisect_left(A, pow2 - A[-1])
    if A[idx] + A[-1] == pow2 and idx != len(A) - 1:
        A.pop(idx)
        ans += 1
    A.pop(-1)
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
from collections import deque

N = int(input())
A = list(map(int, input().split(" ")))
A.sort()
A = deque(A)
ans = 0
t_max = len(bin(A[-1])) - 2
for t in range(t_max, 0, -1):
    if len(A) < 2: break
    while len(bin(A[-1])) - 2 > t:
        A.pop()
        if len(A) < 2: break
    if len(A) < 2: break
    pow2 = 1 << t
    A_tmp = deque()
    while t == len(bin(A[-1])) - 2:
        r = A.pop()
        idx = bisect_left(A, pow2 - r)
        for _ in range(idx):
            A_tmp.appendleft(A.popleft())
        if len(A) == 0: break
        if A[0] + r == pow2:
            A.popleft()
            ans += 1
        if len(A) < 2: break
    A.extendleft(A_tmp)
                    
print(ans)
### BUGGY CODE ###

from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    counter = defaultdict(int)

    parents = deque()
    parents.append(0)
    while parents:
        parent = parents.popleft()
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        if parent in edges:
            for child in edges[parent]:
                counter[child] = counter[parent]
                # print("child")
                # print(child, counter[child])
                parents.append(child)

    print(" ".join(list(map(str, counter.values()))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(list)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        edges[a_i-1].append(b_i-1)

    p = [0] * n
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(input().split(),dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],(A > x).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  C = 2*B-np.arange(N+1)
  C -= np.min(C) - 1
  M = C.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  prev = C[0]
  for c in C[1:]:
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,c) # 右端がRとなる(L,R)対
    prev = c
  return cnt <= (total_medians-1)//2

left = 0 # 答はleftより大きいである
right = 10**9 # 答はright以下である
while right - left > 1:
  mid = (left+right)//2
  if test(mid):
    right = mid
  else:
    left = mid
    
answer = right
print(answer)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)
### BUGGY CODE ###

N = int(input())
a = range(1,N)
print(sum(a))

### FIXED CODE ###

N = int(input())
if N%2==0:
  N_=int(N/2)
  print(N_*(N-1))
else:
  N_=int((N-1)/2)
  print(N_*N)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
t = [0 for _ in range(N)]
for i in range(N-1):
  if S[i] == 'A' and S[i+1] == 'C':
    t[i] = 1
for _ in range(Q):
  r, l = map(int,input().split())
  print(sum(t[0:l-1]) - sum(t[0:r-1]))

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
index = [0] *(N+1)
for i in range(N):
  index[i+1] = index[i] + (1 if S[i:i+2] =='AC' else 0)
for _ in range(Q):
  r, l = map(int,input().split())
  print(index[l-1] - index[ r -1])
### BUGGY CODE ###

N = int(raw_input())
A = map(int, raw_input().split())
A = map(lambda x: format(x, '060b'), A)
MOD = 10**9 + 7

count = dict()
for i in range(60):
    zeros = len([a[i] for a in A if a[i] == '0'])
    ones = N - zeros
    count[i] = zeros*ones

ans = 0
for i, v in count.items():
    ans = (ans + count[i]*(1<<(59-i))) % MOD

print ans


### FIXED CODE ###

import numpy as np

N = int(raw_input())
A = np.array(map(int, raw_input().split()))
# A = map(lambda x: format(x, '060b'), A)
MOD = 10**9 + 7

count = dict()
for i in range(60):
    # zeros = len([a[i] for a in A if a[i] == '0'])
    zeros = np.count_nonzero((A>>i)&1)
    ones = N - zeros
    count[i] = zeros*ones

mod_val = dict()
curr = 1
for i in range(60):
    mod_val[i] = curr % MOD
    curr = (2*curr) % MOD

ans = 0
for i in count:
    ans = (ans + count[i]*mod_val[i]) % MOD

print ans
### BUGGY CODE ###

mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

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

searched = set()
for dup, x in enumerate(a):
    if x in searched:
        break
    else:
        searched.add(x)
first = a.index(a[dup])

for k in range(1, n+2):
    ans = comb(n+1, k)
    if k - 1 <= n - dup + first:
        ans -= comb(n - dup + first, k - 1)
    print(ans % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

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

searched = set()
for dup, x in enumerate(a):
    if x in searched:
        break
    else:
        searched.add(x)
first = a.index(a[dup])

for k in range(1, n+2):
    ans = comb(n+1, k)
    if k - 1 <= n - dup + first:
        ans -= comb(n - dup + first, k - 1)
    print(ans % mod)
### BUGGY CODE ###

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

cnt = 0

for i in range(q):
    a = input()
    if a[0] == "1":
        cnt += 1
    elif a[0] == "2":
        if (a[2] == "1" and cnt % 2 == 0) or (a[2] == "2" and cnt % 2 == 1):
            s = a[4] + s
        elif (a[2] == "2" and cnt % 2 == 0) or (a[2] == "1" and cnt % 2 == 1):
            s = s + a[4]

if cnt % 2 == 1:
    s = s[::-1]

print(s)


### FIXED CODE ###

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

x = []
y = []
cnt = 0

for i in range(q):
    a = list(input().split())
    if a[0] == "1":
        x, y = y, x
        cnt += 1
    else:
        if a[1] == "1":
            x.append(a[2])
        else:
            y.append(a[2])

if cnt % 2 == 1:
    s = s[::-1]

s = ''.join(x[::-1]) + s + ''.join(y)

print(s)
### BUGGY CODE ###

import sys
from math import factorial

def comb(n, r):
    if n - r < r:
        r = n - r
    if r < 0:
        return 0
    if r == 0:
        return 1
    if r == 1:
        return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k 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 *= int(numerator[k])

    return result


def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    for i in range(1, N+2):
        ans = comb(N+1, i)
        for j in range(i):
            m_f = first
            r_f = j

            m_b = N - second
            r_b = i - (j + 1)

            ans -= comb(m_f, r_f) * comb(m_b, r_b)

        print(int(ans) % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    used = set()
    first = 0
    second = 0
    for i in range(N+1):
        if A[i] in used:
            second = i
            first = A.index(A[i])
        else:
            used.add(A[i])

    factrial = [1] * (N+2)
    for k in range(1, N+2):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (N+2)
    fact_inv[N+1] = pow(factrial[N+1], MOD - 2, MOD)
    for k in range(N, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    def comb(n, r, MOD):
        if n < 0 or r < 0 or n < r:
            return 0
        else:
            return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD

    m = first + (N - second)
    for i in range(1, N+2):
        ans = comb(N+1, i, MOD) - comb(m, i-1, MOD)
        print(int(ans) % MOD)


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

N=int(input())
A=list(map(int,input().split()))[::-1]

def f(A):
    nodes=[]
    for i in list(range(len(A))):
        t = len(A)-i-1
        if i == 0:
            if 2**t < A[i]:
                return -1
            nodes.append(A[i])
        else:
            tmp = min(nodes[-1] + A[i],2**t)
            anchor = (tmp-A[i])*2
            if anchor < nodes[-1]:
                flag = True
                for j in range(len(nodes))[::-1]:
                    if anchor < nodes[j]:
                        nodes[j] = anchor
                        anchor = (nodes[j]-A[j])*2
                    else:
                        flag = False
                        break
                if flag : return -1        
            nodes.append(tmp)
    return sum(nodes)
  
print(f(A))

### FIXED CODE ###

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

def solve(A):
    ans = 0
    leaves = sum(A)
    prev_node_capacity = 1

    for ai in A:
        if ai > prev_node_capacity:
            return -1
        ans += min(prev_node_capacity, leaves)

        leaves -= ai
        prev_node_capacity -= ai
        prev_node_capacity *= 2

    return ans
  
print(solve(A))
### BUGGY CODE ###

import math
k = int(input())
s = 0
for p in range(1,k+1):
	for q in range(1,k+1):
			for r in range(1,k+1):
				if r == 1:
					s += 1
				else:
					s = s + math.gcd(p,math.gcd(q,r))
print(s)

### FIXED CODE ###

import math
k = int(input())
s = 0
for p in range(1,k+1):
	for q in range(1,k+1):
		temp = math.gcd(p,q)
		for r in range(1,k+1):
			if r == 1:
				s += 1
			else:
				s = s + math.gcd(temp,r)
print(s)
### BUGGY CODE ###

#!/usr/bin/env python3


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    a = input()
    Q = int(input())
    qs = [input().split() for _ in range(Q)]
    ans = a
    revcount = 0
    for q in qs:
        if len(q) == 1:
            revcount += 1
        else:
            if int(q[1]) == 1:
                if revcount % 2 == 0:
                    ans = q[2] + ans
                else:
                    ans = ans + q[2]
            else:
                if revcount % 2 == 0:
                    ans = ans + q[2]
                else:
                    ans = q[2] + ans
    if revcount % 2 == 1:
        ans = ans[::-1]
    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    a = input()
    Q = int(input())
    qs = [input().split() for _ in range(Q)]
    ans = deque(a)
    revcount = 0
    for q in qs:
        if len(q) == 1:
            revcount += 1
        else:
            if int(q[1]) == 1:
                if revcount % 2 == 0:
                    ans.appendleft(q[2])
                else:
                    ans.append(q[2])
            else:
                if revcount % 2 == 0:
                    ans.append(q[2])
                else:
                    ans.appendleft(q[2])
    if revcount % 2 == 1:
        ans.reverse()
    print(''.join(list(ans)))
    return


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

k,n=map(int,input().split())
a=list(map(int,input().split()))
for j in range(n-1):
	a.append(a[j]+k)
sum=[0]*n
for I in range(n):
	for i in range(n-1):
		sum[I]=sum[I]+a[I+i+1]-a[I+i]
print(min(sum))

### FIXED CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
a.append(a[0]+k)
dist=[0]*n
for i in range(1,len(a)):
	dist[i-1]=a[i]-a[i-1]
print(sum(dist)-max(dist))
### BUGGY CODE ###

n,m=map(int,input().split())
mod = 10 ** 9 + 7
li=[int(input()) for i in range(m)] # 壊れてる段

for i in range(n+1):
  # i-2までがa, i-1までがb
  if i == 0:
    a=1
  elif i == 1:
    if 1 in li:
      a,b=1,0
    else:
      a,b=1,1
  else:
    if i-2 in li and i-1 in li:
      print(0)
      exit()
    elif i-2 in li and i-1 not in li:
      a,b = b,b
    elif i-2 not in li and i-1 in li:
      a,b = 0,a
    else:
      a,b = b,(a+b) % mod
print(b)

### FIXED CODE ###

n,m = map(int,input().split())
broken = [int(input()) for i in range(m)]
broken.sort()
broken += [0] * (n-m)
index = 0
mod = 10**9 + 7
for i in range(1,n+1):
  if i==1:
    if i != broken[index]:
      a=1
      b=1
    else:
      a=1
      b=0
      index += 1
  else:
    if i == broken[index]:
      a,b=b,0
      index += 1
    else:
      a,b=b,(a+b)%mod
print(b)
### BUGGY CODE ###

import string

def bwords(str):
  str = list(str)
  bword = [0]*len(string.ascii_lowercase)
  for s in str:
  	bword[string.ascii_lowercase.index(s)]+=1
  return bword

def check_bword(a_word,b_word):
  for a,b in zip(a_word,b_word):
    if a != b:
      return False
  return True

N = int(input())
groups = {0: 1}
groups_bword = {0: bwords(input())}

for i in range(1,N):
  s = input()
  b_w = bwords(s)
  
  add_grouped = False
  
  for key,bword in groups_bword.items():
    if check_bword(b_w,bword):
      groups[key]+=1
      add_grouped = True
      break
      
  if not add_grouped:
    groups[len(groups.keys())] = 1
    groups_bword[len(groups_bword.keys())] = b_w

count = 0

for key,nums in groups.items():
  count+=nums*(nums-1)//2
  
print(count)

### FIXED CODE ###

import string
import collections

N = int(input())
count = 0

s = []

for i in range(0,N):
  s.append(''.join(sorted(input())))

  
c = collections.Counter(s)
go = c.most_common()

for i in range(len(go)):
  k = go[i][1]
  count+=k*(k-1)//2
  
print(count)
### BUGGY CODE ###

H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]

dp = [float("inf")] * (H+1)
dp[H] = 0

for i in range(H, 0, -1):
  for j in range(N):
    a, b = M[j]
    dp[i-a if i-a >= 0 else 0] = min(dp[i-a if i-a >= 0 else 0], dp[i] + b)
print(dp[0])

### FIXED CODE ###

H, N = map(int, input().split())
M = [tuple(map(int, input().split())) for i in range(N)]

dp = [float("inf")] * (H+1)
dp[H] = 0

for i in range(H, 0, -1):
  for j in range(N):
    a, b = M[j]
    dp[i-a if i-a >= 0 else 0] = min(dp[i-a if i-a >= 0 else 0], dp[i] + b)
print(dp[0])
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
ans = 0
pattern = 1
for i in range(1, n):
  pattern *= i
p=1
k=pattern
while p < n:
  ans += k * (x[p]-x[p-1])
  ans %= 1000000007
  p += 1
  k += pattern//(p)
print(ans)

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
ans = 0
mod = 1000000007
p = 1
for i in range(1, n):
  p *= i
  p %= mod
for i in range(n-1):
  ans += (x[n-1]-x[i])*pow(i+1, mod-2, mod)
ans *= p
ans %= 1000000007
print(ans)