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

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))

waru=10**9+7

ans=1

dic_s={}
dic_t={}

for i in range(2**n):
    li=0
    for j in range(n):
        if (i>>j) & 1:
            li*=10
            li+=s[j]
    if li in dic_s.keys():
        dic_s[li]+=1
    else:
        dic_s[li]=1

for i in range(2**m):
    li=0
    for j in range(m):
        if (i>>j) & 1:
            li*=10
            li+=t[j]
    if li in dic_t.keys():
        dic_t[li]+=1
    else:
        dic_t[li]=1

count=0
for i in dic_s.keys():
    if i in dic_t.keys():
        count+=dic_s[i]*dic_t[i]

print(count%waru)

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))

dp=[[0]*(m+1) for i in range(n+1)]
sumij=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=sumij[i][j]+1
        else:
            dp[i+1][j+1]=0
        sumij[i+1][j+1]=(sumij[i][j+1]+sumij[i+1][j]-sumij[i][j]+dp[i+1][j+1])%mod
print((sumij[-1][-1]+1)%mod)
# print(dp)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
for i in range(m):
  a,b=map(int,input().split())
  l=[i for i in range(a,b+1)]
  if i==0:
    cards=l
  else:
    cards=list(set(l)&set(cards))
print(len(cards))

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
leftgate=[]
rightgate=[]
for i in range(m):
  l,r=map(int,input().split())
  leftgate.append(l)
  rightgate.append(r)
if (min(rightgate)-max(leftgate))>-1:
  print(min(rightgate)-max(leftgate)+1)
else:
  print(0)
### BUGGY CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

S = input()
Q = int(input())

Queries = []
for _ in range(Q):
    Queries.append(list(input().split()))
    
for Query in Queries:
    T = int(Query[0])
    if T == 1:
        S = S[::-1]
    else:
        F = int(Query[1])
        C = Query[2]
        if F == 1:
            S = C + S
        else:
            S = S + C
print(S)


### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
from collections import deque

S = input()
Q = int(input())

# Queries = []
# for _ in range(Q):
#     Queries.append(list(input().split()))
    
# for Query in Queries:
#     T = int(Query[0])
#     if T == 1:
#         S = S[::-1]
#     else:
#         F = int(Query[1])
#         C = Query[2]
#         if F == 1:
#             S = C + S
#         else:
#             S = S + C
# print(S)

swap = 1
head = deque()
tail = deque()
for _ in range(Q):
    Query = list(input().split())

    if Query[0] == "1":
        swap *= -1
    
    else:
        F, C = Query[1], Query[2]
        if F == "1":
            if swap == 1:
                head.appendleft(C)
            else:
                tail.append(C)
        else:
            if swap == -1:
                head.appendleft(C)
            else:
                tail.append(C)         


print(("".join(head) + S + "".join(tail))[::swap])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, w, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
CC = [[] for i in range(h)]
for i in range(m):
    CC[C[i][0]-1].append(C[i][1]-1)

for i in range(h):
    CC[i].sort()

A = [0] * h
B = [0] * w
for i in range(m):
    A[C[i][0]-1] += 1
    B[C[i][1]-1] += 1

# ans = 0
# for i in range(m):
#     ans = max(ans, A[C[i][0]-1] + B[C[i][1]-1] - 1)

D = [[A[i], i] for i in range(h)]
E = [[B[i], i] for i in range(w)]
D.sort(reverse=True)
E.sort(reverse=True)

# print(D,E)

from bisect import bisect
# if not ([D[0][1]+1, E[0][1]+1] in C):
#     # print("r1")
#     ans = D[0][0] + E[0][0]
# else:
ans = 0
aa = D[0][0] + E[0][0]
co = 0
F = []

for i in range(h):
    for j in range(w):
        if D[i][0] + E[j][0] == aa:
            F.append([D[i][1], E[j][1]])
            co += 1
        else:
            break
    # if co > m:
    #     break
