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

import sys
input = sys.stdin.buffer.readline


def convolve(a, b):
    """配列a, bの畳み込みをNTT(number-theoretical transform)によって計算する
    res[k] = (sum{i=0...n}a[i]*b[k-i]) % MOD
    """
    MOD = 998244353
    ROOT = 5

    def ntt(a, inverse=False):
        # バタフライ演算用の配置入れ替え
        for i in range(n):
            j = 0
            for k in range(log_sz):
                j |= (i >> k & 1) << (log_sz - 1 - k)
            if i < j:
                a[i], a[j] = a[j], a[i]

        h = pow(ROOT, (MOD - 1) * pow(n, MOD - 2, MOD) % MOD, MOD)
        if inverse:
            h = pow(h, MOD - 2, MOD)

        # バタフライ演算
        m = 1
        while m < n:
            zeta_pow = 1
            zeta = pow(h, n // (2 * m), MOD)
            for j in range(m):
                for k in range(0, n, 2 * m):
                    s = a[j + k]
                    t = a[j + k + m] * zeta_pow
                    a[j + k] = (s + t) % MOD
                    a[j + k + m] = (s - t) % MOD
                zeta_pow *= zeta
                zeta_pow %= MOD
            m <<= 1

        # 逆変換時には配列のサイズの逆元をかける
        if inverse:
            n_inv = pow(n, MOD - 2, MOD)
            for i in range(n):
                a[i] *= n_inv
                a[i] %= MOD
        return a

    def intt(a):
        return ntt(a, inverse=True)

    n = 1 << (len(a) + len(b) - 1).bit_length()
    log_sz = n.bit_length() - 1
    a += [0] * (n - len(a))
    b += [0] * (n - len(b))

    # in-placeで計算を進めることに注意
    ntt(a), ntt(b)
    for i, val in enumerate(b):
        a[i] *= val
        a[i] %= MOD
    intt(a)

    return a
  

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

ptn = [1]
ans = 0
for i in range(n):
    add = [0] * (a[i] + 1)
    add[0] = 1
    add[-1] = 1
    ptn = convolve(ptn, add)[:s + 1]
    if len(ptn)  > s:
        ans += ptn[s]
        ans %= MOD
    ptn[0] += 1

print(ans)

### FIXED CODE ###

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

dp = [0] * (3000 + 1)
dp[0] = 1
ans = 0
for i in range(n):
    for w in range(3000 + 1)[::-1]:
        # 選ぶとき
        if w - a[i] > 0:
            dp[w] += dp[w - a[i]]
        if w - a[i] == 0:
            dp[w] += dp[w - a[i]] * (i + 1)
        dp[w] %= MOD
    ans += dp[s]
    ans %= MOD
print(ans % MOD)
### BUGGY CODE ###

from collections import defaultdict

h, w, m = map(int, input().split())

cnt_h = [0] * h
cnt_w = [0] * w
dic = defaultdict(int)

for _ in range(m):
    h_m, w_m = map(int, input().split())
    cnt_h[h_m - 1] += 1
    cnt_w[w_m - 1] += 1
    dic[(h_m - 1, w_m - 1)] += 1

max_h = max(cnt_h)
max_w = max(cnt_w)

mh = []
mw = []

for i in range(h):
    if max_h == cnt_h[i]:
        mh.append(i)

for i in range(w):
    if max_w == cnt_w[i]:
        mw.append(i)

flag = False
for i in mh:
    for j in mw:
        if dic[(i, j)] == 0:
            flag = True

if flag:
    print(max_h + max_w)
else:
    print(max_h + max_w - 1)

### FIXED CODE ###

from collections import defaultdict

h, w, m = map(int, input().split())

cnt_h = [0] * h
cnt_w = [0] * w
dic = defaultdict(int)

for _ in range(m):
    h_m, w_m = map(int, input().split())
    cnt_h[h_m - 1] += 1
    cnt_w[w_m - 1] += 1
    dic[(h_m - 1, w_m - 1)] += 1

max_h = max(cnt_h)
max_w = max(cnt_w)

mh = []
mw = []

for i in range(h):
    if max_h == cnt_h[i]:
        mh.append(i)

for i in range(w):
    if max_w == cnt_w[i]:
        mw.append(i)

for i in mh:
    for j in mw:
        if dic[(i, j)] == 0:
            print(max_h + max_w)
            quit()

print(max_h + max_w - 1)
### BUGGY CODE ###

mod = 7+10**9

def expo(x):
  ans = 1
  n = mod-2
  while n>0:
    if n%2 == 1:
      ans = ans*x%mod
    x = x*x%mod
    n = n >> 1
  return ans

def combi(n,k):
  return (fac[n]*(expo(fac[k]))%mod)*expo(fac[n-k])%mod

n,k = map(int,input().split())
fac = [1]+[0]*n
for i in range(1,n+1):
  fac[i] = fac[i-1]*i%mod

ans = 0
for i in range(min(n,k+1)):
  ans = (ans + combi(n,i)*combi(n-1,i)%mod)%mod
print(ans)

### FIXED CODE ###

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

mod = 10**9 + 7
l = 10**7
fac = [1]*l
facr = [1]*l

for i in range(l-1):
    fac[i+1] = fac[i]*(i+1)%mod
facr[l-1] = pow(fac[l-1],mod - 2,mod)
for i in range(1,l)[::-1]:
    facr[i-1] = facr[i]*i%mod

def combi(N,K):
    return fac[N]*facr[N-K]%mod*facr[K]%mod

ans = 1
for i in range(1,min(n,k+1)):
    ans += combi(n,i)*combi(n-1,i)%mod
    ans %= mod
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
  print(A[i-1:].count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans_list = [0]*N

for i in range(N-1):
  ans_list[A[i]-1] += 1
  
for j in range(N):
  print(ans_list[j])
### BUGGY CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		S[i+1] += atack_cnt * A
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= atack_cnt * A

print(ans)

### FIXED CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)
ind = np.searchsorted(X,X+L+1,side = 'left')

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		S[ind[i]] -= tmp

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

r,g,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    for j in range(n+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)


### FIXED CODE ###

r,g,b,n = map(int, input().split())
ans = 0
for i in range(n+1):
    for j in range(n+1):
        k = n - (i*r + j*g)
        if k < 0:
            break
        elif k >= 0 and k%b == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, W = MAP()
wN, vN = [0]*N, [0]*N
for i in range(N):
    wN[i], vN[i] = MAP()

# dp[何個目までから選ぶか][これまでに選んだ荷物の重さ] = これまでに選んだ荷物の価値
dp = [[0] * (W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        # 真下には常に送る
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j + wN[i] <= W:
            # 重さが制限内なら右下にも送る
            dp[i+1][j+wN[i]] = max(dp[i+1][j+wN[i]], dp[i][j] + vN[i])
print(dp[N][W])


### FIXED CODE ###

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, W = MAP()
wN, vN = [0]*N, [0]*N
for i in range(N):
    wN[i], vN[i] = MAP()

# dp[何個目までから選ぶか][これまでに選んだ荷物の重さ] = これまでに選んだ荷物の価値
dp = [[0] * (W+1) for i in range(N+1)]

for i in range(N):
    for j in range(W+1):
        # 真下には常に送る
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j + wN[i] <= W:
            # 重さが制限内なら右下にも送る
            dp[i+1][j+wN[i]] = max(dp[i+1][j+wN[i]], dp[i][j] + vN[i])
print(dp[N][W])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)


def main():
    n, m = map(int, input().split())
    h_list = list(map(int, input().split()))
    ll = []
    for i in range(m):
        a, b = map(int, input().split())
        ll.append((a-1, b-1))

    goods = list(range(n))
    for x, y in ll:
        if h_list[x] == h_list[y]:
            if y in goods:
                goods.remove(y)
            if x in goods:
                goods.remove(x)
        if h_list[x] > h_list[y]:
            if y in goods:
                goods.remove(y)
        else:
            if x in goods:
                goods.remove(x)

    print(len(goods))


main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)


def main():
    n, m = map(int, input().split())
    h_list = list(map(int, input().split()))
    not_good = set()
    for i in range(m):
        a, b = map(int, input().split())
        # ll.append((a-1, b-1))
        x = a-1
        y = b-1
        hx = h_list[x]
        hy = h_list[y]
        if hx == hy:
            not_good.add(x)
            not_good.add(y)
        elif hx > hy:
            not_good.add(y)
        else:
            not_good.add(x)

    print(n - len(not_good))


main()
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "#":
            visited[row][col] = 0
            queue.append((row, col, 0))

while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))

