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

def dfs(v, g, color, paint=0):
	color[v] = paint
	for i in range(len(g)):
		if i == v or g[v][i] == -1:
			continue
		if g[v][i]:
			np = paint if g[v][i] % 2 == 0 else 1 - paint
			g[v][i] = -1
			g[i][v] = -1
			dfs(i, g, color, np)

def resolve():
	n = int(input())
	color = [-1]*n
	g = [[-1]*n for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[u-1][v-1] = w
		g[v-1][u-1] = w
	for v in range(n):
		if color[v] > -1:
			continue
		dfs(v, g, color)

	for i in color:
		print(i)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100**4)

class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	for i in range(n):
		if colors[i] != -1:
			continue
		dfs(i, g, colors)
	for c in colors:
		print(c)
resolve()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    a_tmp = a[:]
    a_tmp[i] = 0
    print(max(a_tmp))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
maxvalue = max(a)
maxindex = a.index(max(a))
for i in range(n):
    if i != maxindex:
        print(maxvalue)
    else:
        a_tmp = a[:]
        a_tmp.pop(maxindex) 
        print(max(a_tmp))
### BUGGY CODE ###

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

dp = [0] * (K + 1)
dp[0] = 1

for i, a in enumerate(A, start=1):
    accDp = [0] * (K + 2)
    for k in range(1, K + 2):
        accDp[k] = accDp[k - 1] + dp[k - 1]

    for k in range(K + 1):
        dp[k] += accDp[k] - accDp[max(0, k - a)]

print(dp[K] % MOD)


### FIXED CODE ###

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

dp = [[0] * (K + 1) for _ in range(N + 1)]  # dp[child][candy] 残りcandy個の場合の数
dp[0][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)
### BUGGY CODE ###

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

A = list(map(int, input().split()))
"""
if N == 1:
    if A[0] % M == 0:
        print(1)
        exit()
"""

ans = 0
cum = [0] * N
cum[0] = A[0]
if cum[0] % M == 0:
    ans += 1

for i in range(1,N):
    cum[i] = cum[i-1] + A[i]
    if cum[i] % M == 0:
        ans += 1

for l in range(N-1): 
    for r in range(l+1,N):
        #print(l,r)
        if (cum[r] - cum[l]) % M == 0:
             ans += 1

            

print(ans)


### FIXED CODE ###

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

A = list(map(int, input().split()))
"""
if N == 1:
    if A[0] % M == 0:
        print(1)
        exit()
"""

ans = 0
cum = [0] * N
cum[0] = A[0]

from collections import defaultdict
d = defaultdict(int)

d[cum[0] % M] += 1
for i in range(1,N):
    cum[i] = cum[i-1] + A[i]
    d[cum[i] % M] += 1


from operator import mul
from functools import reduce

def cmb(n,r):
    if n < r:
        return 0
    r = min(n-r,r)
    if r == 0: return 1
    # reduceは第一引数で与えた関数を第二引数のiterbleのそれぞれで実行した結果をもどす
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ans = 0
d[0] += 1
for i in d.keys():
    #print(i,d[i])
    ans += cmb(d[i], 2)           

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

n = int(input())
s = [input() for _ in range(n)]
lists = sorted(list(set(s)))
num = list()
for i in lists:
    cnt = 0
    for j in s:
        if i == j:
            cnt += 1
    num.append(cnt)
maxnum = max(num)
for j in range(len(lists)):
    if num[j] == maxnum:
        print(lists[j])

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
ss = sorted(s)
t = ss
x = 0
maxx = 0
for i in range(n-1):
    if ss[i] == ss[i+1]:
        x += 1
        if x == maxx:
            maxx = x
            t.append(ss[i])
        elif x > maxx:
            maxx = x
            t = [ss[i]]
    else:
        x = 0
for j in t:
    print(j)
### BUGGY CODE ###

