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

from collections import defaultdict
H, W, D = map(int, input().split())
A = [None] * H
B = {}
for i in range(H):
    A[i] = [int(x) for x in input().split()]
    for j, Aij in enumerate(A[i]):
        B[Aij] = (i, j)
costs = defaultdict(list)
for n in range(1, W * H + 1):
    m = n
    costs[n].append(0)
    while m + D < H * W + 1:
        x1, y1 = B[m]
        m += D
        x2, y2 = B[m]
        costs[n].append(abs(x1 - x2) + abs(y1 - y2) + costs[n][-1])

Q = int(input())
for i in range(Q):
    Li, Ri = map(int, input().split())
    n_move = (Ri - Li) // D
    print(costs[Li][n_move])

### FIXED CODE ###

from collections import defaultdict
H, W, D = map(int, input().split())
B = {}
for i in range(H):
    Ai = [int(x) for x in input().split()]
    for j, Aij in enumerate(Ai):
        B[Aij] = (i, j)
costs = defaultdict(list)

costs = [0] * (H * W + 1)
for i in range(D + 1, W * H + 1):
    x1, y1 = B[i - D]
    x2, y2 = B[i]
    costs[i] = costs[i - D] + abs(x1 - x2) + abs(y1 - y2)

Q = int(input())
for i in range(Q):
    Li, Ri = map(int, input().split())
    print(costs[Ri] - costs[Li])
### BUGGY CODE ###

n,k = map(lambda x: int(x),input().split())
p = list(map(lambda x: int(x),input().split()))
max = 0
max_list = []

for i in range(n-k+1):
    if max < sum(p[i:i+k]) :
        max = sum(p[i:i+k])
        max_list = p[i:i+k]

e = sum(list(map(lambda x: (1+x)/2,max_list)))
print(e)

### FIXED CODE ###

n,k = map(lambda x: int(x),input().split())
p = list(map(lambda x: (int(x) + 1)/2,input().split()))
ruiseki = [0]
max = 0
for i in range(n) :
    ruiseki.append(ruiseki[i]+p[i])

for j in range(n - k + 1):
    if max < (ruiseki[j+k] - ruiseki[j]) :
        max = (ruiseki[j+k] - ruiseki[j])


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

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


#A
"""
def check(n):
    n = list(map(int,list(str(n))))
    s = 0
    for i in n:
        s += f[i]
    return s == 0
n,k = LI()
d = LI()
f = [0 for i in range(10)]
for i in d:
    f[i] = 1
while 1:
    if check(n):
        print(n)
        quit()
    n += 1
"""
#B
def f(x,y):
    return fact[x-1+h-y]*fact[y-1+w-x]*inv_fact[x-1]*inv_fact[y-1]*inv_fact[w-x]*inv_fact[h-y]%mod
h,w,a,b = LI()
fact = [1]
for i in range(h+w):
    fact.append(fact[-1]*(i+1)%mod)
inv_fact = [pow(fact[-1],mod-2,mod)]
for i in range(h+w):
    inv_fact.insert(0,inv_fact[0]*(h+w-i)%mod)
ans = 0
for i in range(1,min(w-b,h-a)+1):
    ans += f(b+i,a+i)
    ans %= mod
print(ans)
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
mod = 1000000007


#A
"""
def check(n):
    n = list(map(int,list(str(n))))
    s = 0
    for i in n:
        s += f[i]
    return s == 0
n,k = LI()
d = LI()
f = [0 for i in range(10)]
for i in d:
    f[i] = 1
while 1:
    if check(n):
        print(n)
        quit()
    n += 1
"""
#B
h,w,a,b = LI()
ans = 0
k = 1
inv = [pow(i,mod-2,mod) for i in range(h+w+1)]
x = b+1
y = a+1
for i in range(min(x-1,h-y)):
    k *= (x-1+h-y-i)*inv[i+1]%mod
    k %= mod
for i in range(min(y-1,w-x)):
    k *= (y-1+w-x-i)*inv[i+1]%mod
    k %= mod
