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

from collections import Counter

N = int(input())
words = [Counter(input()) for _ in range(N)]
ans = 0
counters = []
counters_counts = []
for counter in words:
    try:
        idx = counters.index(counter)
        counters_counts[idx] += 1
    except ValueError:
        counters.append(counter)
        counters_counts.append(1)

for count in counters_counts:
    ans += int((count * (count-1)) / 2)
print(ans)

### FIXED CODE ###

from collections import Counter

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))

N = int(input())
words = [hashabledict(dict(Counter(input()))) for _ in range(N)]
ans = 0
counter_hash = {}
for counter in words:
    if counter not in counter_hash.keys():
        counter_hash[counter] = 1
    else:
        counter_hash[counter] += 1
 
for count in counter_hash.values():
    ans += int((count * (count-1)) / 2)
print(ans)
### BUGGY CODE ###

ans = 0

N = int(raw_input())

A = []

for i in range(N):
  A.append(int(raw_input()))

A.append(0)

for i in range(N):

  while True:

    if A[i] == 0:
      break

    elif A[i] == 1:

      if A[i + 1] >= 1:
        A[i + 1] -= 1
        ans += 1

      break

    A[i] -= 2
    ans += 1

print ans

### FIXED CODE ###

ans = 0

N = int(raw_input())

A = []

for i in range(N):
  A.append(int(raw_input()))

A.append(0)

for i in range(N):

  while True:

    if A[i] == 0:
      break

    elif A[i] == 1:

      if A[i + 1] >= 1:
        A[i + 1] -= 1
        ans += 1

      break

    ans += A[i] / 2

    A[i] = A[i] % 2

print ans
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans *= i
print(ans%(10**9+7))


### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = ans*i % (10**9+7)
print(ans)
### BUGGY CODE ###

def z_algolithm(S):
    length = len(S)
    A = [0]*length
    i = 1; j = 0
    A[0] = length
    while i < length:
        while i+j < length and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = 0
    for a in A:
        if a <= length//2:
            ans = max(ans, a)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S[x:]) for x in range(N)])
print(ans)

### FIXED CODE ###

