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

import copy
A, B = [], []
N, M = (int(x) for x in input().split())
for i in range(N):
    a, b = (int(x) for x in input().split())
    A.append(a), B.append(b)

#sort main_list with sub_list
def merge(main_list, sub_list):
    mid = len(main_list)
    if mid > 1:
        left = merge(main_list[:(mid//2)], sub_list[:(mid//2)])
        right = merge(main_list[(mid//2):], sub_list[(mid//2):])
        main_list, sub_list = [], []
        while len(left[0]) != 0 and len(right[0]) != 0:
            if left[0][0] < right[0][0]:
                main_list.append(left[0].pop(0))
                sub_list.append(left[1].pop(0))
            else:
                main_list.append(right[0].pop(0))
                sub_list.append(right[1].pop(0))
        if len(left[0]) != 0:
            main_list.extend(left[0])
            sub_list.extend(left[1])
        elif len(right[0]) != 0:
            main_list.extend(right[0])
            sub_list.extend(right[1])
    return main_list, sub_list

num_of_drink, total_fee = 0, 0
A, B = copy.copy(merge(A, B)[0]), copy.copy(merge(A, B)[1])
for i in range(N):
    for j in range(B[i]):
        num_of_drink += 1
        total_fee += A[i]
        if num_of_drink == M:
            break
    else:
        continue
    break

print(total_fee)

### FIXED CODE ###

List = []
N, M = (int(x) for x in input().split())
for i in range(N):
    a, b = (int(x) for x in input().split())
    List.append([a, b])

num_of_drink, total_fee = 0, 0
List = sorted(List, key=lambda x:x[0])

temp_M = M
list_of_num = []
for i in range(N):
    if temp_M <= List[i][1]:
        list_of_num.append(temp_M)
        break
    else:
        list_of_num.append(List[i][1])
        temp_M += -List[i][1]
index = 0
for x in list_of_num:
    total_fee += List[index][0] * x
    index += 1
print(total_fee)
### BUGGY CODE ###

a = []
x = 1

n = int(input())
a = input().split()

for i in range(n):
    a[i-1] = int(a[i-1])
    x = x * a[i-1]
    
if x <= 10**18:
    print(x)
elif x > 10**18:
    print(-1)

### FIXED CODE ###

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

for i in range(n):
  ans = ans * a[i]
  if ans > 10**18:
    ans = -1
    break

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

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    bridges = [False]*(N-1)
    battles = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int, input().split())
        battles[b-1].append(a-1)
    for i in range(1,N):
        battle = battles[i]
        if len(battle) == 0: continue

        closest_idx = max(battle)
        for bridge_idx in range(closest_idx, i):
            if bridges[bridge_idx]: break
        else:
            bridges[i-1] = True
    print(bridges.count(True))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    battles = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int, input().split())
        battles[b-1].append(a-1)

    x = -1
    ans = 0
    for i in range(1,N):
        battle = battles[i]
        if len(battle) == 0: continue

        closest_idx = max(battle)
        if x < closest_idx:
            ans += 1
            x = i-1
    print(ans)

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

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0 for i2 in range(b+1)]
        tmp = 0
        for j in range(b):
            if e1 == seq2[j]:
                tmp = x2[j] + 1
            else:
                tmp = max(x2[j+1], tmp)
            x1[j+1] = tmp
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()

### FIXED CODE ###

import sys

def longestcommonsubsequence():
    seq1 = raw_input()
    seq2 = raw_input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = input()
for i2 in range(n):

    print longestcommonsubsequence()
### BUGGY CODE ###

n, q = [int(x) for x in input().split(' ')]
s = input()
lr = [[int(x) for x in input().split(' ')] for _ in range(q)]

indexes = []
for i in range(1, len(s)):
    if s[i-1] == 'A' and s[i] == 'C':
        indexes.append([i-1, i])

for l, r in lr:
    print(len([x for x in indexes if l-1 <= x[0] and x[1] <= r-1]))



### FIXED CODE ###

n, q = [int(x) for x in input().split(' ')]
s = input()
lr = [[int(x) for x in input().split(' ')] for _ in range(q)]


indexes = [0] * n

for i in range(1, len(s)):
    if s[i-1] == 'A' and s[i] == 'C':
        indexes[i] = indexes[i-1]+1
    else:
        indexes[i] = indexes[i-1]

for l, r in lr:
    print(indexes[r-1]-indexes[l-1])
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
q = deque(a)

count_use = 0
while count_use < m:
    max_a = a.pop()
    max_a = max_a//2
    a.append(max_a)
    a.sort()
    count_use += 1

print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

count_use = 0
while count_use < m:
    max_a = heapq.heappop(a)
    max_a = -1*((-1*max_a)//2)
    #print(max_a)
    heapq.heappush(a, max_a)
    count_use += 1

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a.sort()
if sum(a)<=k:
    print(0)
    exit()
f.sort(reverse=True)
m=0
for i in range(n):
    m=max(m,a[i]*f[i])
x=m//2
l=0
r=m
def check(x):
    p=0
    for i in range(n):
        if x//f[i]<a[i]:
            p+=a[i]-x//f[i]
            if p>k:
                return False
    if p>k:
        return False
    else:
        return True
while l<r:
    if check(x):
        r=x
        x=(r+l)//2
    else:
        l=x
        x=(r+l)//2
print(r)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)

a = []
f = []
n = 0

def rec(l, r, k):
    if l+1 < r:
        mid = (l + r) // 2
        s = 0
        for i in range(n):
            s += max(a[i] - mid // f[i], 0)
        if s <= k:
            return rec(l, mid, k)
        else:
            return rec(mid, r, k)
    else:
        return r

def main():
    global a, f, n
    n, k = map(int, input().strip().split())
    a = list(map(int, input().strip().split()))
    f = list(map(int, input().strip().split()))
    a = sorted(a)
    f = sorted(f, reverse=True)
    print(rec(-1, 10**12, k))

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

from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left


class Solution:
    def main(self):
        path = defaultdict(list)
        N, Q = map(int, input().split())
        freq = [0] * N
        for i in range(N-1):
            ai, bi = map(int, input().split())
            path[ai-1].append(bi-1)
            path[bi-1].append(ai-1)

        for i in range(Q):
            p, x = map(int, input().split())
            freq[p-1] += x

        stack = [(0, 0)]
        seen = set()
        res = [0] * N
        while stack:
            node, cum = stack.pop(0)
            seen.add(node)
            val = freq[node] + cum
            res[node] = val
            for other in path[node]:
                if other not in seen:
                    stack.append((other, val))
        print(' '.join(map(str, res)))

if __name__ == '__main__':
    Solution().main()

### FIXED CODE ###

from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict
from bisect import bisect_left


class Solution:
    def main(self):
        path = defaultdict(list)
        N, Q = map(int, input().split())
        freq = [0] * N
        for i in range(N-1):
            ai, bi = map(int, input().split())
            path[ai-1].append(bi-1)
            # path[bi-1].append(ai-1)

        for i in range(Q):
            p, x = map(int, input().split())
            freq[p-1] += x

        stack = [(0, 0)]
        seen = set()
        res = freq[:]
        for i in range(N):
            for other in path[i]:
                res[other] += res[i]

        print(' '.join(map(str, res)))


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

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

listp = [[0 for j in range(31)] for i in range(N)] 
li = [0]*31
for i in range(N):
    for j in range(30,-1,-1):
        if A[i] >= 2**j:
            listp[i][j] = 1
            A[i] -= 2**j
            li[j] = li[j]+1
            if li[j] > 2:
                li[j] = 1
for i in range(N):
    ans = 0
    for j in range(31):
        if li[j] - listp[i][j] == 1:
            ans += 2**j
    print(ans, end=" ")

### FIXED CODE ###

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

s = 0
for i in range(N):
    s ^= A[i]
for i in range(N):
    ans = s^A[i]
    print(ans, end=" ")
### BUGGY CODE ###

import sys

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

for i in range(N):
    for j in range(i + 1, N):
        if As[i] == As[j]:
            print('NO')
            sys.exit(0)

print('YES')

### FIXED CODE ###

import sys

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

As.sort()
for i in range(N):
    for j in range(i + 1, N):
        if As[i] == As[j]:
            print('NO')
            sys.exit(0)
        if As[j] > As[i]:
            break

print('YES')
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())

    res = 0
    for b in range(K + 1, N + 1):
        p = 0
        q = K
        while b * p + q <= N:
            if b * p + q > 0:
                res += 1
            if q == b - 1:
                p += 1
                q = K
            else:
                q += 1

    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())

    res = 0
    for b in range(K + 1, N + 1):
        p = N // b
        q = N - b * p
        res += max(0, q - K + 1)
        res += p * max(0, b - 1 - K + 1)
        if K == 0:
            res -= 1

    print(res)


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

N = int(input())
print

true_ans = 10 ** 12
for i in range(1,N):
    if N % i == 0:
        ans = N // i
        true_ans = min(ans + i - 2, true_ans)
        if(i > N ** 0.5):
            break

print(true_ans)

### FIXED CODE ###

N = int(input())

n_hoge = int(N ** 0.5)
print

true_ans = 10 ** 12
for i in range(1,n_hoge+1):
    if N % i == 0:
        ans = N // i
        true_ans = min(ans + i - 2, true_ans)

print(true_ans)
### BUGGY CODE ###

s = input()
def getScore(arr):
    total = 0
    minus = 0
    start = 0
    while 0 in arr[start:]:
        total += arr.index(0, start)
        total -= minus
        minus += 1
        start = arr.index(0, start) + 1

    return total

total = 0
data = []
toInt = {'A':1, 'B':2, 'C':2}
i = 0
while i < len(s)-1:
    # BC=>0
    if s[i] == 'B' and s[i+1] == 'C':
        data.append(0)
        i += 1
    elif s[i] == 'A':
        data.append(toInt[s[i]])
    else:
        if len(data) > 0:
            total += getScore(data)
            data = []
    i+=1

if len(data) > 0:
    total += getScore(data)
    data = []
    
print(total)

### FIXED CODE ###

s = input()
total = 0
i = 0
inRange = False
range_start = 0
range_minus = 0
range_cnt = 0

while i < len(s)-1:
    # BC=>0
    if s[i] == 'B' and s[i+1] == 'C':
        if inRange:
            total += (range_cnt - range_minus)
            range_cnt += 1
            range_minus += 1
        i += 1
    elif s[i] == 'A':
        inRange = True
        range_cnt += 1
    else:
        inRange = False
        range_start = 0
        range_minus = 0
        range_cnt = 0
    i+=1
    
print(total)
### BUGGY CODE ###

n,q=map(int,input().split())
event=[]
for _ in range(n):
  s,t,x=map(int,input().split())
  event.append([s-x,1,x])
  event.append([t-x,-1,x])
event=sorted(event,key=lambda x:x[0])
event.append([10**10,1,10**10])
pos=[int(input()) for _ in range(q)]
sx=set()
cnt=0
m=10**10
ans=[]
for p in pos:
  while event[cnt][0]<=p:
    s,f,x=event[cnt]
    cnt+=1
    if f==1:
      sx.add(x)
      m=min(m,x)
    else:
      sx.remove(x)
      if m==x:
        if len(sx)==0:
          m=10**10
        else:
          m=min(sx)
  if sx:
    ans.append(m)
  else:
    ans.append(-1)
for i in ans:
  print(i)

### FIXED CODE ###

from bisect import bisect_left

n,q=map(int,input().split())
work=[list(map(int,input().split())) for _ in range(n)]
work=sorted(work,key=lambda x:x[2])
pos=[int(input()) for _ in range(q)]
ans=[-1]*q
checked=[-1]*q
for s,t,x in work:
  l=bisect_left(pos,s-x)
  r=bisect_left(pos,t-x)
  while l<r:
    if checked[l]==-1:
      checked[l]=r
      ans[l]=x
      l+=1
    else:
      l=checked[l]
for i in ans:
  print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
AS = [0]
for i in range(N):
    AS += [AS[i] + A[i]]
AN = []
for i in range(N):
    for j in range(i, N):
        AN += [AS[j + 1] - AS[i]]
ans = 0
for i in range(41, -1, -1):
    c = 0
    p = ans + 2 ** i
    for x in AN:
        if p & x == p:
            c += 1
    if c >= K:
        ans += 2 ** i
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
AS = [0]
for i in range(N):
    AS += [AS[i] + A[i]]
AN = []
for i in range(N):
    for j in range(i, N):
        AN += [AS[j + 1] - AS[i]]
ans = 0
for i in range(41, -1, -1):
    c = 0
    p = ans + 2 ** i
    for x in AN:
        if p & x == p:
            c += 1
    if c >= K:
        ans += 2 ** i
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
magic = []
# Aは威力Bは消費魔力
for i in range(N):
    A, B = map(int, input().split())
    magic.append([A,B])

# DPで解く
# DP[i]ダメージをi与えた時の最低使用魔力
# DP[H]ダメージがH以上になったときの最低使用魔力
# DP[i] = -1 のときは計算しない
DP = [-1 for _ in range(H+1)]
DP[0] = 0

for i in range(H):
    if DP[i] == -1:
        pass
    else:
        for j in range(N):
            h = i + magic[j][0]
            mp = DP[i] + magic[j][1]
            if h <= H and DP[h] == -1:
                DP[h] = mp
            elif h <= H and DP[h] != -1:
                if DP[h] > mp:
                    DP[h] = mp
            elif h > H and DP[H] == -1:
                DP[H] = mp
            elif h >H and DP[H] != -1:
                if DP[H] > mp:
                    DP[H] = mp

#print(DP)
print(DP[H])

### FIXED CODE ###

'''
# 以下はTLである
H, N = map(int, input().split())
magic = []
# Aは威力Bは消費魔力
for i in range(N):
    A, B = map(int, input().split())
    magic.append([A,B])

# DPで解く
# DP[i]ダメージをi与えた時の最低使用魔力
# DP[H]ダメージがH以上になったときの最低使用魔力
# DP[i] = -1 のときは計算しない
DP = [-1 for _ in range(H+1)]
DP[0] = 0

for i in range(H):
    if DP[i] == -1:
        pass
    else:
        for j in range(N):
            h = i + magic[j][0]
            mp = DP[i] + magic[j][1]
            if h <= H and DP[h] == -1:
                DP[h] = mp
            elif h <= H and DP[h] != -1:
                if DP[h] > mp:
                    DP[h] = mp
            elif h > H and DP[H] == -1:
                DP[H] = mp
            elif h >H and DP[H] != -1:
                if DP[H] > mp:
                    DP[H] = mp

#print(DP)
print(DP[H])
'''


'''
# 改善しているがこれもTL
# おそらく関数のappendが足を引っ張っている
def test_func(dp, A_list, B_list, i, N):
    # 参考return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)

H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

dp = [0 for _ in range(H+1)]

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[H])
'''

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))
    '''
    # 最初から配列に格納
    magic = []
    for j in range(N):
        # 考えたいiに対してその元となるdpが存在するか
        if i >= A_list[j]:
            magic.append(dp[i-A_list[j]] + B_list[j])
        # 初めての
        else:
            magic.append(B_list[j])
    # 一番魔力がかからなかったものを採用する
    return min(magic)
    '''
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

