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

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(i8(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape
    queue = [(0,ch*w+cw)]
    used_map = np.full(h*w,2<<30,dtype=np.int64)
    goal = dh*w+dw

    #move walk
            
    while len(queue) != 0:
        dot = heapq.heappop(queue)
        tl,n = dot[0],dot[1]
        th,tw = divmod(n,w)
        used_map[n] = tl
        if n == goal:
            break

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if x == y == 0:
                    continue
                if abs(x)+abs(y) <= 1:
                    loop = tl
                else:
                    loop = tl+1
                tx = th + x
                ty = tw + y
                next_n  = tx*w+ty
                if tx < 0 or ty < 0 or tx >= h or ty >= w or road_map[tx][ty] == True:
                    continue
                check = used_map[next_n]
                if check > loop:
                    heapq.heappush(queue,(loop,next_n))

    if used_map[goal] == 2<<30:
        return -1
    else:
        return used_map[goal]

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

print(solve(ch,cw,dh,dw,road_map))



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X = input().strip()
    while X.count("ST"):
        a = X.find("ST")
        X = X[:a] + X[a + 2:]

    print(len(X))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X = input().strip()


    scount = 0
    ans = 0
    for s in X:
        if s == "S":
            scount += 1
        elif s == "T":
            if scount == 0:
                continue
            else:
                scount -= 1
                ans += 2

    print(len(X) - ans)



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

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
RC110 D
"""


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

from math import sqrt
from collections import deque
def divisors(x):
    divs = deque()
    sx = int(sqrt(x))
    if x == sx**2:
        divs.append(sx)
        sx = sx-1
    for i in range(sx,0,-1):
        if x%i==0:
            divs.append(i)
            divs.appendleft(x//i)
    return(divs)

mdivs = list(divisors(m))
from collections import defaultdict
divsdict = defaultdict(list)
for d in mdivs:
    divsdict[d] = [dd for dd in mdivs if d%dd==0]

dpdict = defaultdict(int)
for d in mdivs:
    dpdict[d]=0
dpdict[1] = 1


cut = 10**9+7

for i in range(n):
    for d in mdivs:
        dpdict[d] = sum(map(lambda x:dpdict[x],divsdict[d]))%(10**9+7)

print(dpdict[m])



### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
RC110 D
"""


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

from math import sqrt
from collections import deque
def divisors(x):
    divs = deque()
    sx = int(sqrt(x))
    if x == sx**2:
        divs.append(sx)
        sx = sx-1
    for i in range(sx,0,-1):
        if x%i==0:
            divs.append(i)
            divs.appendleft(x//i)
    return(divs)

mdivs = list(divisors(m))
from collections import defaultdict
divsdict = defaultdict(list)
for d in mdivs:
    divsdict[d] = [dd for dd in mdivs if d%dd==0]

nbin = list(map(int,format(n,'b')))
nnbin = len(nbin)
dpdicts = [defaultdict(int) for i in range(nnbin)]
for d in mdivs:
    dpdicts[0][d]=1

cut = 10**9+7

for i in range(1,nnbin):
    for d in mdivs:
        dpdicts[i][d] = sum(map(lambda x:dpdicts[i-1][x]*dpdicts[i-1][d//x],divsdict[d]))%(10**9+7)

dpdictbin = defaultdict(int)
for d in mdivs:
    dpdictbin[d]=0
dpdictbin[1]=1

nbin.reverse()
for i in filter(lambda x:nbin[x]==1,range(nnbin)):
    for d in mdivs:
        dpdictbin[d] = sum(map(lambda x:dpdictbin[x]*dpdicts[i][d//x],divsdict[d]))%(10**9+7)



print(dpdictbin[m])
### BUGGY CODE ###

N,P=map(int,input().split())
S=list(input())
count=0

if P!=2 and P!=5:
    for i in range(0,N):
        chec=int(S[i])
        j=0
        while i+j<N:
                if chec%P==0:
                    count+=1
                j+=1
                try:
                    chec=(chec%P)*10+int(S[i+j])
                except:
                    pass
if P==2:
    for i in range(N):
        if int(S[i])%2==0:
            count+=i+1
if P==5:
    for i in range(N):
        if int(S[i])==0 or int(S[i])==5:
            count+=i+1
print(count)


            




### FIXED CODE ###

#E
N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        # print(CS)
        # print(cnt)
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
D = list(map(int, input().split()))
D.sort()
M = int(input())
T = list(map(int, input().split()))
for i in range(M):
    t = T[i]
    idx = min(bisect.bisect_left(D, t), len(D) - 1)
    d = D[idx]
    if t == d:
        D.pop(idx)
    else:
        print('NO')
        exit()
print('YES')



### FIXED CODE ###

from collections import defaultdict
N = int(input())
D = list(map(int, input().split()))
D_dict = defaultdict(int)
for d in D:
    D_dict[d] += 1
M = int(input())
T = list(map(int, input().split()))
T_dict = defaultdict(int)
for t in T:
    T_dict[t] += 1

for target, t_cnt in T_dict.items():
    d_cnt = D_dict[target]
    if t_cnt > d_cnt:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

N = int(input())
X = input()

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

for i in range(N):
    bi = 1
    if X[i] == '0':
        for j in range(N-1-i):
            bi = bi * 2 % (pop+1)
        res = (plu + bi) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        for j in range(N-1-i):
            bi = bi * 2 % (pop-1)
        res = (mai - bi) % (pop-1)
    print(arr[res] + 1)

### FIXED CODE ###

N = int(input())
X = input()

arr = [0 for _ in range(N+1)]
for i in range(1, N+1):
    cnt = bin(i).count('1')
    arr[i] = arr[i%cnt] + 1

x = int(X, 2)
pop = X.count('1')
plu = x % (pop+1)
mai = x % (pop-1) if pop>1 else 0

#bi = 1 << N
for i in range(N):
    #bi = bi >> 1
    if X[i] == '0':
        #res = (plu + bi % (pop+1)) % (pop+1)
        res = (plu + pow(2, N-1-i, pop+1)) % (pop+1)
    else:
        if pop == 1:
            print(0)
            continue
        #res = (mai - bi % (pop-1)) % (pop-1)
        res = (mai - pow(2, N-1-i, pop-1)) % (pop-1)
    print(arr[res] + 1)
### BUGGY CODE ###

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

cnt = 0
for i in range(1000):
    c = list(str(i).zfill(3).strip())
    f = 0
    for j in range(N):
        if S[j] == c[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1
        
print(cnt)        

### FIXED CODE ###

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

cnt = 0
for i in range(1000):
    c = list(str(i).zfill(3).strip())
    f = 0
    for j in range(N):
        if S[j] == c[f]:
            f += 1
        if f == 3:
            break
    if f == 3:
        cnt += 1
        
print(cnt)
### BUGGY CODE ###

N = int(input())
c = list(input())

cnt = 0
for i in range(N):
  if c[i] == 'W':
    flag = True
    for j in range(N-1,i,-1):
      if c[j] == 'R':
        c[j] = 'W'
        cnt+=1
        flag = False
        break
    if flag:
      break
print(cnt)

### FIXED CODE ###

N = int(input())
c = list(input())

cnt = 0
w_last_index = N-1
for i in range(N):
  if c[i] == 'W':
    flag = True
    for j in range(w_last_index,i,-1):
      if c[j] == 'R':
        c[j] = 'W'
        w_last_index=j
        cnt+=1
        flag = False
        break
    if flag:
      break
print(cnt)
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a,reverse=True)
y = 1

if n == 1:
    print(a[0]//(2**m))
else:
    for i in range(m):
        if m < 1:
            a[0] = a[0]//(2**y)
            break
        if a[0]-a[0]//(2**y) > a[1]-a[1]//(2**y):
            a[0] = a[0]//(2**y)
            i -= 1
            m -= 1
        else:
            a[0] = a[0]//(2**y)
        a = sorted(a,reverse=True)
    
    print(sum(a))




### FIXED CODE ###

import math
import heapq
n,m = map(int,input().split())
a = list(map(lambda x: -int(x),input().split()))
heapq.heapify(a)
for i in range(m):
    a_max = heapq.heappop(a)
    heapq.heappush(a,-(-a_max//2))
print(-sum(a))
### BUGGY CODE ###

mod = 1000003
fa = [1] * (2 * mod + 1)
fi = [1] * (2 * mod + 1)
for i in range(1, 2 * mod + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
q = int(input())
for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
        continue
    if x == 0 or n >= mod:
        print(0)
        continue
    x *= pow(d, mod - 2, mod)
    x %= mod
    ans = (fa[x + n - 1] * fi[x - 1] % mod) * pow(d, n, mod)
    ans %= mod
    print(ans)

### FIXED CODE ###

mod = 1000003
fa = [1] * (2 * mod + 1)
fi = [1] * (2 * mod + 1)
for i in range(1, 2 * mod + 1):
    fa[i] = fa[i - 1] * i % mod
    fi[i] = pow(fa[i], mod - 2, mod)
q = int(input())
for _ in range(q):
    x, d, n = map(int, input().split())
    if d == 0:
        print(pow(x, n, mod))
        continue
    if x == 0 or n >= mod:
        print(0)
        continue
    x *= pow(d, mod - 2, mod)
    x %= mod
    ans = (fa[x + n - 1] * fi[x - 1] % mod) * pow(d, n, mod)
    ans %= mod
    print(ans)
### BUGGY CODE ###

from collections import deque
N = int(input())
A = deque([int(input()) for _ in range(N)])

for i in range(N):
    tmp = A.popleft()
    print(max(A))
    A.append(tmp)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)
for x in A:
    if x == B[-1]:
        print(B[-2])
    else:
        print(B[-1])
### BUGGY CODE ###

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

s=input()
s=s.strip("\n")
n=len(s)
res=0
d={}
t=[0]*(n+1)
d[0]=1
for i in range(1,n+1):
    t[n-i]=(t[n-i+1]+(int(s[n-i])*10**(i-1))%2019)%2019
    if t[n-i] not in d:
        d[t[n-i]]=1
    else:
        d[t[n-i]]+=1
for i in d.values():
    res+=int(i*(i-1)/2)
print(res)


### FIXED CODE ###

from collections import Counter

def main():

  s=input()
  n=len(s)
  res=0
  t=[0]*(n+1)
  k=1
  for i in range(1,n+1):
      t[n-i]=(t[n-i+1]+int(s[n-i])*k)%2019
      k*=10
      k=k%2019
  d=Counter(t)
  for i in d.values():
      if i<2:
        continue
      res+=i*(i-1)/2
  print(int(res))

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

#129_D
h, w = map(int, input().split())
s = [input() for _ in range(h)]

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
            
for i in range(h):
    for j in range(w-1, -1, -1):
        if s[i][j] == '#':
            continue
        elif j == w-1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
            
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
            
for i in range(h-1, -1, -1):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == h-1:
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        x = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, x)
        
print(ans)

### FIXED CODE ###

#129_D
h, w = map(int, input().split())
s = [input() for _ in range(h)]

L = [[0]*w for _ in range(h)]
R = [[0]*w for _ in range(h)]
U = [[0]*w for _ in range(h)]
D = [[0]*w for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
            
for i in range(h):
    for j in range(w-1, -1, -1):
        if s[i][j] == '#':
            continue
        elif j == w-1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
            
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
            
for i in range(h-1, -1, -1):
    for j in range(w):
        if s[i][j] == '#':
            continue
        elif i == h-1:
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        x = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        ans = max(ans, x)
        
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
sa = sum(a)
m = 10**10
for i in range(1,n):
    m = min(m, abs(sa-2*sum(a[:i])))
print(m)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
sa = sum(a)
x = a[0]
m = abs(sa-2*x)
for i in range(1,n-1):
    x += a[i]
    m = min(m, abs(sa-2*x))
print(m)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())

S_set = list(set(S))
S_dic = {}
M = 0
for s in S_set:
    S_dic[s] = S.count(s)
    M = max(M, S.count(s))

S_dic_sorted = sorted(S_dic.items(), key=lambda x: x[0])
for l in S_dic_sorted:
    if l[1] == M:
        print(l[0])

### FIXED CODE ###

import collections

N = int(input())
S = []
for _ in range(N):
    S.append(input())

C = collections.Counter(S).most_common()
M = C[0][1]

ans = []
for c in C:
    if c[1] == M:
        ans.append(c[0])
    else:
        break

ans.sort()
for a in ans:
    print(a)
### BUGGY CODE ###

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

### FIXED CODE ###

import sys


# \n
def input():
    return sys.stdin.readline().rstrip()


def main():

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

    current = sum(A[:K])
    ans =(current+K)/2

    for i in range(1,N-K+1):
        current = current - A[i-1] + A[i+K-1]
        ans = max(ans, (current+K)/2 )
    print(ans)



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

from collections import defaultdict

S = input()
K = int(input())

alphabet = defaultdict(list)
for i, s in enumerate(S):
    alphabet[s].append(i)

alpha_list = sorted(alphabet.keys())
cand = []
i = 0
while len(cand) < K:
    for j in alphabet[alpha_list[i]]:
        for l in range(1, len(S)-j+1):
            cand.append(S[j:j+l])
    cand = list(set(cand))
    if len(cand) >= K:
        break
    i += 1
cand = sorted(cand)
print(cand[K-1])

### FIXED CODE ###

# ABC 097 C

from collections import defaultdict

S = input()
K = int(input())

alphabet = defaultdict(list)
for i, s in enumerate(S):
    alphabet[s].append(i)

alpha_list = sorted(alphabet.keys())
cand = []
i = 0
while len(cand) < K:
    for j in alphabet[alpha_list[i]]:
        if len(S)-j+1 >= K:
            for l in range(1, K+1):
                cand.append(S[j:j+l])
        else:
            for l in range(1, len(S)-j+1):
                cand.append(S[j:j+l])
    cand = list(set(cand))
    if len(cand) >= K:
        break
    i += 1
cand = sorted(cand)
print(cand[K-1])
### BUGGY CODE ###

n, m = map(int, input().split())
for i in range(m//n, 0, -1):
  if m%i==0:
    break
print(i)

### FIXED CODE ###

def solve():
  n, m = map(int, input().split())
  for i in range(m//n, 0, -1):
    if m%i==0:
      break
  print(i)

if __name__=='__main__':
  solve()
### BUGGY CODE ###

import math
from functools import lru_cache


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[i][j] = min(OPT[i][k]+OPT[k+1][j])+sum(A[i:j+1])    i <= k < j
    OPT[i][j] = 0 if i == j
    """
    N = read_int()
    A = read_ints()

    @lru_cache(None)
    def dp(i, j):
        if i == j:
            return 0
        return min(dp(i, k)+dp(k+1, j)+sum(A[i:j+1]) for k in range(i, j))

    return dp(0, N-1)


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

import math
from functools import lru_cache, reduce


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def prefix_sum(arr, a):
    arr.append(arr[-1]+a)
    return arr


def solve():
    """
    OPT[i][j] = min(OPT[i][k]+OPT[k+1][j])+sum(A[i:j+1])    i <= k < j
    OPT[i][j] = 0 if i == j
    """
    N = read_int()
    A = read_ints()
    prefix = reduce(prefix_sum, A, [0])

    @lru_cache(None)
    def dp(i, j):
        if i == j:
            return 0
        return min(dp(i, k)+dp(k+1, j)+(prefix[j+1]-prefix[i]) for k in range(i, j))

    OPT = [[0]*N for _ in range(N)]
    for j in range(N):
        for i in range(j-1, -1, -1):
            OPT[i][j] = min(OPT[i][k]+OPT[k+1][j] for k in range(i, j))+(prefix[j+1]-prefix[i])

    return OPT[0][N-1]


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_facts(n):
    '''
        make factorials
        0!(=1), 1!, 2!, 3! .... n!
    '''
    fact = [1]
    for i in range(n):
        fact.append((fact[i] * (i + 1)) % MOD)
    return fact

def make_combs(n, k):
    '''
        make [C(n, 0), C(n, 1), C(n, 2) ..... C(n, k)]
        n! / (n - k)! k!
    '''
    facts = make_facts(n)
    invs = [] # inverted for fraction
    for fact in facts:
        invs.append(pow(fact, MOD - 2, MOD))

    ret = []
    for i in range(0, n + 1):
        a = facts[n]
        #b = facts[i]
        #c = facts[n - i]
        ret.append(a * invs[i] * invs[n - i] % MOD)
    return ret


def _calc(n):
    ret = 2
    tmp = 1
    while tmp < n:
        print(tmp, ret)
        ret = (ret * ret) % MOD
        tmp *= 2
    if n - tmp > 0:
        t = _calc(n - tmp)
        ret *= t
    return ret

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x %= MOD
        n //= 2

    return K * x % MOD


def solve(n: int, a: int, b: int):
    #ret = ((2 ** n) - 1) % MOD
    #ret = (_calc(n) - 1) % MOD
    ret = (pow(2, n, MOD) - 1) % MOD
    #ret = (pow_k(2, n) - 1) % MOD
    combs = make_combs(n, n)
    ret = (ret + MOD * 2 - combs[a] - combs[b]) % MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def get_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def make_comb(n, k):
    a = 1
    b = 1
    for i in range(k):
        a = a * (n - i) % MOD
        b = b * (i + 1) % MOD
    ret = get_fraction_mod(a, b)
    return ret


def solve(n: int, a: int, b: int):
    ret = (pow(2, n, MOD) - 1) % MOD
    ret = ret + MOD - make_comb(n, a)
    ret = ret + MOD - make_comb(n, b)
    ret %= MOD
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    n = int(next(tokens))  # type: int
    a = int(next(tokens))  # type: int
    b = int(next(tokens))  # type: int
    solve(n, a, b)

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

N, Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(lambda x: int(x)-1, input().split())
  ans = 0
  for i in range(l, r):
    if S[i] == "A" and S[i+1] == "C":
      ans += 1
  print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
A = []
for i in range(N - 1):
  if S[i] == "A" and S[i+1] == "C":
    A.append(i+1)
lA = len(A)
for i in range(Q):
  l, r = map(int, input().split())
  L1 = -1
  R1 = lA
  while L1 + 1 < R1:
    C1 = (L1 + R1) // 2
    if A[C1] < l:
      L1 = C1
    else:
      R1 = C1
  L2 = -1
  R2 = lA
  while L2 + 1 < R2:
    C2 = (L2 + R2) // 2
    if A[C2] < r:
      L2 = C2
    else:
      R2 = C2
  print(L2 - L1)