def z_algolithm(S, x):
    length = len(S) - x
    A = [0]*length
    B = [0]
    i = 1; j = 0
    while i < length:
        while i+j < length and S[x+j] == S[x+i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        B.append(min(j, i))
        k = 1
        while k < length - i  and k + A[k] < j :
            A[i+k] = A[k]
            k += 1
        i += k
        j -= k
    ans = max(B)
    return ans

N = int(input())
S = input()
ans = max([z_algolithm(S, x) for x in range(N)])
print(ans)
### BUGGY CODE ###

n, x = map(int, input().split())
a = [int(m) for m in input().split()]
#x=kのときを考える
#f(i,k)を考える，メモ化しておく
memos = []
for k in range(n):
    memos.append([float("INF") for i in range(n)])

def f(i,k):
    if k == 0:
        memos[k][i] = a[i]
        return a[i]
    if memos[k][i] != float("INF"):
        return memos[k][i]
    else:
        memos[k][i] = min(f(i, k - 1), a[i - k])
        return memos[k][i]

ansli = []
tmpsum = 0
for k in range(n):
    for i in range(n):
        tmpsum += f(i, k)
    ansli.append(x * k + tmpsum)
    tmpsum = 0

print(min(ansli))

### FIXED CODE ###

n, x = map(int, input().split())
a = [int(m) for m in input().split()]
#x=kのときを考える
#f(i,k)を考える，メモ化しておく
memos = []
for k in range(n):
    memos.append([float("INF") for i in range(n)])

def f(i,k):
    if k == 0:
        memos[k][i] = a[i]
        return a[i]
    if memos[k][i] != float("INF"):
        return memos[k][i]
    else:
        memos[k][i] = min(f(i, k - 1), a[i - k])
        return memos[k][i]

ansli = []
tmpsum = 0
for k in range(n):
    for i in range(n):
        tmpsum += f(i, k)
    ansli.append(x * k + tmpsum)
    tmpsum = 0

print(min(ansli))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
input()
stones = tuple(map(int, input().split()))
 
tracker = {}
def min_cost(remaining_stones):
    if len(remaining_stones) == 1:
        return 0
    if len(remaining_stones) == 2:
        return abs(remaining_stones[0] - remaining_stones[1])
    
    jump_1 = remaining_stones[1:]
    if jump_1 not in tracker:
        tracker[jump_1] = min_cost(jump_1)
    jump_2 = remaining_stones[2:]
    if jump_2 not in tracker:
        tracker[jump_2] = min_cost(jump_2)
 
    score_1 = abs(remaining_stones[0] - remaining_stones[1]) + tracker[jump_1]
    score_2 = abs(remaining_stones[0] - remaining_stones[2]) + tracker[jump_2]
    return min(score_1, score_2)
 
 
print(min_cost(stones))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
n = int(input())
stones = list(map(int, input().split()))
stones.reverse()

bottum_up = [-1 for i in range(n)]
bottum_up[0] = 0
bottum_up[1] = abs(stones[0] - stones[1])

for i in range(2,len(stones)):
    score_1 = abs(stones[i] - stones[i-1]) + bottum_up[i-1]
    score_2 = abs(stones[i] - stones[i-2]) + bottum_up[i-2] 
    bottum_up[i] = min(score_1, score_2)

print(bottum_up[-1])
### BUGGY CODE ###

# B
k, s = map(int, input().split())

count = 0
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            if i+j+k == s:
                count += 1
print(count)

### FIXED CODE ###

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

from collections import Counter

def main():
  n = int(input())
  a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
  g = [0]*(n+1)
  g[n] = 1
  for _, x in a:
    if sum(g) < x:
      print('No')
      break
    t = [0]*(n+1)
    for i in range(n, -1, -1):
      if g[i] <= x:
        t[i-1] = t[i] + g[i]
        x -= g[i]
        g[i] = 0
      else:
        t[i-1] = t[i] + x
        g[i] -= x
        x = 0
      t[i] += g[i]
    t[n] = 0
    g = t
  else:
    print('Yes')
  return

if __name__ == '__main__':
  main()

### FIXED CODE ###

from collections import Counter
n = int(input())
a = sorted(Counter(list(map(int, input().split()))).items(), reverse=True)
g = [0]*(n+1)
g[n] = 1
for _, x in a:
  if sum(g) < x:
    print('No')
    break
  t = [0]*(n+1)
  for i in range(n, -1, -1):
    if g[i] <= x:
      t[i-1] = t[i] + g[i]
      x -= g[i]
      g[i] = 0
    else:
      t[i-1] = t[i] + x
      g[i] -= x
      x = 0
  t[n] = 0
  g = [x+y for x,y in zip(g, t)]
else:
  print('Yes')
### BUGGY CODE ###

import math
m = 10**9 + 7
def nCr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

x,y = map(int,input().split())

if max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(nCr(k,n) % m)
else:
    print(0)



### FIXED CODE ###

def nCr(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

x,y = map(int,input().split())

if max(x,y) > 2 *min(x,y):
    print(0)
elif (x+y) % 3 == 0:
    k = (x+y)//3
    n = (2*x-y)//3
    print(nCr(k,n))
else:
    print(0)
### BUGGY CODE ###

S=input()
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  if S[i-1] is "A":
    A[i]=A[i-1]+1
    Q[i]=Q[i-1]
  elif S[i-1] is "?":
    A[i]=A[i-1]
    Q[i]=Q[i-1]+1
  else:
    A[i]=A[i-1]
    Q[i]=Q[i-1]
M=Q[N]
for i in range(1,N+1):
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
for i in range(1,N+1):
  if S[i-1] is "C":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2)))%(10**9+7))
  elif S[i-1] is "?":
    ABC[i]=int((ABC[i-1]+AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3)))%(10**9+7))
  else:
    ABC[i]=ABC[i-1]
