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

n, nQueries = map(int,input().split())
inString = input()
queries = [ [int(x)-1 for x in input().split()] for i in range(nQueries)]

for (i,j) in queries:
    count = 0
    while(i < j):
        if(inString[i] == "A" and inString[i+1] == "C"):
            i+=2
            count+=1
        else:
            i+=1
        
    print(count)
            


### FIXED CODE ###

n, nQueries = map(int,input().split())
inString = input()
queries = [ [int(x)-1 for x in input().split()] for i in range(nQueries)]
occurance_list = [0]*n
idx = 0
while(idx < n):
    if(idx<n-1 and inString[idx] == "A" and inString[idx+1] == "C"):
        occurance_list[idx] = occurance_list[idx-1]
        occurance_list[idx+1] += occurance_list[idx-1] + 1
        idx += 2
    else:
        occurance_list[idx] = occurance_list[idx-1]
        idx+=1



for (i,j) in queries:
    print(occurance_list[j] - occurance_list[i])
### BUGGY CODE ###

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

now = 1
pre = 0
for i in range(0,n[1]):
    now *= a[i]

for i in range(n[1],n[0]):
    pre = now
    now /= a[i-n[1]]
    now *= a[i]

    if now > pre:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

for i in range(n[1],n[0]):
    if a[i-n[1]] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
import itertools
ans = 0
for i in itertools.combinations(a, 2):
    ans += i[0]*i[1]
    ans%=10**9+7
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
gou = sum(a)
ans = 0
for i in range(n):
    gou-=a[i]
    ans+=a[i]*(gou)
ans%=10**9+7
print(ans)
### BUGGY CODE ###

import functools
import operator

def nCr(n, r):
    if n < r:
        return 0
    r = min(r, n-r)
    if r == 0:
        return 1
    num = functools.reduce(lambda x, y: x*y%mod, range(n, n-r, -1))
    den = functools.reduce(lambda x, y: x*y%mod, map(lambda x: pow(x, mod-2, mod), range(1, r+1)))
    return num * den % mod

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

mod = 10**9 + 7
for i in range(1, k+1):
    print(nCr(k-1, i-1) * nCr(n-k+1, i) % mod)

### FIXED CODE ###

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
	numer = reduce(mul, range(n, n-r, -1))
	denom = reduce(mul, range(1, r+1))
	return numer // denom % mod

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

for i in range(1, K+1):
	print(cmb(K-1, i-1) * cmb(N-K+1, i) % mod)
### BUGGY CODE ###

N = int(input())
A = input().split()
C = {}

def func01(S,key,C):

    sum_count = 0
    B = set(S)

    if len(B) == N:
        sum_count = 0
    else:
        for s in B:
            count_s = S.count(s)
            sum_count += (count_s * (count_s - 1) // 2)
        C.update({key: sum_count})
    return(sum_count)

for i in range(N):
#すでに計算済みの数字ならば計算結果を参照
#計算未ならば 計算して 計算結果を追加

    if A[i] in C.keys():
        sum_count = C.get(A[i])
    else:
        X = A[0:i] + A[i + 1:N]
        sum_count = func01(X, A[i], C)
    print(sum_count)


### FIXED CODE ###

import collections

N = int(input())
A = input().split()

#A_set = set(A)

#ボールに書かれている 数字の内訳を辞書に登録
A_dic = collections.Counter(A)

#すべてのボールから同じボールを取り出す方法数
all_count = 0

for a in A_dic.keys():
    count_a = A_dic.get(a)
    all_count += (count_a * (count_a - 1) // 2)

#n個あるボールから 1個取り除いた場合の方法数
#すべてのボールから取り出す方法数 - (n-1)通り

for i in range(N):
    print(all_count - A_dic.get(A[i])+1)
### BUGGY CODE ###

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

for i in range(N-2):
	for j in range(i+1, N-1):
		M = L[j+1::]
		k = 0
		while k<len(M) and M[k]>(L[i]-L[j]):
			k += 1
			C += 1
				
print(C)


### FIXED CODE ###

from bisect import bisect
from bisect import bisect_left

_ = input()
l = input()
l = sorted(list(map(int, l.split())))
count = 0

for i in range(len(l)):
	for j in range(i+1, len(l)):
		c = l[i]+l[j]
		count += bisect_left(l,c) - (j+1)

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

N = int(input())
ss = []
for i in range(N):
    s = list(input())
    s.sort()
    ss.append(s)

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        if ss[i] == ss[j]:
            ans += 1

print(ans)


### FIXED CODE ###

N = int(input())
ss = []
for i in range(N):
    s = list(input())
    s.sort()
    ss.append(s)

ss.sort()
ans = 0
tmp = 1
for i in range(N-1):
    if ss[i] == ss[i+1]:
        tmp += 1
        if i == N-2:
            ans += (tmp * (tmp-1)) // 2
    else:
        ans += (tmp * (tmp-1)) // 2
        tmp = 1

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

from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
    G0[(i,c)].add((i,-1))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G0[(a,c)]:
      if not visited[(a,c)]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[(a,c)]:
        stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))


      
    

