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

N,*s=open(0).read().split()
s = ["".join(sorted(s_)) for s_ in s]
cnt = 0
for i in range(len(s)):
  cnt += (s[i:].count(s[i])-1)
print(cnt)

### FIXED CODE ###

n,*S=open(0).read().split()

from collections import defaultdict
dic = defaultdict(int)

for s in S:
  dic["".join(sorted(s))]+=1

print(sum([(v*(v-1))//2 for v in dic.values()]))
### BUGGY CODE ###

n = int(input())
l_list = list(int(i) for i in input().split())
list.sort(l_list, reverse=True)
count = 0
for i in range(n):
    a = l_list[i]
    for j in range(i+1, n):
        b = l_list[j]
        for k in range(j+1, n):
            c = l_list[k]
            if a < b+c and b < c+a and c < a+b:
                count += 1
print(count)


### FIXED CODE ###

import bisect

n = int(input())
l = list(int(i) for i in input().split())
list.sort(l)
count = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)
        count += index_c - j -1

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

n,k = map(int,input().split())
p = [int(i) for i in input().split()]
ans = []
maxv = max(p)
dp = [i+1 for i in range(maxv+1)]
for i in range(1,maxv+1):
    dp[i] = dp[i-1]+dp[i]
dp = [j/(i+1) for i,j in enumerate(dp)]

def func(n,dp):
    ans = 0
    for i in n:
        ans += dp[i-1]
    return ans

maxv = 0
for i in range(n-k+1):
    a = func(p[i:(i+k)],dp)
    if maxv < a:
        maxv = a
    
print(maxv)

### FIXED CODE ###

n,k = map(int,input().split())
p = [(int(i)+1)/2 for i in input().split()] #期待値にして格納

#累積和を求める
for i in range(1,n):
    p[i]=p[i-1]+p[i]
mx = p[k-1]
for i in range(k,n):
    a = p[i] - p[i-k]
    if a > mx:
        mx = a
        
print(mx)
### BUGGY CODE ###

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

MOD = pow(10, 9) + 7

dp = [[0 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    S = [0] * (K+1)
    S[0] = dp[i][0]
    # 累積和
    for j in range(1, K+1):
        S[j] = (dp[i][j] + S[j - 1]) % MOD

    for j in range(K+1):
        if j-1 >= A[i]:
            dp[i+1][j] = (S[j] - S[j-1-A[i]]) % MOD
        else:
            dp[i+1][j] = S[j]

print(dp[N][K])


### FIXED CODE ###

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

MOD = pow(10, 9) + 7

dp = [[0 for i in range(K+1)] for j in range(N+1)]
dp[0][0] = 1

for i in range(N):
    S = [0] * (K+1)
    S[0] = dp[i][0]
    # 累積和
    for j in range(1, K+1):
        S[j] = (dp[i][j] + S[j - 1]) % MOD

    for j in range(K+1):
        if j-1 >= A[i]:
            dp[i+1][j] = (S[j] - S[j-1-A[i]]) % MOD
        else:
            dp[i+1][j] = S[j]

print(dp[N][K])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        return 2
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            return f
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
        return n
    return n

A_B = prime_factorize(X)
A_B_other = X // A_B
A = -120
while True:
    B = A - A_B

    if A ** 5 - B ** 5 == X:
        print(A, int(B))
        exit()
    B = A - A_B_other

    if A ** 5 - B ** 5 == X:
        print(A, int(B))
        exit()

    A += 1


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

X = input_int()

for a in range(2000):
    A = a - 1000

    for b in range(2000):
        B = b - 1000
        if A ** 5 - B ** 5 == X:
            print("{} {}".format(A, B))
            exit()
### BUGGY CODE ###

s = input()
q = int(input())
rev = 0

for i in range(q):
    a = input()
    
    if a[0] == '1':
        rev += 1
    if a[0] == '2':
        if (int(a[2]) + rev) % 2 == 1:
            s = a[4] + s
        else:
            s += a[4]
    
if rev%2 == 0:
    print(s)
else:
    s = list(reversed(s))
    ans = "".join(s)
    print(ans)

### FIXED CODE ###

s = input()
q = int(input())
rev = 0
mae = []
usiro = []

for i in range(q):
    a = input()
    
    if a[0] == '1':
        rev += 1
    else:
        if (int(a[2]) + rev) % 2 == 1:
            mae.append(a[4])
        else:
            usiro.append(a[4])
            
mae = mae[::-1]
mae2 = "".join(mae)
usiro2 = "".join(usiro)
if rev%2 == 0:
    print(mae2 + s + usiro2)
else:
    ans = mae2 + s + usiro2
    print(ans[::-1])
### BUGGY CODE ###

import math
s = input()[::-1] # 入力文字列を逆順でsに格納
n = len(s)
taro = [0]*n
s_ = [0]*n
b = 1
num = 0
for i in range(n):
    s_[i] = int(s[i])*b +num
    num += int(s[i])*b
    num %=2019
    b *=10
    b %2019

for i in range(n):
    a = s_[i]%2019
    taro[i]=a
# print(taro)
counts = [0]*2019
for i in range(n):
    counts[taro[i]]+=1
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
# print(counts)
ans = 0
for j in counts:
    if j>=2:
        ans +=combinations_count(j, 2)
ans += counts[0]

print(ans)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N = int(input())
A_list = list(map(int, input().split()))
myans_list =  [ [0 for n in range(N)] for nn in range(N) ]
myans = 0
for n in range(N):
    for nn in range(N):
        myans_list[n][nn] = A_list[n] * A_list[nn]
#for n in myans_list:
#    print(n)
myans = 0
for n in range(N-1):
    for nn in range(n+1, N):
        myans += myans_list[n][nn]
print(myans%(1000000007))

### FIXED CODE ###

N = int(input())
A_list = list(map(int, input().split()))
#myans_list =  [ [0 for n in range(N)] for nn in range(N) ]
#myans = 0
#for n in range(N):
#    for nn in range(N):
#        myans_list[n][nn] = A_list[n] * A_list[nn]
#for n in myans_list:
#    print(n)
mysum = sum(A_list)
myans = 0
for n in range(N-1):
    mysum -= A_list[n]
    myans +=  mysum*A_list[n]
print(myans%(1000000007))
### BUGGY CODE ###

N=int(input())

S=[]
S_count=dict()

total=0

for n in range(N):
    s=input()
    s=''.join(sorted(s))
    if s in S:
        total+=S_count[s]
        S_count[s]+=1

    else:
        S_count[s]=1
    S.append(s)

print(total)

### FIXED CODE ###


N=int(input())
S=[]
total=0

for s in range(N):
    tmp=input()
    S.append("".join(sorted(tmp)))

S=sorted(S)
S_key=list(set(S))
count=[0]*len(S_key)
S_dict=dict(zip(S_key,count))


for s in S:
    total+=S_dict[s]
    S_dict[s]+=1

print(total)
### BUGGY CODE ###

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

a,b,c=sorted(a),sorted(b),sorted(c)

la=[]
for i in range(n):
    p=[0,n-1]
    for j in range(n):
        if p[1]-p[0]==1 and n>2:
            break
        else:
            if a[i]<b[0]:
                p[1]=0
                break
            elif b[n-1]<=a[i]:
                p[1]=n
                break
            elif a[i]<b[(p[0]+p[1])//2]:
                p[1]=(p[0]+p[1])//2
            else:
                p[0]=(p[0]+p[1])//2
    la.append(n-p[1])

lb=[]
for i in range(n):
    p=[0,n-1]
    for j in range(n):
        if p[1]-p[0]==1 and n>2:
            break
        else:
            if b[i]<c[0]:
                p[1]=0
                break
            elif c[n-1]<=b[i]:
                p[1]=n
                break
            elif b[i]<c[(p[0]+p[1])//2]:
                p[1]=(p[0]+p[1])//2
            else:
                p[0]=(p[0]+p[1])//2
    lb.append(n-p[1])

m=0
for i in range(n):
    m+=sum(lb[n-la[i]:n])
print(m)


### FIXED CODE ###

n=int(input())
a=map(int,input().split())
b=map(int,input().split())
c=map(int,input().split())
a=sorted(a)
b=sorted(b)
c=sorted(c)

import bisect

m=0
d=[0 for i in range(n)]
for i in range(n):
    y=bisect.bisect_right(c,b[n-1-i])
    m+=n-y
    d[n-1-i]=m

m=0
for i in a:
    x=bisect.bisect_right(b,i)
    try :
        m+=d[x]
    except IndexError:
        pass
    
print(m)
### BUGGY CODE ###

import scipy.sparse as sps
import scipy.sparse.csgraph as spsc
import numpy as np
from time import process_time as timer

N,M = map(int,input().split())

S,T = map(int,input().split())
S,T = S-1,T-1

E = sps.dok_matrix((N,N),dtype=int)

def it():
  for _ in range(M):
    u,v,d = map(int,input().split())
    u,v = u-1,v-1
    yield ((u,v),d)
E.update(it())


dS,dT = spsc.dijkstra(E,directed=False, indices=[S,T]).astype(int)
D = dS[T]
D2 = D//2

E = tuple((u,v) for d,u,v in ((d,u,v) if dS[u] <= dS[v] else (d,v,u) for (u,v),d in E.items()) if dS[u]+d+dT[v] == D)

MOD = 10**9+7


def helper(start, edges):
  cnts = [0]*N
  cnts[start] = 1
  for d,u,v in edges:
    cnts[v] = (cnts[v] + cnts[u]) % MOD
  return cnts


Sn = helper(S,sorted((dS[u],u,v) for u,v in E))
Tn = helper(T,sorted((dT[v],v,u) for u,v in E))

from functools import reduce

def it():
  for v in range(N):
    if dS[v] == D2:
      yield (Sn[v]*Tn[v])**2

c0 = reduce(lambda x,y: (x+y)%MOD, it(), 0) if D%2==0 else 0

diff = dS-dT

def it():
  for u,v in E:
    if diff[u] < 0 < diff[v]:
      yield (Sn[u]*Tn[v])**2

c1 = reduce(lambda x,y: (x+y)%MOD, it(), 0)

total = Sn[T]*Tn[S]
cnt = c0+c1

print((total-cnt)%MOD)


### FIXED CODE ###

from collections import defaultdict
from functools import reduce
import heapq as hq
from sys import stdin
 
MOD = 10**9+7
N,M = map(int,stdin.readline().split())
S,T = map(int,stdin.readline().split())
S,T = S-1,T-1
 
E = defaultdict(list)
lines = stdin.readlines()
for line in lines:
  u,v,d = map(int,line.split())
  E[u-1].append((v-1,d))
  E[v-1].append((u-1,d))
 
dS = [None]*N
dT = [None]*N
 
Q = [(0,S,False),(0,T,True)]
 
D = float('inf')
 
 
while Q:
  d,v,f = hq.heappop(Q)
  if d*2 > D:
    break

  dM = dT if f else dS
  dN = dS if f else dT
  if dM[v] is None:
    dM[v] = d
    for u,dd in E[v]:
      if dM[u] is None and (d+dd)*2 <= D:
        hq.heappush(Q,(d+dd,u,f))
 
  if dN[v] is not None:
    D = min(dN[v]+d,D)
 
del Q

def helper(start,dist):
  cnts = [0]*N
  cnts[start] = 1

  for d,v in sorted((d,v) for v,d in enumerate(dist) if d is not None):
    c = cnts[v]
    for u,dd in E[v]:
      if dd+d == dist[u]:
        cnts[u] = (cnts[u]+c) % MOD

  return cnts

Sn = helper(S,dS)
Tn = helper(T,dT)


def it():
  for v in range(N):
    if dS[v] is not None:
      ds = dS[v]
      if dT[v] == ds and ds*2 == D:
        yield Sn[v]*Tn[v] % MOD
      else:
        for u,d in E[v]:
          if dT[u] is not None and abs(dT[u]-ds) < d and ds+d+dT[u] == D:
            yield Sn[v]*Tn[u] % MOD


X = list(it())

 
total = reduce(lambda a,b:(a+b)%MOD, X,0)
total = total*total % MOD
 
sub = reduce(lambda a,b:(a+b)%MOD, map(lambda x: x*x % MOD, X),0)
print((total-sub)%MOD)
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
l = [0] * N
ans = 0
count = 0
check = [False] * N

while(count <= N - 1):
    check = [False] * N
    for i in range(N):
        if l[i] < N - 1:
            to = A[i][l[i]] - 1
            if (not check[to]) and (not check[i]):
                if A[to][l[to]] - 1 == i:
                    l[i] += 1
                    l[to] += 1
                    check[to] = True
                    check[i] = True
                if l[i] == N - 1:
                    count += 1
                if l[to] == N - 1:
                    count += 1
    ans += 1
    if ans > N * (N - 1) // 2 + 1:
        print(-1)
        exit()
    # print(l, ans)

print(ans)


### FIXED CODE ###

import sys
import time
def input():
    return sys.stdin.readline()
 
def main():
    a = time.time()
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []
    next = False
 
    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                        next = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if not next:
            print(-1)
            exit()
        next = False

        b = time.time()
        if b - a >= 1.7:
            print(N*(N - 1)//2)
            exit()
        # print(l, ans)
 
    print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
import sys

for line in sys.stdin:
    n = int(line)

    nums = [1] * (n+1)
    nums[:2] = [0,0]
    
    cnt = 0
    while cnt <= math.sqrt(n):
        flg = nums[cnt]
        if flg == 1:
            k = 2
            while k*cnt <= n:
                nums[k*cnt] = 0
                k += 1
        cnt += 1
    print sum(nums)

### FIXED CODE ###

import math
import sys

n = 999999
nums = [1] * (n+1)
nums[:2] = [0,0]
    
cnt = 0
while cnt <= math.sqrt(n):
    flg = nums[cnt]
    if flg == 1:
        k = 2
        while k*cnt <= n:
            nums[k*cnt] = 0
            k += 1
    cnt += 1


for line in sys.stdin:
    n = int(line)
    print sum(nums[:n+1])
### BUGGY CODE ###

k = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

pn=factorization(k)

go =0
keta = len(str(k))
sevens = []

if k % 2 == 0 or k %5 == 0:
    print(-1)
elif str(k)[-1] == "3":
    for i in range(9,10**100000,10):
        if not str(k * i).count('7') == len(str(k*i)):
            continue
        else:
            print(str(k * i).count('7'))
elif str(k)[-1] == "7":
    for i in range(1,10**100000,10):
        if not str(k * i).count('7') == len(str(k*i)):
            continue
        else:
            print(str(k * i).count('7'))
elif str(k)[-1] == "9":
    for i in range(3,10**100000,10):
        if not str(k * i).count('7') == len(str(k*i)):
            continue
        else:
            print(str(k * i).count('7'))
elif str(k)[-1] == "1":
    for i in range(7,10**100000,10):
        if not str(k * i).count('7') == len(str(k*i)):
            continue
        else:
            print(str(k * i).count('7'))



### FIXED CODE ###

k = int(input())

go = 0
keta = len(str(k))

for i  in range(10**1000000):
    if k % 2 ==0:
        print(-1)
        break
    if k % 5==0:
        print(-1)
        break
    else:
        go =(go*10+7) %k
        if go ==0:
            print(i+1)
            break
### BUGGY CODE ###

import numpy as np
N = int(input())
alist = np.array(list(map(int, input().split())))
alist
alistp = alist + 1
alistm = alist - 1
k = []
d = {}
for a in alist:
    if a not in k:
        k.append(a)
        d[a] = 1
    else:
        d[a] += 1
for a in alistp:
    if a not in k:
        k.append(a)
        d[a] = 1
    else:
        d[a] += 1
for a in alistm:
    if a not in k:
        k.append(a)
        d[a] = 1
    else:
        d[a] += 1
print(max(d.values()))

### FIXED CODE ###

import numpy as np
N = int(input())
alist = np.array(list(map(int, input().split())))
alist
alistp = alist + 1
alistm = alist - 1
d = {}
for a in alist:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
for a in alistp:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
for a in alistm:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
print(max(d.values()))
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
L = [N + 1]
con = 0
for i in range(N):
  if min(L) > P[i]:
    con += 1
  L.append(P[i])
print(con)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
c = 10 ** 20
con = 0
for i in range(N):
  if c > P[i]:
    con += 1
    c = P[i]
print(con)
### BUGGY CODE ###

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

def z_algo(s):
    """
    param s:str
    return list of int with length len(s)
    """
    # initialization
    n=len(s)
    z=[0]*n
    z[0]=n
    # construct
    L,R=0,0
    for i in range(1,n):
        if i>R: # 過去の結果が全く使えない
            L=R=i
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1 # 0-indexedでiと比較するため
        elif z[i-L]<R-i+1:
            z[i]=z[i-L]
        else:
            L=i
            R+=1 # Rまでは確定しているので、R+1から確認
            while(R<n and s[R-L]==s[R]): R+=1
            z[i]=R-L
            R-=1
    return z

ans = 0
for i in range(N-1):
    z = z_algo(S[i:])
    z = z[(len(z)+1)//2:]
    max_z = max(z)
    ans = max(ans, max_z)
print(ans)

### FIXED CODE ###

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for j, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()
### BUGGY CODE ###

n = int(input())
s = input()
sum = s.count("R") * s.count("G") * s.count("B")
for i in range(1, n-1):
  for j in range(i+1, n):
    if(2*j-i-1 <n):
      if(len({s[i-1], s[j-1], s[2*j-i-1]}) == 3):
        sum -= 1
print(sum)

### FIXED CODE ###

n = int(input())
s = input()
sum = s.count("R") * s.count("G") * s.count("B")
for i in range(1, n-1):
  for j in range(i+1, n):
    k = 2*j-i-1
    if(k >= n):
      break
    if(len({s[i-1], s[j-1], s[k]}) == 3):
        sum -= 1
print(sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
now='.'
ans=0
x,y=0,0
if S[x][y]=='#':
  ans+=1
  now='#'
  
def findroot(x,y):
  global nextkouho,now,S
  nextkouho.add((x,y))
  if x<H-1 and S[x+1][y]==now:
    findroot(x+1,y)
  if y<W-1 and S[x][y+1]==now:
    findroot(x,y+1)
kouho=[(0,0)]
while 1:
  nextkouho=set()
  for x,y in kouho:
    if x<H-1 and S[x+1][y]==now:
      findroot(x+1,y)
    else:
      nextkouho.add((x,y))
    if y<W-1 and S[x][y+1]==now:
      findroot(x,y+1)
    else:
      nextkouho.add((x,y))
  if (H-1,W-1) in nextkouho:
    break
  if now=='#':
    now='.'
  else:
    ans+=1
    now='#'
  kouho=nextkouho
  #print(nextkouho,kouho,now,ans)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
dp=[0]*W
if S[0][0]=='#':
  dp[0]=1
for j in range(1,W):
  if S[0][j]!=S[0][j-1] and S[0][j-1]=='.':
    dp[j]=dp[j-1]+1
  else:
    dp[j]=dp[j-1]
for i in range(1,H):
  if S[i][0]!=S[i-1][0] and S[i-1][0]=='.':
    dp[0]=dp[0]+1
  for j in range(1,W):
    hidari=1 if S[i][j]!=S[i][j-1] and S[i][j-1]=='.' else 0
    ue=1 if S[i][j]!=S[i-1][j] and S[i-1][j]=='.' else 0
    dp[j]=min(dp[j-1]+hidari,dp[j]+ue)
print(dp[-1])
### BUGGY CODE ###

from collections import deque

N,M,*f = map(int, open(0).read().split())
uv = [f[i:i+2] for i in range(0, len(f)-2, 2)]
S = f[-2]
T = f[-1]
connected = [[] for _ in range(N+1)]
for u, v in uv:
    connected[u].append(v)

d = deque([S])
for i in range(1,N+1):
    for j in range(3):
        for k in range(len(d)):
            temp = d.popleft()
            for edge in connected[temp]:
                d.append(edge)
    if T in d:
        print(i)
        break
else:
    print('-1')

### FIXED CODE ###

from collections import deque

N,M,*f = map(int, open(0).read().split())
uv = [f[i:i+2] for i in range(0, len(f)-2, 2)]
S = f[-2]
T = f[-1]
connected = [[] for _ in range(N+1)]
for u, v in uv:
    connected[u].append(v)
dist = [[-1] * 3 for _ in range(N+1)]
dist[S][0] = 0
ans = 0
d = deque([(S,0)])
while d:
    temp = d.popleft()
    for edge in connected[temp[0]]:
        if edge == T and temp[1] == 2:
            print((dist[temp[0]][2]+1)//3)
            break
        else:
            if dist[edge][(temp[1]+1)%3] < 0:
                dist[edge][(temp[1]+1)%3] = dist[temp[0]][temp[1]] + 1
                d.append((edge,(temp[1]+1)%3))
    else:
        continue
    break
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
a = input()
q = int(input())
for i in range(q):
    b, c = map(str, input().split())
    A = a.replace(b, c)    
    ans = 0
    s = "0"
    for j in list(A):
        if j != " ":
            s += j
        else :
            ans += int(s[1:])
            s = "0"
    ans += int(s[1:])
    print(ans)
    a = A
    


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
l = [0]*(10**5+1)
all_sum = sum(a)
for i in a:
    l[i] += 1
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    cnt = l[b]
    l[c] += cnt 
    all_sum += cnt * (c-b)
    l[b] = 0
    print(all_sum)
### BUGGY CODE ###

n,a,b = map(int,input().split())
lim = 10**9+7
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod
c = Combination(n)
print((pow(2,n,lim)-c.C(n,a)-c.C(n,b)-1) % lim)


### FIXED CODE ###

n,a,b = map(int,input().split())
lim = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

print((pow(2,n,lim)-combination(n,a)-combination(n,b)-1) % lim)