print(ABC[N]%(10**9+8))

### FIXED CODE ###

S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
  O=O%(10**9+7)
print(int(ABC[N]%(10**9+7)))
### BUGGY CODE ###

S=input()
keta=len(S)
dp=[[0 for j in range(13)] for i in range(keta)]
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
for i in range(1,keta):
  if S[keta-1-i]=="?":
    for j in range(13):
      for k in range(10):
        dp[i][convert(j,k*(10**i)%13)]+=dp[i-1][j]
        dp[i][convert(j,k*(10**i)%13)]%=DIV
  else:
    ch=int(S[keta-1-i])
    for j in range(13):
      dp[i][convert(j,ch*(10**i)%13)]+=dp[i-1][j]
      dp[i][convert(j,ch*(10**i)%13)]%=DIV

print(dp[len(dp)-1][5])

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###

N=int(input())
L=list(map(int, input().split()))
L.sort()
cnt=0

for i in range(0,N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      if L[k]<L[i]+L[j]:
        if L[i]<L[j]+L[k]:
          if L[j]<L[i]+L[k]:
            cnt+=1
      else:
        break

print(cnt)

### FIXED CODE ###

import bisect

N=int(input())
L=list(map(int, input().split()))
L.sort()

ans=0
for i in range(N-2):
  for j in range(i+1,N-1):
    #small = bisect.bisect_left(L, L[j]-L[i])
    large = bisect.bisect_left(L, L[j]+L[i])    
    #print(i,j,L[i],L[j],"  ",L[j]-L[i],L[j]+L[i],small,large)
    ans += max(large-j-1,0)    

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

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

x = 1
for i in a:
    x *= i

ans = x
if ans > 10**18:
    ans = -1
print(ans)


### FIXED CODE ###

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

x = 1
for i in a:
    x *= i
    if x > 10**18:
        break

ans = x
if ans > 10**18:
    ans = -1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
Am = []
n0 = 0
Ap = []
for a in A:
    if a<0: Am.append(a)
    if a==0: n0+=1
    if a>0: Ap.append(a)

Am = sorted(Am)
Ap = sorted(Ap)
    
nm = len(Am)
np = len(Ap)

Nm = nm*np
N0 = n0*(n0-1)//2 + n0*(nm+np)
Np = nm*(nm-1)//2 + np*(np-1)//2

if K<=Nm:
    # K-th product is negative
    min_ok = 0
    max_ng = -10**20
    while min_ok-max_ng>1:
        tgt = (min_ok+max_ng)//2

        k=0
        i=0
        for a in Am:
            while i<np and a*Ap[i]>tgt: i+=1
            k+=np-i

        if k>=K:
            min_ok = tgt
        else:
            max_ng = tgt
            
    print(min_ok)

elif K<=Nm+N0:
    # K-th product is zero
    print(0)

else:
    # K-th product is positive
    K-= Nm+N0
    
    Am = [-a for a in Am[::-1]]
    
    min_ok = +10**20
    max_ng = 0
    while min_ok-max_ng>1:
        tgt = (min_ok+max_ng)//2

        k=0
        i=np-1
        for j,a in enumerate(Ap):
            while i>=0 and a*Ap[i]>tgt: i-=1
            if i<=j: break
            k+=i-j
            
        i=nm-1
        for j,a in enumerate(Am):
            while i>=0 and a*Am[i]>tgt: i-=1
            if i<=j: break
            k+=i-j
            
        if k>=K:
            min_ok = tgt
        else:
            max_ng = tgt
            
    print(min_ok)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
Am = []
n0 = 0
Ap = []
for a in A:
    if a<0: Am.append(a)
    if a==0: n0+=1
    if a>0: Ap.append(a)

Am = sorted(Am)
Ap = sorted(Ap)
    
nm = len(Am)
np = len(Ap)

Nm = nm*np
N0 = n0*(n0-1)//2 + n0*(nm+np)
Np = nm*(nm-1)//2 + np*(np-1)//2

if K<=Nm:
    # K-th product is negative
    min_ok = 0
    max_ng = -10**20
    while min_ok-max_ng>1:
        tgt = (min_ok+max_ng)//2

        k=0
        i=0
        for a in Am:
            while i<np and a*Ap[i]>tgt: i+=1
            k+=np-i

        if k>=K:
            min_ok = tgt
        else:
            max_ng = tgt
            
    print(min_ok)

elif K<=Nm+N0:
    # K-th product is zero
    print(0)

else:
    # K-th product is positive
    K-= Nm+N0
    
    Am = [-a for a in Am[::-1]]
    
    min_ok = +10**20
    max_ng = 0
    while min_ok-max_ng>1:
        tgt = (min_ok+max_ng)//2

        k=0
        i=np-1
        for j,a in enumerate(Ap):
            while i>=0 and a*Ap[i]>tgt: i-=1
            if i<=j: break
            k+=i-j
            
        i=nm-1
        for j,a in enumerate(Am):
            while i>=0 and a*Am[i]>tgt: i-=1
            if i<=j: break
            k+=i-j
            
        if k>=K:
            min_ok = tgt
        else:
            max_ng = tgt
            
    print(min_ok)
### BUGGY CODE ###

n = int(input())
S = [str(input()) for _ in range(n)]
count = 0
for i in range(n):
    for j in range(n):
        if i == j or i > j: #2つの文字列を選択
            continue
        else:
            ana1 = list(S[i])
            ana2 = list(S[j])
            ana1.sort()
            ana2.sort()
            if ana1 == ana2:
                count += 1
            
print(count)

### FIXED CODE ###

import collections

# nC2を足す理由は、同一文字列からアナグラムとなっている2つの文字列を見つけないといけないから
N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
# ソートした時にそれぞれの文字がリストに分割されるからjoinで文字列に直す
c = collections.Counter(s)
ans = 0
for i in set(s):
    n = c[i]
    ans += n * (n - 1) // 2
print(ans)

# set(s)によって、同じ文字列は消去される。そしてcによって、何回その文字が出ているかを数えれる。
### BUGGY CODE ###

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

count = 0
for i in range(n-1):
    for j in range(i+1, n):
        for k in range(j+1,n):
            if l[k] < l[i] + l[j]:
                count += 1

print(count)

### FIXED CODE ###

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

import bisect

count = 0
for i in range(n-1):
    for j in range(i+1, n):
            ab = l[i] + l[j]
            right = bisect.bisect(l, ab-1)
            left = j + 1
            count += (right - left)

print(count)
### BUGGY CODE ###

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

c = S.count('1')
m = int('0B'+S, 0)

def calc(a, ans):
    if a == 0: return ans
    ans += 1
    m = bin(a).count('1')
    return calc(a%m, ans)
    
for i in range(N):
    if S[i] == '1': b = c - 1
    else: b = c + 1
    if S[i] == '1':
        a = m - 2**(N - 1 - i)
    else: a = m + 2**(N - 1 - i)

    print(calc(a, 0))
    


### FIXED CODE ###

import math
N = int(input())
S = input()

lst0 = [0]*N
lst1 = [0]*N
lst0[0] = 1
lst1[0] = 1
c = S.count('1')
m0 = int(S[-1])
m1 = int(S[-1])
for i in range(1, N):
    lst0[i] += (lst0[i-1]*2)%(c+1)
    if c == 1:lst1[i] = 0
    else: lst1[i] += (lst1[i-1]*2)%(c-1)
    m0 += lst0[i] * int(S[N - 1- i])
    m0 %= c+1
    m1 += (lst1[i] * int(S[N - 1 - i]))
    if c == 1: m1 = 0
    else: m1 %= c-1

memo = [0]*(N+1)

def calc(a):
    global ans, memo
    if a == 0: return ans
    ans += 1
    if memo[a] != 0:
        b = memo[a]
    else:
        b = bin(a).count('1')
        memo[a] = b
    return calc(a%b)
    
for i in range(N):
    if S[i] == '1':
        b = c - 1
        if b == 0: a = 0
        else: a = max((m1 - lst1[N - 1 - i])%b, (m1 - lst1[N - 1 - i]+ b)%b)
    else:
        b = c + 1
        a = (m0 + lst0[N - 1 - i])%b
    if b == 0: print(0)
    elif a == 0:print(1)
    else:
        ans = 1
        print(calc(a))
### BUGGY CODE ###

n, h = map(int, input().split())
h2 = h
l = []
for i in range(n):
  l.append(list(map(int,input().split())))

l_b = sorted(l, key=lambda x: x[1])
l = sorted(l_b, reverse=True, key=lambda x: x[0])
c_a = 0
c_b = 0
b_sum = 0

for i in range(n-1, -1, -1):
  if l_b[i][1] >= l[0][0]:
    b_sum += l_b[i][1]
    h -= l_b[i][1]
    c_b += 1
    if h <= 0:
      print(c_b)
      exit()

while h2 > b_sum:
  h2 -= l[0][0]
  c_a += 1

print(c_a+c_b)


### FIXED CODE ###

n, h = map(int, input().split())
h2 = h
l = []
for i in range(n):
  l.append(list(map(int,input().split())))

l_b = sorted(l, key=lambda x: x[1])
l = sorted(l_b, reverse=True, key=lambda x: x[0])
c_a = 0
c_b = 0
b_sum = 0

for i in range(n-1, -1, -1):
  if l_b[i][1] >= l[0][0]:
    b_sum += l_b[i][1]
    h -= l_b[i][1]
    c_b += 1
    if h <= 0:
      print(c_b)
      exit()
import math
c_a = math.ceil((h2 - b_sum) / l[0][0])


print(c_a+c_b)
### BUGGY CODE ###

import sys
import array

from operator import itemgetter

def upd(ft,i):
	i+=1
	while(i<len(ft)):
		ft[i]+=1
		i+=i&-i

def get(ft,i):
	i+=1
	ret=0
	while(i!=0):
	    ret+=ft[i]
	    i-=i&-i
	return ret


def comb(cnt,x):
	return cnt[x]-1;

def main():

	tl=200100

	ft=[0]*tl


	md = 998244353
	n = int(input())
	xy = [[0]*2 for _ in range(n)]
	yxi = [[0]*3 for _ in range(n)]
	ys = []
	hp = []
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))

	for i in range(n):
		yxi[i]=[xy[i][1],xy[i][0],i]
	yxi.sort(key=itemgetter(0))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	ans=0

	for i in range(n):
		ix=yxi[i][2]
		a=get(ft,ix)
		b=get(ft,n)-a
		c=ix-a
		d=n-ix-1-b
	#	exc=(comb(a+b)+comb(a+c)+comb(b+d)+comb(c+d)-comb(a)-comb(b)-comb(c)-comb(d))%md
	#	cur=(comb(n)-exc)%md
	#	ans=(ans+cur)%md
		ans=(ans+comb(cnt,n)-comb(cnt,a+b)-comb(cnt,a+c)-comb(cnt,b+d)-comb(cnt,c+d)+comb(cnt,a)+comb(cnt,b)+comb(cnt,c)+comb(cnt,d))%md
		upd(ft,ix)

	if(ans<0):ans+=md

	print(ans)