### FIXED CODE ###

from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))
### BUGGY CODE ###

#dp[i+1][j+1]:=Sのi文字目までとTのj文字目までのLCSの長さ
def main():
    S=input()
    T=input()
    ls=len(S)
    lt=len(T)

    dp=[["" for j in range(lt+1)] for i in range(ls+1)]

    for i in range(ls):
        for j in range(lt):
            if S[i]==T[j]: 
                dp[i+1][j+1]=max(dp[i][j]+S[i],dp[i+1][j],dp[i][j+1],key=len)
            else:
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1],key=len)
    print(dp[ls][lt])

main()

### FIXED CODE ###

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


dp = [[0 for i in range(lt+1)] for j in range(ls+1)]
answer = ''

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][j+1], dp[i+1][j])


i = ls-1
j = lt-1
while (0 <= i) & (0 <= j):
    if s[i] == t[j]:
        answer += s[i]
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
    else:
        i -= 1
if len(answer) == 0:
  print('')
else:
  print(answer[::-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1

C = [input() for i in range(H)]
dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        dist[xx][yy] = dist[x][y] + 1
        d.append([xx, yy])
      else:
        break

print(dist[x2][y2])

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

S = list(input())
Q = int(input())
L = [input().split() for _ in range(Q)]

count = 0 # ['1']の数
for i in range(len(L)):
    if L[i][0] == '1':
        count += 1
    if L[i][0] == '2':
        if (count % 2) == 0:
            if L[i][1] == '1':
                S = [L[i][2]] + S
            else:
                S = S + [L[i][2]]
        else:
            if L[i][1] == '2':
                S = [L[i][2]] + S
            else:
                S = S + [L[i][2]]



# print(L)
if (count % 2) == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))

### FIXED CODE ###

s = input()
q = int(input())
query = []
lead = ''
end = ''
inversion_flg = False
 
for j in range(q):
    i = input().split()
    if i[0] == "1":
        if inversion_flg:
            inversion_flg = False 
        else:
            inversion_flg = True
    else:
        if inversion_flg:
            if i[1] == "1":
                i[1] = "2"
            else:
                i[1] = "1"
        if i[1] == "1":
            lead+=i[2]
        else:
            end+=i[2]
 
lead = lead[::-1]
s = lead+s+end
if inversion_flg:
    s = s[::-1]
print(s)
### BUGGY CODE ###

S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
follow = 0
for i in range(N):
  Amari_ = (int(S[N-i-1]) * pow(10, i) + follow) % 2019
  ans += amari[Amari_]
  amari[Amari_] += 1
  follow = Amari_
ans += amari[0]

print(ans)

### FIXED CODE ###

S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
amari[0] = 1
follow = 0
POW = 1

for i in reversed(S):
  follow += int(i) * POW
  follow %= 2019
  amari[follow] += 1
  POW *= 10
  POW %= 2019
  