result = 0
for row in visited:
    row_max = max(row)
    if row_max > result:
        result = row_max

print(result)


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
move = [(1,0), (0,1), (-1,0), (0,-1)]

queue = deque()
visited = [[-1] * w for _ in range(h)]
for row in range(h):
    for col in range(w):
        if a[row][col] == "#":
            visited[row][col] = 0
            queue.append((row, col, 0))
dist = 0
while queue:
    row, col, dist = queue.popleft()
    for drow, dcol in move:
        if a[row+drow:row+drow+1] and a[row+drow][col+dcol:col+dcol+1] and visited[row+drow][col+dcol] == -1 and a[row+drow][col+dcol] == ".":
            visited[row+drow][col+dcol] = dist + 1
            queue.append((row+drow, col+dcol, dist+1))


print(dist)
### BUGGY CODE ###

import math
from collections import Counter
N = int(input())

for i in range(N):
    x_flg = False
    y_flg = False
    count = 0
    if i < 5:
        print(count)
    else:
        x_min = 1
        x_max = int(math.sqrt(i + 1))
        for x in range(x_min, x_max + 1):
            for y in range(x, x_max + 1):
                for z in range(y, x_max + 1):
                    #print(i, x, y, z)
                    if x * x + y * y + z * z + x * y + y * z + z * x == i + 1:
                        numbers = Counter([x, y, z]).values()
                        count += math.factorial(3)
                        for number in numbers:
                            count /= math.factorial(number)
                    elif x * x + y * y + z * z + x * y + y * z + z * x > i + 1:
                        break
        print(int(count))