main()


### FIXED CODE ###

import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()
### BUGGY CODE ###

def remove_01_10(S):
	S = S.replace('10', '')
	S = S.replace('01', '')
	return S	


S = input()
N = len(S)
while True:
	if len(S) == len(remove_01_10(S)):
		print(N - len(S))
		exit()
	else:
		S = remove_01_10(S)


### FIXED CODE ###

S = list(input())
N = len(S)
num0 = 0
for i in range(N):
	if S[i] == '0':
		num0 = num0 + 1

num1 = 0
for i in range(N):
	if S[i] == '1':
		num1 = num1 + 1
print(N - abs(num0 - num1))
### BUGGY CODE ###

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

dp = [10**9]*n
dp[0] = 0
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, n): 
    dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, min(k, i)+1))
#    for j in range(1, min(k, i)+1):  
#        dp[i] = min([dp[i], dp[i-j]+abs(h[i]-h[i-j])])
        #print(i, dp[i])

print(dp[n-1])

### FIXED CODE ###

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

dp = [10**9+1]*n
dp[0] = 0
dp[1] = dp[0] + abs(h[1]-h[0])

for i in range(2, n): 
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1, min(k, i)+1)])

print(dp[n-1])
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    nmin = 10**12
    if N == 1:
        print(0)
        exit()
    for n in range(1, max(2, N//2)):
        if N % n == 0:
            nmin = min(nmin, n + N//n - 2)

    print(nmin)

### FIXED CODE ###

import math

if __name__ == "__main__":
    N = int(input())
    nsqrt = math.sqrt(N)
    for i in range(int(nsqrt), 0, -1):
        if N % i == 0:
            print(i + N//i - 2)
            exit()
### BUGGY CODE ###

def knapsack(nums, k):
    n = len(nums)

    # dp[i] is min cost when reaching stone i
    dp = [0] * n
    dp[0] = 0
    for i in range(1, n):
        dp[i] = min([
            dp[i-j] + abs(nums[i] - nums[i-j])
            for j in range(1, k+1) if i - j >= 0]
        )
    return dp[-1]


if __name__ == "__main__":
    _, k = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]
    print(knapsack(nums, k))


### FIXED CODE ###

def knapsack(nums, k):
    n = len(nums)

    # dp[i] is min cost when reaching stone i
    dp = [float('Inf')] * n
    dp[0] = 0
    for i in range(1, n):
        dp[i] = min([
            dp[i-j] + abs(nums[i] - nums[i-j])
            for j in range(1, k+1) if i - j >= 0]
        )
    return dp[-1]


if __name__ == "__main__":
    _, k = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]
    print(knapsack(nums, k))
### BUGGY CODE ###

n = input()
array = []
for i in range(n):
	inst = raw_input().split()
	if inst[0][0] == 'i':
		array.append(int(inst[1]))
	elif inst[0] == "delete":
		if int(inst[1]) in array:
			x = array[::-1].index(int(inst[1]))
			if x != -1 and int(inst[1]):
				del array[-x-1]
	elif inst[0][6] == 'F':
		array.pop()
	else:
		array.pop(0)
print " ".join(map(str,array[::-1]))

### FIXED CODE ###

n = input()
array = []
base = 0
for i in xrange(n):
    inst = raw_input().split()
    if inst[0][0] == 'i':
        array.append(int(inst[1]))
    elif inst[0] == "delete":
        if int(inst[1]) in array:
            x = array[::-1].index(int(inst[1]))
            if x != -1 and int(inst[1]):
                del array[-x-1]
    elif inst[0][6] == 'F':
        array.pop()
    else:
        base += 1
print (" ".join(map(str,array[base:][::-1])))
### BUGGY CODE ###

n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if 1 in ais:
  dp[1]=0
else:
  dp[1]=1
for i in range(2,n+1):
    if i in ais:
        dp[i] = 0
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
ais = []
for _ in range(m):
    ai = int(input())
    ais.append(ai)
dp = [0]*(n+1)
dp[0]=1
if len(ais)>0 and ais[0]==1:
  dp[1]=0
  ais.pop(0)
else:
  dp[1]=1
for i in range(2,n+1):
    if len(ais)>0 and ais[0]==i:
        dp[i] = 0
        ais.pop(0)
    else:
        dp[i] = dp[i-1] + dp[i-2]
print(dp[n]%1000000007)