for i in range(1,min(w-b,h-a)+1):
    ans += k
    ans %= mod
    k *= (h-y)*(w-x)*inv[x]*inv[y]%mod
    k %= mod
    x += 1
    y += 1
print(ans)
#C

#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T
### BUGGY CODE ###

import collections
N,M = map(int,input().split())
road = [[] for i in range(N+1)]
rev_road = [[] for i in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
    rev_road[y].append(x)

dep = []
for i in range(1,N+1):
    if len(rev_road[i]) == 0:
        dep.append(i)

def largest_distance(i):
    q = collections.deque([i])
    dp =[0]*(N+1) #地点iからの最長経路
    dp_max = 0
    while q:
        now = q.popleft()
        for direct in road[now]:
            if dp[direct]<=dp[now]:
                dp[direct] = dp[now]+1
                q.append(direct)
                dp_max = max(dp_max,dp[direct])
    return dp_max
ans = 0
for de in dep:
    ans = max(ans,largest_distance(de))
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N,M = map(int,input().split())
road = [[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int,input().split())
    road[x].append(y)
flag = [0]*(N+1)
dist = [0]*(N+1)
def distance(i):#地点iから終点までの最長距離
    if flag[i] == 1:
        return dist[i]
    
    if road[i] == []:#行き先がない
        return 0
    else:#行き先がある
        long_dist = 0
        tmp = 0
        for dirct in road[i]:
            tmp = 1 + distance(dirct)
            long_dist = max(long_dist,tmp)
        flag[i]=1
        dist[i] = long_dist
        return long_dist

ans = 0
for i in range(1,N+1):
    ans = max(ans,distance(i))
print(ans)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
nums = list(set(a_list))
r_list = []
for n in nums:
	count = a_list.count(n) + a_list.count(n-1) + a_list.count(n+1)
	r_list.append(count)
print(max(r_list))

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
r_list = [0]*(10**5+2)
for n in a_list:
	r_list[n] += 1
	r_list[n+1] += 1
	if n > 0:
		r_list[n-1] += 1
print(max(r_list))
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(_) for _ in input().split()]
a = [0] + a

rep_check = 0
now = 1
place = []

if now == a[1]:
    print(1)
    exit()

while now not in place:
    place.append(now)
    now = a[now]
    rep_check += 1
    if rep_check == k:
        print(now)
        exit()

rep_start = 0
for i in enumerate(place):
    if i[1] == now:
        rep_start = i[0]
        break

k -= rep_start
rep_cnt = len(place) - rep_start

place = place[rep_start:]
k %= rep_cnt
print(place[k])

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(_) for _ in input().split()]
a = [0] + a

rep_check = 0
now = 1
place = dict()
place2 = []

if now == a[1]:
    print(1)
    exit()

while now not in place:
    place[now] = 1
    place2.append(now)
    now = a[now]
    rep_check += 1
    if rep_check == k:
        print(now)
        exit()

rep_start = 0
for i in enumerate(place):
    if i[1] == now:
        rep_start = i[0]
        break

k -= rep_start
rep_cnt = len(place) - rep_start

place2 = place2[rep_start:]
k %= rep_cnt
print(place2[k])
### BUGGY CODE ###

N, point, Q = map(int, input().split())
ans = [int(input()) for i in range( Q)]
ans = [n-1 for n in ans]
participants = [i for i in range(N)]
points = [point for i in range(N)]

for i in range(len(ans)):
    points = [n-1 for n in points]

for i in ans:
    points[i] += 1

for i in range(N):
    if points[i] > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N, point, Q = map(int, input().split())
ans = [int(input()) for i in range(Q)]
ans = [n-1 for n in ans]
# participants = [i for i in range(N)]
points = [point for i in range(N)]

points = [n-len(ans) for n in points]

for i in ans:
    points[i] += 1

#print(N, point, Q, ans, points)