### FIXED CODE ###

N = int(input())
answer = [0] * (10001)

for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            index = x * x + y * y + z * z + x * y + y * z + z * x - 1
            if index > N:
                break
            answer[index] += 1
            

for i in range(N):
    print(answer[i])
### BUGGY CODE ###

import math

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


def choose(n, a):
    x = 1
    y = 1
    for i in range(a):
        x *= n - i
        y *= i + 1
    return x // y


def pow2(num):
    c = 2
    d = 1
    dic = {d: c}

    for _ in range(20):
        c **= 2
        d *= 2
        dic[d] = c

    ret = 0
    while d != 0:
        if num >= d:
            num -= d
            if ret == 0:
                ret = dic[d]
            else:
                ret *= dic[d]
        else:
            d //= 2
    return ret


print((pow2(n) - 1 - choose(n, a) - choose(n, b)) % 1000000007)

### FIXED CODE ###

from functools import reduce

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

MOD = 10**9 + 7


def comb(n, r, mod=float("inf")):
    c = 1
    m = 1
    r = min(n - r, r)
    for i in range(r):
        c = c * (n - i) % mod
        m = m * (i + 1) % mod
    return c * pow(m, mod - 2, mod) % mod


print((pow(2, n, MOD) - comb(n, a, MOD) - comb(n, b, MOD) - 1) % MOD)
### BUGGY CODE ###

S = input()

N = len(S)

answer = 0

for start in range(N-3):
    for end in range(start+3,N+1):
        if int(S[start:end]) % 2019 == 0:
            answer += 1

print(answer)

### FIXED CODE ###

S = list(map(int, list(input())))

pops = 0
digi = 1
cnt = [0] * 2019
cnt[0] = 1

while S:
    s = S.pop()

    pops = (pops + s * digi) % 2019
    digi = (10 * digi) % 2019

    cnt[pops] += 1

ans = 0

for i in range(2019):
    ans += cnt[i] * (cnt[i] - 1) // 2

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

from collections import deque