print(sum( i * (i-1) // 2 for i in amari ))
### BUGGY CODE ###

H, W = list(map(int, input().split(' ')))
xs = []
for i in range(H):
    xs.append(list(map(int, input().split(' '))))
# best でなくても良い？
ans = []  # x,y -> p, q
seeds = []
for i in range(H):  # 500
    for j in range(W):  # 500
        if xs[i][j] % 2 != 0:
            seeds.append((i, j))
used = {}
def f(st, ed):
    res = []
    while(st != ed):
        while(st[0] > ed[0]):
            if (st[0]-1, st[1]) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1-1, st[1]+1))
            st = (st[0]-1, st[1])
            used[st] = True
        while(st[0] < ed[0]):
            if (st[0]+1, st[1]) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1+1, st[1]+1))
            st = (st[0]+1, st[1])
            used[st] = True
        while(st[1] > ed[1]):
            if (st[0], st[1]-1) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1, st[1]+1-1))
            st = (st[0], st[1]-1)
            used[st] = True
        while(st[1] < ed[1]):
            if (st[0], st[1]+1) in used:
                break
            res.append('%d %d %d %d' % (st[0]+1, st[1]+1, st[0]+1, st[1]+1+1))
            st = (st[0], st[1]+1)
            used[st] = True
    return res

ans = []
# print (seeds)
seeds = sorted(seeds, key=lambda x:(x[0] * 9999999 + x[1] * (-1 if x[0]%2 == 1 else 1)))
# print (seeds)
for i in range(0, len(seeds)-1, 2):
    st = seeds[i]
    ed = seeds[i+1]
    ans += f(st, ed)
print(len(ans))
print('\n'.join(ans))


### FIXED CODE ###

H, W = list(map(int, input().split(' ')))
xs = []
for i in range(H):
    xs.append(list(map(int, input().split(' '))))
# best でなくても良い？
ans = []  # x,y -> p, q
seeds = []
for i in range(H):  # 500
    for j in range(W):  # 500
        if xs[i][j] % 2 != 0:
            seeds.append((i, j))
used = {}
def f(st, ed):
    res = []
    while(st != ed):
        old = st
        if (st[0] % 2 == 0):
            if st[1] < W - 1:
                st = (st[0], st[1] + 1)
            else:
                st = (st[0]+1, st[1])
        else:
            if st[1] > 0:
                st = (st[0], st[1] - 1)
            else:
                st = (st[0]+1, st[1])
        res.append('%d %d %d %d' % (old[0]+1, old[1]+1, st[0]+1, st[1]+1))
    return res

ans = []
# print (seeds)
seeds = sorted(seeds, key=lambda x:(x[0] * 9999999 + x[1] * (-1 if x[0]%2 == 1 else 1)))
# print (seeds)
for i in range(0, len(seeds)-1, 2):
    st = seeds[i]
    ed = seeds[i+1]
    ans += f(st, ed)
print(len(ans))
print('\n'.join(ans))
### BUGGY CODE ###

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

A = [int(input()) for _ in range(M)]

@lru_cache(100000)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    s = 0
    if (pos + 1) not in A:
        s += dfs(pos + 1)
    if (pos + 2) not in A:
        s += dfs(pos + 2)
    return s

print(dfs(0) % 1000000007)


### FIXED CODE ###

from functools import lru_cache

import sys
sys.setrecursionlimit(1000000)

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

A = set(int(input()) for _ in range(M))

@lru_cache(None)
def dfs(pos):
    if pos > N:
        return 0
    if pos == N:
        return 1
    if pos in A:
        return 0
    return dfs(pos + 2) + dfs(pos + 1)

for i in reversed(range(N+1)):
    dfs(i)

print(dfs(0) % 1000000007)
### BUGGY CODE ###

from collections import deque
# from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