# if co > m:
#     # print("r2")
#     ans = D[0][0] + E[0][0]
else:
    ha = 0
    # print(F)
    # print(CC)
    for i in range(len(F)):
        ind = bisect(CC[F[i][0]], F[i][1])
        if ind==0 or (ind >= 1 and CC[F[i][0]][ind-1] != F[i][1]):
            # print(CC[ind-1], F[i][1])
            ha = 1
            break
    if ha == 1:
        # print("r3")
        ans = D[0][0] + E[0][0]
    else:
        # print("m1")
        ans = D[0][0] + E[0][0] - 1
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
CC = [[] for i in range(h)]
for i in range(m):
    CC[C[i][0]-1].append(C[i][1]-1)

for i in range(h):
    CC[i].sort()

A = [0] * h
B = [0] * w
for i in range(m):
    A[C[i][0]-1] += 1
    B[C[i][1]-1] += 1

# ans = 0
# for i in range(m):
#     ans = max(ans, A[C[i][0]-1] + B[C[i][1]-1] - 1)

D = [[A[i], i] for i in range(h)]
E = [[B[i], i] for i in range(w)]
D.sort(reverse=True)
E.sort(reverse=True)

# print(D,E)

from bisect import bisect
if not ([D[0][1]+1, E[0][1]+1] in C):
    # print("r1")
    ans = D[0][0] + E[0][0]
else:
    ans = 0
    aa = D[0][0] + E[0][0]
    co = 0
    F = []

    for i in range(h):
        for j in range(w):
            if D[i][0] + E[j][0] == aa:
                F.append([D[i][1], E[j][1]])
                co += 1
            else:
                break
        if co > m:
            break
    if co > m:
        # print("r2")
        ans = D[0][0] + E[0][0]
    else:
        ha = 0
        # print(F)
        # print(CC)
        for i in range(len(F)):
            ind = bisect(CC[F[i][0]], F[i][1])
            if ind==0 or (ind >= 1 and CC[F[i][0]][ind-1] != F[i][1]):
                # print(CC[ind-1], F[i][1])
                ha = 1
                break
        if ha == 1:
            # print("r3")
            ans = D[0][0] + E[0][0]
        else:
            # print("m1")
            ans = D[0][0] + E[0][0] - 1
print(ans)
### BUGGY CODE ###

#くじ引き

import numpy
import re
import math

def calc_max_num(int_list):
	"""
	listから最大操作回数を算出
	:param int_list:
	:return:
	"""
	count = 0
	even_flag = False
	while True:
		for i in int_list:
			if i % 2 == 1:
				even_flag = True
		if even_flag is True:
			break
		else:
			for i in int_list:
				i /= 2
			count += 1
	return count


def main():
	"""
	テストコード実行
	:return:
	"""
	line = input()
	int_num = int(line)
	line = input()
	line_list = re.split(" +", line)
	int_list = [int(s) for s in line_list]
	print(calc_max_num(int_list))


if __name__ == '__main__':
	main()


### FIXED CODE ###

#くじ引き

import numpy
import re
import math

def main():
	"""
	テストコード実行
	:return:
	"""
	n = input()
	a = list(map(int, input().split()))
	ans = float("inf") #無限大を挿入
	for i in a:
		# 2値で変換した際の右に並ぶ0の数が2で割ることのできる回数
		# rfindで1の値を持つ最大インデックスを求め、その分だけ引く
		# 計算した回数の最小値を求める
		ans = min(ans, len(bin(i)) - bin(i).rfind("1") - 1)
	print(round(ans))

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