n = int(input())
alist = deque()
for i in range(n):
    alist.append(int(input()))



anslist = deque()
for _ in range(n):
    ai = alist.popleft()
    anslist.append(max(alist))
    alist.append(ai)

for i in anslist:
    print(i)
    
    

### FIXED CODE ###


n = int(input())
alist = []
for i in range(n):
    alist.append(int(input()))

amax = max(alist)
anslist = [amax]*n
if alist.count(amax)>=2:
    for i in anslist:
        print(i)
    exit()

if alist.count(amax)==1:
    maxindex = alist.index(amax)
    del alist[maxindex]
    anslist[maxindex]= max(alist)
    for i in anslist:
        print(i)
    exit()
### BUGGY CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k-1, n):
    #print(A[i])
    now = 1
    for j in range(k):
        now *= A[i-j]
    if i == k-1:
        before = now
    else:
        #print(now, before)
        if before < now:
            print("Yes")
        else:
            print("No")
        before = now

### FIXED CODE ###

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

import sys, math, itertools, collections, bisect 
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1
 
n, k = map(int, input().split())
A = list(map(int, input().split()))
for i in range(k-1, n):
    if i == k-1:
        continue
    else:
        if A[i] > A[i-k]:
            print("Yes")
        else:
            print("No")
        #print(A[i], A[i-k])
### BUGGY CODE ###

N = int(input())
result = 0
for i in range(N+1):
    count = 0
    flag = True
    while flag == True:
        if i%2 == 0:
            count += 1
            i = i/2
        else:
            flag = False
        result = max([result,count])

print(2^(result))


### FIXED CODE ###

N = int(input())

count = 0

while N != 1:
    count += 1
    N = N//2

print(2**count)
### BUGGY CODE ###

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

dp=[[0 for _ in range(i)] for i in range(N)]
#dp[i][j]:i文字目とj文字目からの共通文字の最大長さ(i>j)

for i in range(N-1):
  if S[i]==S[N-1]:
    dp[N-1][i]=1

for i in reversed(range(N-1)):
  for j in range(i):
    if S[i]==S[j]:
      dp[i][j]=dp[i+1][j+1]+1
      if j+dp[i][j]-1>=i:
        dp[i][j]=i-j

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

print(max(A))


### FIXED CODE ###

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

dp=[[0 for _ in range(i)] for i in range(N)]
#dp[i][j]:i文字目とj文字目からの共通文字の最大長さ(i>j)

for i in range(N-1):
  if S[i]==S[N-1]:
    dp[N-1][i]=1

for i in reversed(range(N-1)):
  for j in range(i):
    if S[i]==S[j]:
      dp[i][j]=dp[i+1][j+1]+1
      if j+dp[i][j]-1>=i:
        dp[i][j]=i-j

A=[]
for i in range(N):
  for j in range(i):
    A.append(dp[i][j])

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