road = [[] for i in range(n)]
cnt  = [0 for i in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.popleft()
    for i,r in enumerate(road[v]):
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        que.append(r)

for i in range(q):
    idx,v = map(int,input().split())
    for j in range(n):
        if j == idx-1:
            cnt[j] += v
        if dist[j] > dist[idx-1]:
            cnt[j] += v

print(*cnt)

### FIXED CODE ###

from collections import deque
# from collections import Counter
# from itertools import accumulate
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

# input = sys.stdin.readline
# def main():

#---------------------------------------------------------

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

road = [[] for _ in range(n)]
cnt  = [0 for _ in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)

for i in range(q):
    idx,v = map(int,input().split())
    cnt[idx-1] += v

dist = [-1]*n
que  = deque()
dist[0] = 0
que.append(0)

while(len(que)!=0):
    # BFS/DFS
    v = que.pop()
    for r in road[v]:
        if dist[r]!=-1:
            continue
        dist[r] = dist[v] + 1
        cnt[r] += cnt[v]
        que.append(r)

print(*cnt)
### BUGGY CODE ###

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

for i in range(N):
    X=X_raw[:]
    X.pop(i)
    X.sort()
    print(X[int(N/2-1)])




### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
sX=sorted(X)
for i in X:
    if i<=sX[int(N/2-1)]:
        print(sX[int(N/2)])
    else:
        print(sX[int(N/2-1)])
### BUGGY CODE ###

n = int(input())
x = [int(i) for i in input().split()]

for i in range(n):
    print(sorted((x[:i] + x[i+1:]))[(n-1)//2])

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]

sorted_x = sorted(x)
smaller = sorted_x[n//2 - 1]
bigger = sorted_x[n//2]

for i in range(n):
    print(bigger if x[i] <= smaller else smaller)
### BUGGY CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


def list_gcd(a):
    a_gcd = a[0]
    for i in range(n-1):
        a_gcd = gcd(a_gcd, a[i+1])
    return a_gcd


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

ans = 0

for i in range(n):
    b = a[:]
    b[i] = b[i-1]
    ans = max(ans, list_gcd(b))

print(ans)

### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)


n = int(input())
a = list(map(int, input().split()))
a = [0]+a[:]+[0]

l = [0]*len(a)
r = [0]*len(a)

for i in range(len(a)-1):
    m = len(a)-1
    l[i+1] = gcd(l[i], a[i+1])
    r[m-i-1] = gcd(r[m-i], a[m-i-1])

ans = [0]*n

for i in range(n):
    ans[i] = gcd(l[i], r[i+2])

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

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

l=list()
c=2
while m>1:
  if m%c==0:
    l.append(c)
    m = m//c
  else:
    c+=1

e=[[x,l.count(x)] for x in set(l)]    

l2=[1]
for i in range(len(e)):
  for j in range(len(l2)):
    for k in range(e[i][1]):
      l2.append(l2[j]*e[i][0]**(k+1))

l2.sort()
m=1
for i in range(len(l2)):
  if a//n>=l2[i]:
    m=max(l2[i],m)

print(m)


### FIXED CODE ###

n,m=map(int,input().split())

d=list()
for i in range(1,int(m**0.5)+1):
  if m%i==0:
    d.append(i)
    if i!=m//i:
      d.append(m//i)

d.sort()

c=1
for i in range(len(d)):
  if m//d[i]>=n:
    c=max(d[i],c)

print(c)
### BUGGY CODE ###

K , S = map(int, input().split())
x , y , z , cnt = 0 , 0 , 0 , 0
if K * 3 == S:
    cnt = 1
else :
    for i in range(K + 1):
        x = i
        if x + y + z == S :
            cnt += 1
        for j in range(K + 1):
            y = j
            if x + y + z == S :
                cnt += 1
            for k2 in range(K + 1) :
                z = k2
                if x + y + z == S:
                    cnt += 1

print(cnt)


### FIXED CODE ###

K , S = map(int, input().split())
x , y , z , cnt = 0 , 0 , 0 , 0
A = K + 1
if K * 3 == S:
    cnt = 1
else :
    for i in range(A):
        for j in range(A):
            if  S - (i + j) <= K :
                if 0 <= S - (i + j): 
                    cnt += 1
print(cnt)
### BUGGY CODE ###

import time

n=int(input())
x=(n%15)*0.001*100
a=0.037
#time.sleep(x+a)
ls=[1 for i in range((n%100)*10**6)]
print('Yes')

### FIXED CODE ###

x=int(input())
s=str(x)
keta=0
for i in s:
  keta+=int(i)
if x%keta==0:
  ans='Yes'
else:
  ans='No'
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = map(int, input().split())


d = [-1]*(N+1)


def dfs(v, c):
    d[v] = c
    for nv, cost in G[v]:
        if d[nv] == -1:
            dfs(nv, cost+c)

dfs(K, 0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(d[x]+d[y])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    G[a].append((b, c))
    G[b].append((a, c))
Q, K = map(int, input().split())


d = [-1]*(N+1)


def dfs(v, c):
    d[v] = c
    for nv, cost in G[v]:
        if d[nv] == -1:
            dfs(nv, cost+c)

dfs(K, 0)

for _ in range(Q):
    x, y = map(int, input().split())
    print(d[x]+d[y])
### BUGGY CODE ###

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

dp = [0] * (n)
dp[0] = 0
dp[1] = abs(h[1] - h[0])
for i in range(2,n):
    minp = dp[i-1] + abs(h[i]-h[i-1])
    x = max(i-k, 0)
    dp[i] = min([d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i])])

print(dp[n-1])


### FIXED CODE ###

import sys
import numpy as np
n,k = map(int,input().split())
h = np.array(list(map(int,sys.stdin.readline().split())))

dp = np.zeros(n, dtype=int)
dp[0] = 0
for i in range(1,n):
    x = max(i-k, 0)
    #dp[i] = min(d + abs(h[i]-hd) for d, hd in zip(dp[x:i], h[x:i]))
    dp[i] = (dp[x:i] + abs(h[i] - h[x:i])).min()
print(dp[-1])
### BUGGY CODE ###

n = int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1 * j
    
    return table

a = sum(num_divisors_table(n))
print(a)

### FIXED CODE ###

n = int(input())
def div(n):
    a = 0
    for i in range(1, n+1):
        y = int(n/i)
        a += y* (y+1)*i/2
    return int(a)
print(div(n))
### BUGGY CODE ###

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

n = int(input())
nums = list(map(int, input().split()))
x = 10 ** 9 + 7

ans = 0

for i in range(n):
    for j in range(i + 1, n):
        item = (nums[i] % x) * (nums[j] % x)
        item = item % x
        ans += item
        ans = ans % x

print(ans)


### FIXED CODE ###

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

n = int(input())
nums = list(map(int, input().split()))
x = 10 ** 9 + 7

ans = 0

sums = [0] * (n - 1)

for j in range(n - 1):
    if j == 0:
        sums[0] = nums[0] % x
    else:
        sums[j] = (sums[j - 1] + nums[j]) % x

for i in range(1, len(nums)):
    ans += sums[i - 1] * nums[i]
    ans = ans % x

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

from itertools import combinations
n = int(input())
aList = list(map(int, input().split()))
comb = combinations(aList, 2)
ansSum = 0
for i in list(comb):
    ansSum += i[0]*i[1]
print(ansSum%(7+10**9))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
array_sum_square = sum(A)**2
individual_square_sum = 0
for i in range(0, n, 1):
    individual_square_sum += A[i]**2
print((array_sum_square - individual_square_sum) // 2 % (7 + 10 ** 9))
### BUGGY CODE ###

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


MOD = 10 ** 9 + 7

def main():
    input = sys.stdin.readline
    N = int(input())
    S = input()
    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
        if Dc < 0:
           Pattern *= LRsub
        LRsub += Dc

    if LRsub == 0:
        for i in range(2,N+1):
            Pattern *= i
            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)