dp = [0 for _ in range(H+1)]

for i in range(1,H+1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

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

# E - Coprime

import math
from functools import reduce
from itertools import chain
from collections import Counter

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

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def primes_under(n):
    plist = []
    isprime = [1] * (n + 1)
    for p in range(2, n + 1):
        if isprime[p]:
            plist.append(p)
            for q in range(p + p, n + 1, p):
                isprime[q] = 0
    return plist

primes = primes_under(10 ** 6)

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    sqrtn = math.sqrt(n)
    i = 0
    while primes[i] <= sqrtn:
        if n % primes[i] == 0:
            fac.add(primes[i])
            n //= primes[i]
        else:
            i += 1
    if n > 1:
        fac.add(n)
    return fac

c = Counter(chain.from_iterable(map(factors, a)))
if max(c.values(), default=0) > 1:
    print("setwise coprime")
else:
    print("pairwise coprime")


### FIXED CODE ###

# E - Coprime

import math
from functools import reduce

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

if reduce(math.gcd, a) > 1:
    print("not coprime")
    exit()

def factors(n):
    """Return the list of prime factors of n."""
    fac = set()
    sqrtn = math.sqrt(n)
    d = 2
    while d <= sqrtn:
        if n % d == 0:
            fac.add(d)
            n //= d
        else:
            d += 1
    if n > 1:
        fac.add(n)
    return fac

count = [0] * (10 ** 6 + 1)
for x in a:
    for f in factors(x):
        count[f] += 1
        if count[f] > 1:
            print("setwise coprime")
            exit()
print("pairwise coprime")
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
answers = []
for i in range(Q):
    l, r = map(int, input().split())
    answers.append(S[l-1:r].count('AC'))
for answer in answers:
    print(answer)


### FIXED CODE ###

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

N = int(input())
A = list(input().split())
C = []

for n in range(N):
  B = A[:]
  B.pop(n)
  C.append(eval("^".join(B)))

print(*C,sep=" ")

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
b = 0
C = []

for a in A:
  b^=a

for a in A:
  C.append(a^b)

print(*C)
### BUGGY CODE ###

n, m = map(int, input().split())
p = sorted(list(map(int, input().split())))
for i in range(m):
    p.append(p.pop(-1)//2)
    p.sort()
print(sum(p))

### FIXED CODE ###

import heapq as hq
n, m = map(int, input().split())
a = []
for i in input().split(): hq.heappush(a, -int(i))
for i in range(m): hq.heappush(a, int(hq.heappop(a)/2))
print(-sum(a))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        V = i * R + j * G
        if N >= V and (N - V) % B == 0:
            ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(N//R + 1):
    for j in range(N//G + 1):
        V = i * R + j * G
        if N >= V and (N - V) % B == 0:
            ans += 1

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

import sys
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")
### BUGGY CODE ###

def main():
    N=int(input())
    a=[]
    for i in range(N):
        A=list(map(int,input().split()))
        a.append(sum(2**i*A[i] for i in range(N)))
    mod=10**9+7
    
    dp=[0]*(2**N)
    dp[0]=1
    for i in range(1,2**N):
        m=bin(i).count("1")
        for j in range(N):
            if (i&a[m-1])>>j&1==1:
                dp[i]+=dp[i-2**j]
        dp[i]%=mod
    
    print(dp[-1])

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N=int(input())
    a=[]
    for i in range(N):
        a.append(list(map(int,input().split())))
    mod=10**9+7

    dp=[0]*(2**N)
    dp[0]=1
    for i in range(1,2**N):
        m=[j for j in range(N) if i>>j &1==1]
        for j in m:
            dp[i]+=dp[i-2**j]*a[len(m)-1][j]
        dp[i]%=mod
    
    print(dp[-1])

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

n=int(input())
S=[sorted(list(input())) for i in range(n)]
ans=0

for i in S:
  ans+=S.count(i)-1
print(ans//2)

### FIXED CODE ###

n = int(input())
d = {}
ans = 0
for i in range(n):
    s = str(sorted(input()))
    if s in d:
        ans+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(ans)
### BUGGY CODE ###

import numpy as np

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

l.sort()
s=0
for i in range(n):
  for j in range(i+1,n):
    k=np.searchsorted(l,l[i]+l[j],side="left")
    s+=k-(j+1)
    
print(s)

### FIXED CODE ###


n=int(input())
l=list(map(int , input().split()))
#尺取り法
l.sort()
s=0
for i in range(n):
  if i+2<n:
    k=i+2
  else:
    break
  for j in range(i+1,n):
    while (k<n and l[k]<l[i]+l[j]):
      k+=1
    s+=k-(j+1)
print(s)