import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N=int(input())
A=list(map(int,input().split()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

gcd = 1
for key,val in d.items():
    gcd = gcd*pow(key,val)

ans = 0
for a in A:
    ans = (ans+gcd//a)%m
print(ans)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    i=2
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])
            
    for i in range(3, int(-(-n**0.5//1))+1,2):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])    

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N=int(input())
A=list(map(int,input().split()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

gcd = 1
for key,val in d.items():
    gcd = gcd*pow(key,val)

ans = 0
for a in A:
    ans = ans+gcd//a
print(ans%m)
### BUGGY CODE ###

s = input().strip()

DIV = 10**9 + 7
digit = 1
log = {}

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log[0] = {t: int(t < 10) for t in range(13)}
        else:
            log[0] = {t: int(t == int(c)) for t in range(13)}
    else:
        log[i] = {t: 0 for t in range(13)}
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in log[i - 1].items():
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt) % DIV
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in log[i - 1].items():
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt) % DIV
    digit = (digit * 10) % 13

print(log[len(s) - 1][5] % (10**9 + 7))

### FIXED CODE ###

s = input().strip()

DIV = 10**9 + 7
new = list(range(13))
old = None

c = s[-1]
if c == '?':
    old = [int(t < 10) for t in range(13)]
else:
    c = int(c)
    old = [int(t == c) for t in range(13)]

digit = 10
for i, c in enumerate(reversed(s[:-1])):
    for j in range(13):
        new[j] = 0
    if c == '?':
        for m in range(10):
            for mod, cnt in enumerate(old):
                shifted = (mod + m * digit) % 13
                new[shifted] += cnt
    else:
        c = int(c)
        for mod, cnt in enumerate(old):
            shifted = (mod + c * digit) % 13
            new[shifted] += cnt
    for j in range(13):
        new[j] %= DIV
    new, old = old, new
    digit = (digit * 10) % 13

print(old[5])
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(list)
        for i in range(self.n):
            d[self.find(i)] += [i]
        for i in d.keys():
            d[i].sort()
            d[i] = deque(d[i])
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = p[i]
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))



def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    for i in range(N):
        tmp = p[i]
        if not uf.same(tmp,i):continue
        else:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

import fractions
import sys

lcm = a[0]//2

for i in range(1, N):
    lcm = lcm * (a[i]//2) // fractions.gcd(lcm, a[i]//2)

    
count_list = []
count = 0
for i in range(N):
    while a[i] % 2 == 0:
        count += 1
        a[i] = a[i] // 2
    count_list.append(count)
    count = 0
    
for i in range(N):
    if count_list[i] != sum(count_list)/N:
        print(0)
        sys.exit()
    

print(-(-(M//lcm) // 2))

### FIXED CODE ###

from math import gcd, ceil
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i // 2 for i in a]
l = 1
for i in a:
    l *= i // gcd(l, i)
for i in a:
    if l // i % 2 == 0:
        print(0)
        exit()
print(ceil((m // l) / 2))
### BUGGY CODE ###

import sys
# input = sys.stdin.readline

def main():
  s = int(input())
  x1, y1, y2 = 0, 0, 0
  i = 1
  while i*i<=pow(10, 9):
    if s % (i-x1) == 0:
      if s // (i-x1) <= pow(10, 9):
        print("%d %d %d %d %d %d" % (x1, y1, i, y2, i-1, s//(i-x1)))
        sys.exit(0)


if __name__ == '__main__':
  main()


### FIXED CODE ###

def main():
  s = int(input())
  ppp = pow(10, 9)
  x = (ppp-s%ppp)%ppp
  y = (s+x) // ppp
  print("%d %d %d %d %d %d" % (0, 0, ppp, 1, x, y))


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

import re

s = input()
pattern = "(01)|(10)"
count = 0
diff = 1

while diff:
    ssub = re.sub(pattern, "", s)
    diff = len(s) - len(ssub)
    count += diff
    s = ssub


print(count)


### FIXED CODE ###

import re

s = input()
zero = re.findall("0", s)
one = re.findall("1", s)
print(2 * min(len(zero), len(one)))
### BUGGY CODE ###

#心折れた

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1
		return

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

vx = sorted(x, key=lambda x: x[1])
vy = sorted(y, key=lambda x: x[1])

edges = []
uf = UnionFind(n)

for i in range(n - 1):
	if vx[i][1] == vx[i + 1][1]:
		uf.union(vx[i][0], vx[i + 1][0])
	else:
		edges.append([vx[i][0], vx[i + 1][0], vx[i + 1][1] - vx[i][1]])

	if vy[i][1] == vy[i + 1][1]:
		uf.union(vy[i][0], vy[i + 1][0])
	else:
		edges.append([vy[i][0], vy[i + 1][0], vy[i + 1][1] - vy[i][1]])

edges = sorted(edges, key=lambda x: x[2], reverse=True)
#print(edges)

ans = 0

while edges != []:
	e = edges.pop()
	if uf.find(e[0]) != uf.find(e[1]):
		uf.union(e[0], e[1])
		ans += e[2]

print(ans)

### FIXED CODE ###

import heapq
import sys
sys.setrecursionlimit(10 ** 7)

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]
		self.count = 0

#	def find(self, x):
#		while self.table[x] >= 0:
#			x = self.table[x]
#		return x

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x])
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1

			self.count += 1
			return True
		return False

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

vx = sorted(x, key=lambda x: x[1])
vy = sorted(y, key=lambda x: x[1])

edges = []
uf = UnionFind(n)

for i in range(n - 1):
	if vx[i][1] == vx[i + 1][1]:
		uf.union(vx[i][0], vx[i + 1][0])
	else:
		heapq.heappush(edges, (vx[i + 1][1] - vx[i][1], vx[i][0], vx[i + 1][0]))

	if vy[i][1] == vy[i + 1][1]:
		uf.union(vy[i][0], vy[i + 1][0])
	else:
		heapq.heappush(edges, (vy[i + 1][1] - vy[i][1], vy[i][0], vy[i + 1][0]))


#edges = sorted(edges, key=lambda x: x[2], reverse=True)
#print(edges)

ans = 0

while edges != []:
	e = heapq.heappop(edges)
	if uf.union(e[1], e[2]):
		ans += e[0]
	if uf.count == n - 1:
		break

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

N = int(input())
A = list(map(int, input().split()))
M = 10**9+7
ans = 0

for i in range(61):
    b = 1<<i
    count = 0
    for a in A:
        c = a & b
        if c != 0:
            count += 1
    ans += b*count*(N-count)

print(ans%M)


### FIXED CODE ###

N,*A=map(int,open(0).read().split())
print(sum((b:=1<<i)*(z:=sum(1 for a in A if a&b==0))*(N-z)%(mod:=10**9+7) for i in range(60))%mod)
### BUGGY CODE ###

from bisect import bisect,insort
n,k = (int(i) for i in input().split())
a = [int(input())-k for i in range(n)]
b = [[0,0]]
for i in range(n): b.append([-(a[i]-b[-1][0]),-(i+1)])
b.sort()
q,ans,num = [-b[0][1]],0,1
for i,j in b[1:]:
	c = bisect(q,-j)
	ans+=num-c
	num+=1
	insort(q,-j,c,c)
print(ans)

### FIXED CODE ###

n,k = (int(i) for i in input().split())
a = [int(input())-k for i in range(n)]
b = [[0,0]]
for i in range(n): b.append([b[-1][0]+a[i],i+1])
b.sort()
num,c = 1,[[b[0][1],1]]
for i in range(1,n+1):
	if b[i][0]!=b[i-1][0]: num+=1
	c.append([b[i][1],num])
c,d,ans = sorted(c),[0]*(n+2),0
def add(i):
	while i<=n+1:
		d[i] += 1
		i += i & -i
def get(i):
	s = 0
	while i:
		s += d[i]
		i -= i & -i
	return s
for i,j in c:
	ans+=get(j)
	add(j)
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    mod = 10**9 + 7
    b = [0] * 60
    for ai in a:
        for k in range(60):
            if ai == 0:
                break
            b[k] += ai % 2
            ai //= 2
    c = 0
    for k in range(60):
        c = (c + b[k] * (n - b[k]) * pow(2, k, mod)) % mod
    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    mod = 10**9 + 7
    c = 0
    for kk in range(k):
        h, l = 0, 0
        for ai in a:
            if ai // 2**kk % 2:
                h += 1
            else:
                l += 1
        kc = h * l * pow(2, kk, mod) % mod
        c = (c + kc) % mod
    print(c)

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

n = int(input())
a = list(map(int,input().split()))
if n % 2 == 1:
    b = []
    for i in range(n//2):
        b = [a[2*i]]+b
        b.append(a[2*i+1])
    b = [a[-1]]+b
    print(' '.join(map(str,b)))
else:
    b = []
    for i in range(n//2):
        b.append(a[2*i])
        b = [a[2*i+1]]+b
    print(' '.join(map(str,b)))

### FIXED CODE ###

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

if n % 2 == 1:
    b = a[::2]
    c = a[1::2]
    b.reverse()
    d = b+c
    print(' '.join(map(str,d)))
else:
    b = a[::2]
    c = a[1::2]
    c.reverse()
    d = c+b
    print(' '.join(map(str,d)))
### BUGGY CODE ###

S = input()
l = len(S)
ans = 0
for i in range(l+1):
    for j in range(l-i):
        if int(S[j:i+j+1])%2019 == 0:
            ans += 1
print(ans)

### FIXED CODE ###

P = 2019
S = input()
N = len(S)
res = 0
 
if P in [2,5]:
    for i in range(N):
        if int(S[i])% P == 0:
            res += i+1
else:
    dic = {0:1}
    t1 = 0
    t2 = 1
    for i in range(N):
        t2 = (10*t2) % P
        t1 = (int(S[N-1-i])*t2 + t1) % P
        if t1 in dic:
            res += dic[t1]
            dic[t1] += 1
        else:
            dic[t1] = 1
 
print(res)
### BUGGY CODE ###

s = input()
q = int(input())
query = []
for i in range(q):
    query.append(list(map(str, input().split())))
i = 0
rev = 0
while i < q:
    if len(query[i]) == 1:
        if i < q - 1:
            if len(query[i + 1]) == 1:
                i += 2
                continue
        rev = (rev + 1) % 2
        i += 1
    else:
        if rev == 0:
            if int(query[i][1]) == 1:
                s = query[i][2] + s
                i += 1
            else:
                s = s + query[i][2]
                i += 1
        else:
            if int(query[i][1]) == 2:
                s = query[i][2] + s
                i += 1
            else:
                s = s + query[i][2]
                i += 1
if rev == 1:
    s = s[::-1]
print(s)            

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
sa = []
sb = []
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
        else:
            if query[i][1] == '2':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
ssa = ''.join(sa)
ssa = ssa[::-1]
ssb = ''.join(sb)
ss = ssa + s + ssb
if rev == 1:
    ss = ss[::-1]
print(ss)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import re
pattern = 'AC'
n, q = map(int, raw_input().split())
s = raw_input()

x = [raw_input() for i in range(q)]

result = re.finditer(pattern, s)

ac = np.zeros(len(s))
count = 0
for match in result:
#    count += 1
    ac[match.span()[0]] = 1

#print ac



for d in x:
    r = d.split(' ')
    start = int(r[0])-1
    end = int(r[1])
    wa = np.sum(ac[start:end] == 1)
#    wa = ac[start:end].count(1)
#    wa = sum(ac[start:end])
    if ac[end-1]==1: wa = wa-1
    print int(wa)


### FIXED CODE ###

#!/usr/bin/env python3
N, Q = map(int, input().split())
S = input()
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append([l,r])

A = [0]

cnt = 0
for i in range(1, len(S)):
    if S[i-1:i+1] == 'AC':
        cnt += 1
    A.append(cnt)

for l, r in LR:
    print(A[r-1] - A[l-1])