for i in range(N):
    if points[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

P = []
before_a = False
for i in range(N):
  if before_a and S[i] == 'C':
    P.append(i)
    before_a = False
  elif S[i] == 'A':
    before_a = True
  else:
    before_a = False
for i in range(Q):
  ans = 0
  for num in P:
    if num >= LR[i][0] and num <= LR[i][1]-1:
      ans += 1
  print(ans)

### FIXED CODE ###

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

P = [0] * (N)
before_a = False
cnt = 0
for i in range(N):
  if before_a and S[i] == 'C':
    cnt += 1
    before_a = False
  elif S[i] == 'A':
    before_a = True
  else:
    before_a = False
  P[i] = cnt
for i in range(Q):
  print(P[LR[i][1]-1] - P[LR[i][0]-1])
### BUGGY CODE ###

import sys
n = int(input())
a = [int(_) for _ in input().split()]
ans = 1
for i in a:
    if i == 0:
        ans = 0
        print(ans)
        sys.exit()
    ans *= i
if ans > 10**18:
    ans = -1

print(ans)


### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
ans = 1
for i in a:
    if i == 0:
        ans = 0
        break
    ans *= i
    if ans > 10**18:
        ans = -1
        break

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

n, t = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
m = ab[-1][0]
dp = [0] * (m + t)
for a, b in ab:
    for j in range(t - 1, -1, -1):
        dp[a + j] = max(dp[a + j], dp[j] + b)
print(max(dp))

### FIXED CODE ###

n, t = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
m = ab[-1][0]
dp = [0] * (m + t)
for a, b in ab:
    for j in range(t - 1, -1, -1):
        dp[a + j] = max(dp[a + j], dp[j] + b)
print(max(dp))
### BUGGY CODE ###

import copy
n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=([0]*wv[0][0])+[wv[0][1]]*(w+1-wv[0][0])
for i in range(n-1):
    dp_copy=copy.deepcopy(dp)
    for j in range(w+1):
        if j>=wv[i+1][0]:
            dp[j]=max(dp_copy[j],dp_copy[j-wv[i+1][0]]+wv[i+1][1])
print(dp[-1])

### FIXED CODE ###

n,w=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for j in range(w+1):
        if j>=wv[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[-1][-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

from functools import reduce

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

def gcd_list(numbers):
    return reduce(gcd, numbers)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = ii()
A = li()
inf = 10**9+7
lcm_a = lcm_list(A)

ans = 0
for num in A:
    ans += lcm_a // num
    ans %= inf
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def ti(): return tuple(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

from functools import reduce

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

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

def table(n:int, p=10**9+7):
    global fact, factinv, inv
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, n+1):
        fact.append((fact[-1] * i) % p)
        inv.append((-inv[p % i] * (p // i)) % p)
        factinv.append((factinv[-1] * inv[-1]) % p)

def main():
    N = ii()
    A = ti()
    P = 10**9 + 7
    lcm_a = lcm(A) % P

    N = 10**6+1
    inv_t = [0]+[1]
    for i in range(2,N):
        inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

    #print(inv_t[:10])
    ans = 0
    for num in A:
        ans = (ans + inv_t[num] * lcm_a) % P
        #ans +=  (ans + lcm_a // num) % P
        #ans %= inf
    print(ans)

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

n = int(input())
o = n // 3
a = [0]* n * 2
for i in range(1,o):
    for j in range(1,o):
        for k in range(1,o):
            num = i * i + j * j + k * k + i * j + j * k + k * i
            if  num > n:
                break
            a[num-1] +=1
            #print("#" + str(num)+" "+str(i) + " " + str(j) + " "+ str(k))
for  i in range(n*2):
    if i >= n:
        break
    print(a[i])

### FIXED CODE ###

n = int(input())
o = n // 5
if n > 1000:
    o =n //100
a = [0]* n * 2
for i in range(1,o):
    for j in range(1,o):
        for k in range(1,o):
            num = i * i + j * j + k * k + i * j + j * k + k * i
            if  num > n:
                break
            a[num-1] +=1
           # print("#" + str(num)+" "+str(i) + " " + str(j) + " "+ str(k))
for  i in range(n*2):
    if i >= n:
        break
    print(a[i])
### BUGGY CODE ###

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

def hoge(a):
    for i in range(n):
        for j in range(i+1, n):
            if a[i]==a[j]:
                return "NO"
    return "YES"

print(hoge(a))

### FIXED CODE ###

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

a.sort()
for i in range(n-1):
    if a[i]==a[i+1]:
        print("NO")
        break
else:
    print("YES")
### BUGGY CODE ###

from collections import deque
s = deque(input())
n = len(s)

temp = [0]*2019
num = 0
for i in range(n):
    num += int(s.pop())*pow(10,i)
    temp[num % 2019] += 1

ans = temp[0]
for t in temp:
    if t > 1:
        ans += t*(t-1)/2

print(int(ans))

### FIXED CODE ###

S=input()
N=len(S)
M=2019

remainder=[0]*M
val=0
for i in range(N):
  val=(int(S[N-1-i])*pow(10,i,M)+val)%M
  remainder[val]+=1

ans=remainder[0]
for i in range(2019):
  ans+=remainder[i]*(remainder[i]-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
A = sorted(map(int, input().split()), reverse=False)
dp = [0] * (max(A)+1)

for i in range(N):
    if dp[A[i]] == 0:
        dp[A[i]] = 1
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                dp[A[j]] = 2
print(dp.count(1))


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
a = [['_' for i in range(n)] for i in range(n)]
def dp(i,j):
    if i==n:
        return 0
    if a[i][j] != '_':
        return a[i][j]
    if j==0:
        a[i][j] = dp(i+1,1) + (0 if s[i]=='g' else -1)
        return a[i][j]
    else:
        x = dp(i+1,j+1) + (0 if s[i]=='g' else -1)
        y = dp(i+1,j-1) + (1 if s[i]=='g' else 0)
        a[i][j] = max(x,y)
        return a[i][j]
print(dp(0,0))


### FIXED CODE ###

s=input();n=len(s)//2;m=s.count('p');print(n-m);
### BUGGY CODE ###

N, M = (int(i) for i in input().split())

c = 1
for i in range(1,(M//N)+1):
    if M%i ==0:
        c = i

print(c)


### FIXED CODE ###

import math
N, M = (int(i) for i in input().split())

c = [1]
for i in range(1,math.ceil(math.sqrt(M))):
    if M%i == 0 :
        if i <= M//N and M//i > M//N:
            c.append(i)
        if i <= M//N and M//i <= M//N:
            c.append(M//i)
        else:
            continue
c = sorted(c)
print(c[-1])
### BUGGY CODE ###

import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    B = np.zeros(N, dtype='int32')
    count = 0
    C = {}
    for i in range(N):
        x = i - A[i]
        cx = C.get(x, ([],[]))
        C[x] = (cx[0], cx[1] + [i])
        x = i + A[i]
        cx = C.get(x, ([],[]))
        C[x] = (cx[0] + [i], cx[1])
    for a,b in C.values():
        count += len(a) * len(b)

    print(count)
main()


### FIXED CODE ###

#import numpy as np
#import math
#from decimal import *
#from numba import njit
from collections import Counter

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0
    r = []
    l = []
    for i in range(N):
        r += i - A[i],
        l += i + A[i],

    c = Counter(l)
    for i in r:
        count += c[i]

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

import collections

X, Y = map(int, input().split())

ans = "No"
for i in range(2**X):
    count = collections.Counter(bin(i)[2:].zfill(X))
    num = count["0"]*2 + count["1"]*4
    if num == Y:
        ans = "Yes"
        break
    elif num > Y:
        ans = "No"
        break

print(ans)


### FIXED CODE ###

X, Y = map(int, input().split())

b = (Y - 2*X)/2
a = X - b

is_int = (a.is_integer() and b.is_integer())
is_positive = (a >= 0 and b >= 0)
if is_int and is_positive and (a + b) == X and (2*a + 4*b) == Y:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    print(s[l-1:r].count("AC"))                                                              

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
a=[0]*n
ac=0
for i in range(1,n):
    if s[i-1]=="A" and s[i]=="C":
        ac+=1
    a[i]=ac
for i in range(q):
    l,r=map(int,input().split())
    print(a[r-1]-a[l-1])
### BUGGY CODE ###

import re

n = int(input())
s = []
for i in range(n):
    s.append(input())
res = 0
for index, j in enumerate(s):
    for k in s[index + 1:]:
        for l in j:
            k = re.sub(l, "", k)
        if not k:
            res += 1

print(res)


### FIXED CODE ###

n = int(input())
dic = {}
res = 0
for i in range(n):
    s = ''.join(sorted(input()))
    if s in dic.keys():
        res += dic[s]
        dic[s] += 1
    else:
        dic[s] = 1
print(res)
### BUGGY CODE ###

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

ans=[0]*N
D=[[0]*N for _ in range(N)]
graph=[[] for _ in range(N)]
for i in range(M):
  L,R,d=map(int,input().split())
  L,R=L-1,R-1
  D[L][R]=d
  D[R][L]=-d
  ans[R]=ans[L]+D[L][R]
  graph[L].append(R)
  graph[R].append(L)
  for j in graph[R]:
    if ans[R]-ans[j]!=D[j][R]:
      print("No")
      exit()
    else:
      continue
print("Yes")

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,M=map(int,input().split())
graph=[[] for _ in range(N)]

for _ in range(M):
  l,r,d=map(int,input().split())
  l,r=l-1,r-1
  graph[l].append([r,d])
  graph[r].append([l,-d])

def BFD(x):
  global checked,answer,graph
  checked[x]=1
  for i,distance in graph[x]:
    if answer[i]=="first":
      answer[i]=answer[x]+distance
    else:
      if answer[i]!=answer[x]+distance:
        print("No")
        exit()
    
    if checked[i]==0:
      BFD(i)

checked=[0]*N
answer=["first"]*N

for i in range(N):
  if checked[i]==0:
    answer[i]=0
    BFD(i)

print("Yes")
### BUGGY CODE ###

def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*(pow(2,Bsum(B1,X[i][1]+1),mod)-1)%mod
    if Z[j][1]:
      A=A*(pow(2,i-Bsum(B1,X[i][1]+1),mod)-1)%mod
    if Z[j][2]:
      A=A*(pow(2,Bsum(B2,X[i][1]+1),mod)-1)%mod
    if Z[j][3]:
      A=A*(pow(2,N-i-1-Bsum(B2,X[i][1]+1),mod)-1)%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)

### FIXED CODE ###

import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(S[0])
X=[list(map(int,S[i+1].split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  W=[pow(2,V[0],mod)-1,pow(2,i-V[0],mod)-1,pow(2,V[1],mod)-1,pow(2,N-i-1-V[1],mod)-1]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*W[0]%mod
    if Z[j][1]:
      A=A*W[1]%mod
    if Z[j][2]:
      A=A*W[2]%mod
    if Z[j][3]:
      A=A*W[3]%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
total = 0
for i in range(n):
  for j in range(i + 1, n):
    total += l[i] * l[j]
print(total % (10 ** 9 + 7))

### FIXED CODE ###

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

n = int(input())
S = input()
q = int(input())
K = list(map(int, input().split()))
for k in K:
  d = 0
  m = 0
  dm = 0
  dmc = 0
  for s in S[:k-1]:
    if s == "D":
      d += 1
    elif s == "M":
      m += 1
      dm += d
    elif s == "C":
      dmc += dm
  for s,e in zip(S[k-1:],S):
    if s == "D":
      d += 1
    elif s == "M":
      m += 1
      dm += d
    elif s == "C":
      dmc += dm
    if e == "D":
      d -= 1
      dm -= m
    elif e == "M":
      m -= 1
  print(dmc)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  S = input()[:-1]
  q = int(input())
  K = map(int, input().split())
  for k in K:
    d = 0
    m = 0
    dm = 0
    dmc = 0
    for s in S[:k-1]:
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
    for s,e in zip(S[k-1:],S):
      if s == "D":
        d += 1
      elif s == "M":
        m += 1
        dm += d
      elif s == "C":
        dmc += dm
      if e == "D":
        d -= 1
        dm -= m
      elif e == "M":
        m -= 1
    print(dmc)
  
if __name__ == "__main__":
  main()