N,Q = map(int, input().split())
abL = [[int(x) for x in input().split()] for _ in range(N-1)]
tree = [[0]*(N+1) for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for a,b in abL:
    graph[a].append(b)
 
for a in range(N, 0, -1):
    incL = graph[a]
    for b in incL:
        for i in range(a):
            if a in graph[i]:
                graph[i].append(b)
    graph[a].append(a)
 
pxL = [[int(x) for x in input().split()] for _ in range(Q)]
 
for p,x in pxL:
    tmpL = graph[p]
    for b in tmpL:
        tree[p][b] += x
 
for i in range(1, N+1):
    sum_ = 0
    for j in range(1, N+1):
        sum_ += tree[j][i]
    print(sum_, end=" ")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

N,Q = map(int, input().split())
graph = [[] for _ in range(N)]
counter = [0]*N
for i in range(N-1):
    a,b = map(int, input().split()) 
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

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

def dfs(v, parent):
    for i in graph[v]:
        if i==parent:
            continue
        counter[i] += counter[v]
        dfs(i, v)
        
dfs(0, -1)
print(*counter)
### BUGGY CODE ###

#計算量的にはきつそうだけど，dp[i][j]でやる？

s=input()
t=input()

ls=len(s)
lt=len(t)

add=ls-lt
if add>0:
    t+="T"*add
else:
    s+="S"*(-1*add)
N=len(s)
    
    
#sのi文字目とtのj文字目までで取れる最長部分列
dp=[[""]*(N+1) for _ in range(N+1)]

temp=["",""]

for i in range(N):
    for j in range(N):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
            L=len(dp[i+1][j+1])
        else:
            temp[0]=dp[i+1][j]
            temp[1]=dp[i][j+1]
            if len(temp[0])>len(temp[1]):
                dp[i+1][j+1]=temp[0]
            else:
                dp[i+1][j+1]=temp[1]

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

### FIXED CODE ###

#ひとまず長さだけ持つ，後から表を後ろ向きに見て復元を試みる

s=input()
t=input()

ls=len(s)
lt=len(t)
    
    
#sのi文字目とtのj文字目までで取れる最長部分列の長さ
dp=[[0]*(lt+1) for _ in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

ans=""
i=ls
j=lt
while(i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        i-=1
        j-=1
        ans+=s[i]
        


print(ans[::-1])
### BUGGY CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
new_a_plus = [a[i] for i in range(n)]
new_a_minus = [a[i] for i in range(n)]

count_plus = 0
if a[0] <= 0:
    new_a_plus[0] = 1
    count_plus += 1 - a[0]

for i in range(1, n):
    if i % 2 == 0:
        if sum(new_a_plus[:i+1]) <= 0:
            new_a_plus[i] = -sum(new_a_plus[:i])+1
            count_plus += new_a_plus[i] - a[i]
    else:
        if sum(new_a_plus[:i+1]) >= 0:
            new_a_plus[i] = -sum(new_a_plus[:i])-1
            count_plus += a[i] - new_a_plus[i]

count_minus = 0
if a[0] >= 0:
    new_a_minus[0] = -1
    count_minus += a[0] + 1

for i in range(1, n):
    if i % 2 == 0:
        if sum(new_a_minus[:i+1]) >= 0:
            new_a_minus[i] = -sum(new_a_minus[:i])-1
            count_minus += a[i] - new_a_minus[i]
    else:
        if sum(new_a_minus[:i+1]) <= 0:
            new_a_minus[i] = -sum(new_a_minus[:i])+1
            count_minus += new_a_minus[i] - a[i]

print(min(count_plus, count_minus))

### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
new_a_plus = [a[i] for i in range(n)]
new_a_minus = [a[i] for i in range(n)]

count_plus = 0
now_total_plus = 0

for i in range(0, n):
    if i % 2 == 0:
        if now_total_plus + a[i] <= 0:
            new_a_plus[i] = - now_total_plus + 1
            count_plus += new_a_plus[i] - a[i]
    else:
        if now_total_plus + a[i] >= 0:
            new_a_plus[i] = - now_total_plus - 1
            count_plus += a[i] - new_a_plus[i]
    now_total_plus += new_a_plus[i]

count_minus = 0
now_total_minus = 0

for i in range(0, n):
    if i % 2 == 0:
        if now_total_minus + a[i] >= 0:
            new_a_minus[i] = - now_total_minus - 1
            count_minus += a[i] - new_a_minus[i]
    else:
        if now_total_minus + a[i] <= 0:
            new_a_minus[i] = - now_total_minus + 1
            count_minus += new_a_minus[i] - a[i]
    now_total_minus += new_a_minus[i]

print(min(count_plus, count_minus))
### BUGGY CODE ###

N,K,Q=map(int, input().split())
A=[int(input()) for i in range(Q)]
for i in range(N):
  if (Q - A.count(i+1))< K:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q=map(int, input().split())
A=[int(input()) for i in range(Q)]
from collections import Counter
A=Counter(A)
B=list(A.most_common())
#B.sort(key=lambda x:x[0])
C = [0]*N
for i in B:
  C[i[0]-1]=i[1]
for i in range(N):
  if (Q - C[i])< K:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 7+1000000000

amari = 0


for i in range(n):
    for e in range(n-i-1):
        j = i+e+1
        if i != j:
            number = number + (a[i] * a[j])
amari = number % mod
print(amari)



### FIXED CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

all_a = 0

for i in range(n):
    all_a = all_a + a[i]

for i in range(n):
    all_a = all_a - a[i]
    number = number + (a[i] * all_a)
    number = number % mod
amari = number % mod
print(amari)
### BUGGY CODE ###

n = int(input())

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

ans = 1
if 0 in l:
  print(0)
else:
  for i in l:
    ans *= i
  if ans >= 1000000000000000001:
    print(-1)
  else:
    print(ans)

### FIXED CODE ###

import sys
n = int(input())

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

ans = 1
if 0 in l:
  print(0)
  sys.exit()

for i in l:
  ans *= i
  if ans > 10 ** 18:
    print(-1)
    sys.exit()
print(ans)
### BUGGY CODE ###

import sys
from fractions import gcd
import bisect

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
s = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]



n, m = na()
a = na()
a.sort()

for i in range(m):
    b, c = na()
    for j in range(b):
        a.append(c)
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

import sys
import math
import numpy as np
import bisect
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
a = na()
bc = []

for _ in range(m):
    bci = na()
    bc.append(bci)

bc.sort(key=lambda x:x[1], reverse=True)
#print(bc)

bi, ci = bc[0][0], bc[0][1]
i = 0
for _ in range(n):
    if bi != 0:
        bi -= 1
        a.append(ci)
    else:
        i += 1
        if i > (m - 1):
            break
        else:
            bi, ci = bc[i][0], bc[i][1]
            bi -= 1
            a.append(ci)

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

from collections import Counter

num = int(input())

# tmp = []
# for n in range(num):
#   tmp.append(input())

tmp = [input() for i in range(num)]

count = Counter(tmp)

tmp2 = []
for k, v in count.items():
  if count.most_common(1)[0][1] == v:
    tmp2.append(k)

for t in sorted(tmp2):
  print(t)

### FIXED CODE ###

def main():
  num = int(input())

  tmp = [input() for i in range(num)]

  tmp2 = {}
  for t in tmp:
    if len(tmp2) == 0:
      tmp2[t] = 1
    else:
      if t in tmp2:
        tmp2[t] += 1
      else:
        tmp2[t] = 1

  _tmp2 = sorted(tmp2.items(), key=lambda x:x[1])
  tmp3 = sorted(tmp2.items())
  for t in tmp3:
    if _tmp2[-1][1] == t[1]:
      print(t[0])

main()
### BUGGY CODE ###

k, n = map(int, input().split())
 
An = list(map(int, input().split()))
 
mn = 0
Amax = max(An)
Amin = min(An)
for i in range(len(An)):
    cal = 0
    A = An[i:]  + An[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
        
        if mn > 0 and cal > mn:
            break
    
    if mn ==0 or mn > cal:
        mn = cal
        
rAn = An[:]
rAn.reverse()
for i in range(len(rAn)):
    cal = 0
    A = rAn[i:]  + rAn[:i]
    for i in range(len(A)-1):
        if A[i] == Amax and A[i+1] == Amin:
            cal += A[i+1] + k - A[i]
        elif A[i] == Amin and A[i+1] == Amax:
            cal += A[i] + k - A[i+1]
        elif A[i+1] >= A[i]:
            cal += A[i+1] - A[i]
        else:
            cal += A[i] - A[i+1]
            
        if mn > 0 and cal > mn:
            break
 
    if mn ==0 or mn > cal:
        mn = cal
print(mn)

### FIXED CODE ###

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

N,K,*A = map(int, open(0).read().split())

for _ in range(K):
    X = [1] * N
    for i, d in enumerate(A):
        for j in range(max(0, i-d), i):
            X[j] += 1
        for j in range(i+1, min(N, i+d+1)):
            X[j] += 1
    if X == A:
        break
    A = X

print(" ".join(map(str, A)))


### FIXED CODE ###

N,K,*A = map(int, open(0).read().split())
                                         
for _ in range(K):                       
    b = [0] * N                          
    for i, d in enumerate(A):            
        b[max(0, i-d)] += 1              
        if i+d+1 < N:                    
            b[i+d+1] -= 1                
    for i in range(1, N):                
        b[i] += b[i-1]                   
    if A == b:                           
        break                            
    A = b                                
                                         
print(" ".join(map(str, A)))
### BUGGY CODE ###

N,K=map(int, input().split())
A = list(map(int, input().split()))
S=[]
for i in range(N-K+1):
    S += [(sum(A[i:i+K])+K)/2]
print(max(S))

### FIXED CODE ###

def main():
    N,K=map(int, input().split())
    A = list(map(int, input().split()))
    S = (sum(A[0:K])+K)/2
    S_max=S
    for i in range(K,N):
        S +=  A[i]/2
        S -= A[i-K]/2
        if S_max<S:
            S_max=S
    print(S_max)

main()
### BUGGY CODE ###

import sys
N = int(input())
list = list(map(int, input().split()))
  
for i in range(N):
  for j in range(N):
    if i==j:
      continue
    if list[i] == list[j]:
      print("NO")
      sys.exit()
print("YES")

### FIXED CODE ###

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



if ((len(list)) == (len(set(list)))) == True:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

N, K = map(int, input().split())
p_list = list(map(int, input().split()))
EV_p_list = [0] * len(p_list)

EV_list = [0] * 1000

for i in range(len(EV_list)):
  EV_list[i] = (i + 2) / 2

for i in range(len(p_list)):
  index = p_list[i]
  EV_p_list[i] = EV_list[index - 1]

max_EV = 0
for i in range(N - K + 1):
  tmp = 0
  for j in range(K):
    tmp += EV_p_list[i + j]
  
  if tmp >= max_EV:
    max_EV = tmp

print(max_EV)

### FIXED CODE ###

N, K = map(int, input().split())
p_list = list(map(int, input().split()))
EV_p_list = [0] * len(p_list)

for i in range(len(p_list)):
  EV_p_list[i] = (p_list[i] + 1) / 2

# 最初のsum
sum_EV = 0
for i in range(K):
  sum_EV = sum_EV + EV_p_list[i]

# それ以降の比較
max_EV = sum_EV
for i in range(1, N - K + 1):
  sum_EV = sum_EV - EV_p_list[i - 1] + EV_p_list[i + K - 1]
  if sum_EV > max_EV:
    max_EV = sum_EV

print(max_EV)
### BUGGY CODE ###

import bisect

N = int(input())
L = [int(x) for x in input().split()]
L.sort()
ret = 0
# print(L)
for i in range(N-2):
    for j in range(i+1, N-1):
        add = bisect.bisect_left(L,L[i]+L[j]-0.01) - (j+1)
        # print(f"{L[i]}, {L[j]} , add:{add}")
        ret += add

print(ret)



### FIXED CODE ###

import bisect

N = int(input())
L = [int(x) for x in input().split()]
L.sort()
ret = 0
# print(L)
for i in range(N-2):
    for j in range(i+1, N-1):
        add = bisect.bisect_left(L,L[i]+L[j]-0.01) - (j+1)
        # print(f"{L[i]}, {L[j]} , add:{add}")
        ret += add

print(ret)
### BUGGY CODE ###

x,y,a,b,c=[int(j) for j in input().split()]
p=[int(j) for j in input().split()]
q=[int(j) for j in input().split()]
r=[int(j) for j in input().split()]

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
l=p[:x]+q[:y]
l.sort()
ans=0
for i in l:
    if r!=[]:
        if i<r[0]:
            ans+=r[0]
            del r[0]
        else:
            ans+=i
    else:
        ans+=i
print(ans)

### FIXED CODE ###

x,y,a,b,c=[int(j) for j in input().split()]
p=[int(j) for j in input().split()]
q=[int(j) for j in input().split()]
r=[int(j) for j in input().split()]
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

p=p[:x]
q=q[:y]
l=p+q
l.sort()
ans=sum(l)
for i in l:
    if i<r[0]:
        ans+=r[0]-i
        del r[0]
        if r==[]:
            break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


N, Q = map(int, input().split())
AB = {i: [] for i in range(N)}
for _ in range(N - 1):
    a, b = map(int, input().split())
    AB[a - 1].append(b - 1)

X = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    X[p - 1] += x


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


recursive(0)
print(" ".join(map(str, X)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)


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

X = [0] * (N + 1)
for _ in range(Q):
    p, x = map(int, input().split())
    X[p] += x


def recursive(p):
    for c in AB[p]:
        X[c] += X[p]
        recursive(c)


recursive(1)
print(" ".join(map(str, X[1:])))
### BUGGY CODE ###

# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない
K = int(input())

count =1
x=7

if K %2 ==0 or K %5 ==0:
    count = -1
else:
    while x %K !=0:
        count +=1
        x = x*10 +7
        #print(x,end =" ")
print(count)

### FIXED CODE ###

# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない
K = int(input())

count =1
x=7 %K

if K %2 ==0 or K %5 ==0:
    count = -1
else:

    while x %K !=0:
        count +=1
        x = (x*10 +7)%K
        #print(x,end =" ")
print(count)
### BUGGY CODE ###

n = int(input())

d = set([])
for _ in range(n):
    d = d ^ set([int(input())])
    
print(len(d))

### FIXED CODE ###

n = int(input())

d = set()
for _ in range(n):
    d ^= {input()}
    
print(len(d))
### BUGGY CODE ###

x = int(input())
for i in range(2000):
  for j in range(-1000,1999):
    if i**5 - j**5 == x:
      print(i,j)
      break


### FIXED CODE ###

X = int(input())

AA = 0
BB = 0

for A in range(-121,121):
    for B in range(-121,121):
        if X == (A ** 5) - (B ** 5):
            AA = A
            BB = B

print(AA,BB)
### BUGGY CODE ###

N,M = map(int,input().split())
gcd = M // N
gcd_tmp = 0
while gcd > 0:
 if M % gcd == 0:
  tmp = M - gcd
  if tmp % gcd == 0:
   gcd_tmp = gcd
   break
 gcd = gcd - 1
print(gcd_tmp)

### FIXED CODE ###

def calc():
 N,M = map(int,input().split())
 for gcd in range(M // N,0,-1):
  if M % gcd == 0:
   break
 return(gcd)
print(calc())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math

MOD = 10 ** 9 + 7

def main():
    N = int(input())
    S = input().strip()

    if S[0] == 'W' or S[-1] == 'W':
        print(0)
        return

    Dc = 1
    LRsub = 1
    Pattern = 1
    for i in range(1,2*N):
        Dc = Dc if S[i] != S[i-1] else -Dc
        Pattern *= LRsub if Dc < 0 else 1
        LRsub += Dc

    if LRsub == 0:
        Pattern *= math.factorial(N)
        Pattern = Pattern % MOD
        print(Pattern)
    else:
        print(0)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

MOD = 10 ** 9 + 7

N = int(input())
S = list(map(lambda x: int(x == "W"),input()))
if S[0] or S[-1]:
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
Sp = S[0]

for i in range(1,N*2):
    Sc = S[i]
    Dc = Dc if Sc != Sp else -Dc
    Sp = Sc
    if Dc < 0:
        Pattern = (Pattern * LRsub) % MOD
    LRsub += Dc

if LRsub == 0:
    for i in range(2,N+1):
        Pattern = (Pattern * i) % MOD
    print(Pattern)
else:
    print(0)
### BUGGY CODE ###

n = input().split()
N = int(n[0])
Q = int(n[1])
S = input()

#tmp_list = np.zeros(N)
#ans = []
#for i in range(N-1):
#    if S[i] == 'A' and S[i+1] == 'C':
#        ans.append(int(i))

for i in range(Q):
    lr = input().split()
    tmp = S[int(lr[0])-1:int(lr[1])]
    tmp.replace("G", "").replace("T", "")
    count = tmp.count('AC')
    print(str(count))

### FIXED CODE ###

from itertools import accumulate

N, Q = list(map(int, input().split()))
S = input()
A = [list(map(int, input().split())) for i in range(Q)]

tmp = []
for i in range(N-1):
    tmp_S  = S[i:i+2]
    if tmp_S == 'AC':
        tmp.append(1)
    else:
        tmp.append(0)

tmp2 = [0] + tmp
tmp2 = list(accumulate(tmp2))
#print(tmp2)

for j in A:
    print(tmp2[j[1]-1] - tmp2[j[0]-1])
### BUGGY CODE ###

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

adic = {}

for i in a:
  if i in adic:
    adic[i] += 1
  else:
    adic[i] = 1


for i in range(q):
  b, c = input().split()
  if b in adic:
    if c not in adic:
      adic[c] = 0
    adic[c] += adic.pop(b)
  print( sum(int(j)*int(adic[j]) for j in adic)  )

### FIXED CODE ###

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

asum = sum(a)
adic = {}

for i in a:
  if i in adic:
    adic[i] += 1
  else:
    adic[i] = 1


for i in range(q):
  b, c = map(int, input().split())
  if b in adic:
    if c not in adic:
      adic[c] = 0
    cnt = adic.pop(b)
    adic[c] += cnt
    asum += (c-b) * cnt
  print(asum)
### BUGGY CODE ###

import statistics
N = int(input())
X = list(map(int, input().split()))
B = []
for i in range(N):
    X_sub = X[:i] + X[i+1:]
    B.append(statistics.median(X_sub))
for i in range(N):
    print(B[i])

### FIXED CODE ###

def calculate_median(lst):
    lst.sort()
    median_right = lst[int(len(lst)/2)]
    median_left = lst[int(len(lst)/2)-1]
    return median_right, median_left


N = int(input())
X = list(map(int, input().split()))
X_copy = X.copy()
median_right, median_left = calculate_median(X)
for i in range(N):
    if X_copy[i] >= median_right:
        print(median_left)
    elif X_copy[i] < median_right:
        print(median_right)
### BUGGY CODE ###

N,D,A = map(int,input().split())
enemies = [list(map(int,input().split())) for _ in range(N)]
enemies.sort(key=lambda x:x[0])
ans = 0
for i in range(N):
    if enemies[i][1] > 0:
        bomb = -(-enemies[i][1]//A)
        j = i
        while j < N and enemies[j][0]-enemies[i][0] <= 2*D:
            enemies[j][1] -= A*bomb
            j += 1
        ans += bomb

print(ans)


### FIXED CODE ###

N,D,A = map(int,input().split())
enemies = [list(map(int,input().split())) for _ in range(N)]
enemies.sort(key=lambda x:x[0])
ans = 0
from collections import deque
damage = deque()
dmg = 0
for x,h in enemies:
    if len(damage) == 0:
        bomb = -(-h//A)
        damage.append([x+2*D,bomb])
        dmg += bomb*A
        ans += bomb
    else:
        while len(damage) > 0:
            d,bomb = damage.popleft()
            if x > d:
                dmg -= bomb*A
            else:
                damage.appendleft([d,bomb])
                break
        if h > dmg:
            bomb = -(-(h-dmg)//A)
            dmg += bomb*A
            damage.append([x+2*D,bomb])
            ans += bomb

print(ans)