# coding: utf-8
from collections import deque
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    D = [[float("inf") for _ in range(N)] for _ in range(N)]
    D[X][Y] = 1
    D[Y][X] = 1
    queue = deque([[X, Y]])
    visited = [[False for _ in range(N)] for _ in range(N)]
    visited[X][Y] = True 
    while queue:
        x,y = queue.popleft()
        for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
            nx, ny = x+i, y+j
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
            if visited[nx][ny]:
                continue
            else:
                visited[nx][ny] = True
                D[nx][ny] = min(abs(ny-nx), D[x][y]+1)
                queue.append([nx, ny])
    ans = [0 for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            v = D[i][j]
            ans[v-1] += 1
    print(*ans[:-1], sep="\n")
main()


### FIXED CODE ###

# coding: utf-8
from collections import deque
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
D = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        D[i][j] = abs(j-i)
        D[j][i] = abs(j-i)
D[X][Y] = 1
D[Y][X] = 1
# print(*D, sep="\n")
queue = deque([[X, Y]])
visited = [[False for _ in range(N)] for _ in range(N)]
visited[X][Y] = True 
while queue:
    x,y = queue.popleft()
    for i, j in zip([1, 0, -1, 0], [0, 1, 0, -1]):
        nx, ny = x+i, y+j
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        if visited[nx][ny]:
            continue
        else:
            visited[nx][ny] = True
            D[nx][ny] = min(D[nx][ny], D[x][y]+1)
            queue.append([nx, ny])
# print(*D, sep="\n")
ans = [0 for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(i+1, N):
        # cnt += 1
        v = D[i][j]
        # print(i,j, v)
        ans[v-1] += 1
print(*ans[:-1], sep="\n")
### BUGGY CODE ###

#C - Traveling Salesman around Lake WA(ヒント)
K,N = map(int,input().split())
A = list(map(int, input().split()))

A[N+1:] = A#Aを二回繰り返して円を表現
A_reverse = reversed(A)

distance_list = []
for i in range(N):#スタート地点の数
    distance = 0
    for j in range(N-1):#道の数
        distance += abs(A[i+1] - A[i])#道の距離
    distance_list.append(distance)
for k in range(N):#逆回りについて
    distance = 0
    for j in range(N-1):
        distance += abs(A[i+1] - A[i])
    distance_list.append(distance)
print(min(distance_list))

### FIXED CODE ###

#C - Traveling Salesman around Lake WA(ヒント)
K,N = map(int,input().split())
A = list(map(int, input().split()))

A[N+1:] = [A[0] + K]#Aを二回繰り返して円を表現

distance_list = []
for i in range(N):
    distance = abs(A[i] - A[i+1])
    distance_list.append(distance)
distance_list.remove(max(distance_list))
print(sum(distance_list))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def main():
    n, q = inputAsIntArr()
    s = input()

    num_acs = []
    for i in range(q):
        li, ri = inputAsIntArr()

        num_ac = 0
        for j in range(li-1, ri-1):
            if s[j] != 'A':
                continue
            if s[j+1] == 'C':
                num_ac += 1
                j += 1
        num_acs += [str(num_ac)]

    print("\n".join(num_acs))


def inputAsIntArr():
    return [int(i) for i in input().split(' ')]


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split())
    s = input()

    # 累積出現数を格納: 指定される番号が1始まりなのでズラして格納
    p = [0] * (n+1)
    for i in range(n):
        p[i+1] = p[i] + (1 if s[i:i+2] == "AC" else 0)

    for i in range(q):
        l, r = map(int, input().split())
        # 終端(=l-1)から始端-1(=r-1)の累積出現数を引いた数が指定区間内での出現回数
        print(p[r-1] - p[l-1])


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

from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for b in range(max(1,g))] for g in range(max(1,r))] for r in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(max(1,r)):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][r][g] >= 0:
        dp[r+1][r][g] += v
        dp[r+1][r][g] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans%mod)


### FIXED CODE ###

from itertools import permutations
n,m = map(int,input().split())
lrx = [list(map(int,input().split())) for i in range(m)]
lrx.sort(key = lambda x:x[1])
mod = 10**9+7
dp = [[[0 for b in range(max(1,g))] for g in range(max(1,r))] for r in range(n+1)]
dp[0][0][0] = 1
for l,r,t in lrx:
  if t != 1:
    for g in range(l):
      for b in range(max(1,g)):
        dp[r][g][b] = -1
  if t != 2:
    for g in range(l,r):
      for b in range(l):
        dp[r][g][b] = -1
  if t != 3:
    for g in range(l,r):
      for b in range(l,g):
        dp[r][g][b] = -1

for r in range(n):
  for g in range(max(1,r)):
    for b in range(max(1,g)):
      v = dp[r][g][b]
      if v == -1:
        continue
      if dp[r+1][g][b] >= 0:
        dp[r+1][g][b] += v
        dp[r+1][g][b] %= mod
      if dp[r+1][r][b] >= 0:
        dp[r+1][r][b] += v
        dp[r+1][r][b] %= mod
      if dp[r+1][r][g] >= 0:
        dp[r+1][r][g] += v
        dp[r+1][r][g] %= mod
ans = 0
for i in range(n):
  for j in range(max(1,i)):
    if dp[n][i][j] >= 0:
      ans += dp[n][i][j]
      ans %= mod
print(ans%mod)