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

from math import factorial
n,m,K=map(int,input().split())
ans=0
def comb(n,r):
    return factorial(n)//factorial(n-r)//factorial(r)
for i in range(3,n+m+1):
    t=0
    for j in range(max(1,i-n),i):
        if(j>m):
            ans+=t*(i-2)
            break
        k=i-j
        if(j==1 or k==1):
            t+=(m-j+1)*(n-k+1)
        else:
            t+=(m-j+1)*(n-k+1)*2
    else:
        ans+=t*(i-2)
print((ans*comb(n*m-2,K-2))%(10**9+7))

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=10**9+7
x=1
y=1
for i in range(1,k-1):
    y*=i
    y%=mod
for i in range(k-2):
    x*=n*m-2-i
    x%=mod
x*=pow(y,mod-2,mod)
x%=mod
def f(n,m):
    s=0
    for i in range(1,n):
        s+=i*(n-i)
        s%=mod
    return s*m*m%mod
print((f(n,m)+f(m,n))*x%mod)
### BUGGY CODE ###

import bisect

n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        else:
            ans += i - bisect.bisect_right(l[:i-1],(l[j]-l[i]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
l = sorted([int(i) for i in input().split()])
ans = 0
for i in range(1,n-1):
    tmp=0
    for j in range(i+1,n):
        if l[j] - l[i] >= l[i-1]:
            break
        else:
            for k in range(tmp,i):
                if l[tmp] > l[j]-l[i]:
                    ans += i-tmp
                    break
                elif l[k] > l[j]-l[i]:
                    tmp = k
                    ans += i-tmp
                    break
print(ans)
### BUGGY CODE ###

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

K = [0] * 61
for a in A:
    L = list(format(a, 'b').zfill(61))
    M = list(int(s) for s in L)
    for i in range(61):
        K[i] += M[i]

cnt = []
for i in range(61):
    cnt.append(K[i] * (N - K[i]))
cnt.reverse()

ans = 0
for i in range(61):
    ans += (2 ** i) * cnt[i] % MOD

print(ans % MOD)

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int,input().split())))
MOD = 10 ** 9 + 7
ans = 0

for i in range(61):
    cnt = np.count_nonzero(A & 1)
    ans += (2 ** i) * cnt * (N - cnt)
    A >>= 1

print(ans % MOD)
### BUGGY CODE ###

from itertools import *
from collections import *
from sys import *
input=stdin.readline
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if (nx,ny) not in q:
                    q.append((nx,ny))
aa=[]
for i in range(h):
    aa.append(max(ans[i]))
print(max(aa))


### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


@njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N, np.int64)
    dp[0] = 1
    for i in range(N):
        steps = steps[steps < N]
        dp[steps] += dp[i]
        dp[steps] %= mod
        steps += 1

    return dp[N - 1]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps += list(range(l, r + 1))

steps = np.array(steps)

print(main(N, steps))

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

# import numba
# from numba import njit, b1, i4, i8, f8

input = sys.stdin.readline
mod = 998244353


def I():
    return int(input())


def MI():
    return map(int, input().split())


# @njit((i8, i8[:]), cache=True)
def main(N, steps):
    dp = np.zeros(N + 1, np.int64)
    dpsum = np.zeros(N + 1, np.int64)
    dp[1] = 1
    dpsum[1] = 1
    for i in range(2, N + 1):
        for l, r in steps:
            li = i - r
            ri = i - l
            if ri < 0:
                continue
            li = max(li, 1)
            dp[i] += dpsum[ri] - dpsum[li - 1]
            dp[i] %= mod
        dpsum[i] = dpsum[i - 1] + dp[i]
        dpsum[i] %= mod

    return dp[N]


N, K = MI()

steps = []
for _ in range(K):
    l, r = MI()
    steps.append((l, r))


print(main(N, steps))
### BUGGY CODE ###

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

Asum = sum(A)

sumdiflist = []

for i in range(N-1):
  B = A[:i+1]
  Bsum = sum(B) #前半の和
  temp = Asum - Bsum #後半の和
  sumdif = Bsum - temp
  if(sumdif<0):
    sumdif = -sumdif
  sumdiflist.append(sumdif)

print(min(sumdiflist))

### FIXED CODE ###

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

Asum = sum(A)
sumdiflist = []

temp = 0
for i in range(N-1):
  temp += A[i]
  sumdif = 2*temp - Asum
  if(sumdif<0):
    sumdif = -sumdif
  sumdiflist.append(sumdif)

print(min(sumdiflist))
### BUGGY CODE ###

from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを作る
    adj = defaultdict(list)
    for a in DISTINCT_A:
        for e in range(MAX_EXP + 1):
            b = pow2[e] - a
            if a <= b:
                break
            if counter[b] == 0:
                continue
            adj[a].append(b)
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        for b in adj[a]:
            cnt = min(counter[a], counter[b])
            ans += cnt
            counter[a] -= cnt
            counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MAX_EXP = 30  # 2**30 < 2 * (10 ** 9) < 2**31
    pow2 = [1] * (MAX_EXP + 1)
    for e in range(1, MAX_EXP + 1):
        pow2[e] = 2 * pow2[e - 1]
    counter = defaultdict(int)
    for a in A:
        counter[a] += 1
    DISTINCT_A = list(counter.keys())
    DISTINCT_A.sort(reverse=True)  # 大きい順に並べておく
    # 和が2のべき乗になるペアの間をedgeで結んだグラフを考え
    # ノードの値が大きい順に貪欲にペアを作っていく
    ans = 0
    for a in DISTINCT_A:
        b = pow2[a.bit_length()] - a
        if counter[b] == 0:
            continue
        cnt = min(counter[a], counter[b])
        ans += cnt
        counter[a] -= cnt
        counter[b] -= cnt
    # 最後に2のべき乗のノードはそれ単体でペアを作れるので、その分を足す
    for e in range(MAX_EXP + 1):
        a = pow2[e]
        ans += counter[a] // 2
    print(ans)


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

n, q = map(int, input().split())
s = input()
LR = []
for i in range(q):
  LR.append(list(map(int, input().split())))
  num = s[LR[i][0]-1:LR[i][1]].count('AC')
  print(num)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
A = [0 for _ in range(n+1)]
for i in range(n-1):
  A[i+1] = A[i] + (1 if s[i:i+2] == 'AC' else 0)
for j in range(q):
  l, r = map(int, input().split())
  print(A[r-1] - A[l-1])
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[a-1 for a in A]
Appeared=[]
k=0
location=0
T=0
T_List=[]
while k<=K:
    k+=1
    Appeared.append(location)
    location=A[location]
    if location in Appeared:
        T=k-Appeared.index(location)
        T_List=Appeared[k-T:k]
        break
if len(T_List)==0:
    print(Appeared[-1]+1)
else:
    Destination=(K-(k-T-1))%T
    print(T_List[Destination-1]+1)


### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A=[a-1 for a in A]
Arrived=[-1 for i in range(N)]
Appeared=[]
k=0
location=0
T=0
T_List=[]
while k<=K:
    k+=1
    Arrived[location]=k-1
    Appeared.append(location)
    location=A[location]
    if Arrived[location]!=-1:
        T=k-Arrived[location]
        T_List=Appeared[k-T:k]
        break
if len(T_List)==0:
    print(Arrived.index(k-1)+1)
else:
    Destination=(K-(k-T-1))%T
    print(T_List[Destination-1]+1)
### BUGGY CODE ###

n, k = map(int,input().split())
A = [int(i) for i in input().split()]
scores = []
hyotei = 1

for i in range(0,n-k+1):
    for j in range(i,i+k):
        hyotei *= A[j]
    scores.append(hyotei)
    hyotei = 1
    
for i in range(n-k):
    if scores[i+1]>scores[i]:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

n, k = map(int,input().split())
A = [int(i) for i in input().split()]

for i in range(n-k):
    if A[i]<A[i+k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
visitSpot = list(map(int, input().split()))
listForAnswer =[]
index=0
while index<len(visitSpot):
    index2=0
    sum=0
    while index2<len(visitSpot):
        if index2 ==index:
            index2+=1
        elif sum ==0:
            sum+=(max(visitSpot[index2], 0)-min(visitSpot[index2],0))
            index2+=1
        else:
            if index2-1 != index:
                sum+=(max(visitSpot[index2], visitSpot[index2-1])-min(visitSpot[index2],visitSpot[index2-1]))
            else:
                sum+=(max(visitSpot[index2], visitSpot[index2-2])-min(visitSpot[index2],visitSpot[index2-2]))
                flag =0
            index2+=1
    if index2-1!=index:
        sum+=(max(visitSpot[index2-1], 0)-min(visitSpot[index2-1],0))
    else:
        sum+=(max(visitSpot[index2-2], 0)-min(visitSpot[index2-2],0))
    listForAnswer.append(sum)
    index+=1

for ans in listForAnswer:
    print(ans)

### FIXED CODE ###

n = int(input())
listA = list(map(int, input().split()))
sumOriginal =0
index =0
while index<len(listA):
    if index == 0:
        sumOriginal+=(max(listA[index], 0)-min(listA[index], 0))
    elif index == len(listA)-1:
        sumOriginal+=(max(listA[index], 0)-min(listA[index], 0))
        sumOriginal+=(max(listA[index], listA[index-1])-min(listA[index], listA[index-1]))
    else:
        sumOriginal+=(max(listA[index], listA[index-1])-min(listA[index], listA[index-1]))
    index+=1

index2=0
listForAnswer =[]
while index2<len(listA):
    sumAnswer=0
    if index2 ==0:
        sumAnswer = sumOriginal-(max(listA[index2], 0)-min(listA[index2], 0))
        sumAnswer-=(max(listA[index2], listA[index2+1])-min(listA[index2], listA[index2+1]))
        sumAnswer+=(max(listA[index2+1], 0)-min(listA[index2+1], 0))
    elif index2 ==len(listA)-1:
        sumAnswer =sumOriginal-(max(listA[index2], 0)-min(listA[index2], 0))
        sumAnswer-=(max(listA[index2], listA[index2-1])-min(listA[index2], listA[index2-1]))
        sumAnswer+=(max(listA[index2-1], 0)-min(listA[index2-1], 0))
    else:
        sumAnswer =sumOriginal-(max(listA[index2], listA[index2+1])-min(listA[index2], listA[index2+1]))
        sumAnswer-=(max(listA[index2], listA[index2-1])-min(listA[index2], listA[index2-1]))
        sumAnswer+=(max(listA[index2-1], listA[index2+1])-min(listA[index2-1], listA[index2+1]))
    listForAnswer.append(sumAnswer)
    index2+=1

for ans in listForAnswer:
    print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        a = j - i + 1 - K
        for m in XY[i:j + 1]:
            if y_min <= m[1] <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val in enumerate(XY[:N - 1]):
        a = val[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            for k in range(N):
                c = XY[k][1]
                for l in range(N):
                    d = XY[l][1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

n=int(input())
a=[int(_) for _ in input().split()]
ans=0
for i in range(n):
    t=a[i]
    for j in range(i,n):
        ans+=a[j]==j-i-t
print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=[int(_) for _ in input().split()]
l=[a[i]+i for i in range(n)]
r=[i-a[i] for i in range(n)]
c=collections.Counter(r)
ans=0
for i in range(n):ans+=c[l[i]]
print(ans)
### BUGGY CODE ###

A, B = map(int, input().split())

def cf(x1,x2):
    cf=[]
    for i in range(2,min(x1, x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf

import math
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

list = [1]
list.extend(cf(A,B))
cnt = 1
for i in list:
    if is_prime(i) == True:
        cnt += 1
print(cnt)

### FIXED CODE ###

A, B = map(int, input().split())
 
def gcd(a, b):  # a,bの最大公約数
    while b:
        a, b = b, a % b
    return a

def factorization(n):  # 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 == []: # ｎが1のとき
        arr.append([n, 1])
    return arr
 
g = gcd(A, B) 
ans = len(factorization(g))

if g != 1:
    ans += 1
print(ans)
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
A = [0] + [int(i) for i in input().split()]
# first study the cycle of A
cycle = [A[1]]
i = A[1]
while A[i] not in cycle:
    cycle.append(A[i])
    i = A[i]
cycle.append(A[i])
interest_ind = cycle.index(cycle[-1])
first_part = cycle[:interest_ind]
second_part = cycle[interest_ind:-1]
p = len(second_part)
k -= 1
if k < interest_ind:
    print(first_part[k])
else:
    k -= interest_ind
    k %= p
    print(second_part[k])

### FIXED CODE ###

n, k = [int(i) for i in input().split()]
A = [0] + [int(i) for i in input().split()]
# first study the cycle of A
cycle = [A[1]]
i = A[1]
visited = set(cycle)
while A[i] not in visited:
    cycle.append(A[i])
    visited.add(A[i])
    i = A[i]
interest_ind = cycle.index(A[i])
second_part = cycle[interest_ind:]
p = len(cycle) - interest_ind
k -= 1
if k < interest_ind:
    print(cycle[k])
else:
    k -= interest_ind
    k %= p
    print(cycle[interest_ind + k])
### BUGGY CODE ###

import heapq

q = int(input())

nchange = 0
ming, maxg = [], []
heapq.heapify(ming)
heapq.heapify(maxg)
a = 0
b = 0
for i in range(q):
    qi = input()
    if qi[0] == '1':
        _, ai, bi = map(int, qi.split())
        b += bi
        nchange += 1
        if nchange % 2 == 1:
            if nchange == 1:
                x = ai
                continue
            Smax = -heapq.heappop(ming)
            Dmin = heapq.heappop(maxg)
            if Smax <= ai and ai <= Dmin:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, Dmin)
                x = ai
            elif ai < Smax:
                heapq.heappush(ming, -ai)
                heapq.heappush(maxg, Dmin)
                x = Smax
                a += Smax - ai
            else:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, ai)
                x = Dmin
                a += ai - Dmin
        else:
            heapq.heappush(ming, -min(x, ai))
            heapq.heappush(maxg, max(x, ai))
            a += abs(x - ai)
            x = -heapq.heappop(ming)
            heapq.heappush(ming, -x)
    else:
        print(x, a+b)

### FIXED CODE ###

import heapq

q = int(input())

nchange = 0
ming, maxg = [], []
heapq.heapify(ming)
heapq.heapify(maxg)
a = 0
b = 0
for i in range(q):
    qi = input()
    if qi[0] == '1':
        _, ai, bi = map(int, qi.split())
        b += bi
        nchange += 1
        if nchange % 2 == 1:
            if nchange == 1:
                x = ai
                continue
            Smax = -heapq.heappop(ming)
            Dmin = heapq.heappop(maxg)
            if Smax <= ai and ai <= Dmin:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, Dmin)
                x = ai
            elif ai < Smax:
                heapq.heappush(ming, -ai)
                heapq.heappush(maxg, Dmin)
                x = Smax
                a += Smax - ai
            else:
                heapq.heappush(ming, -Smax)
                heapq.heappush(maxg, ai)
                x = Dmin
                a += ai - Dmin
        else:
            heapq.heappush(ming, -min(x, ai))
            heapq.heappush(maxg, max(x, ai))
            a += abs(x - ai)
            x = -heapq.heappop(ming)
            heapq.heappush(ming, -x)
    else:
        print(x, a+b)
### BUGGY CODE ###

N,A,B = map(int, input().split())

arr = []
ans = 0

for i in range(N):
    y = i
    while y >= 1:
        arr.append(int(i % 10))
        i /= 10
    if sum(arr)>= A and sum(arr) <= B:
        ans += sum(arr)
        arr = []
    else:
        arr = []
        
ptint(ans)



### FIXED CODE ###


N, A, B = map(int,input().split())
ans = 0
arr = []
for y in range(N+1):
	i = y
	while i >= 1:
		arr.append(int(i % 10))
		i /= 10
	if sum(arr) <= B and sum(arr) >= A:
		ans += y
		arr = []
	else:
		arr = []

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

from itertools import accumulate
from operator import add


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

white_count = [0] * (w+1)
prev = [0] * (w+1)
for _ in range(h):
    line = iter('0'+input())
    cumsum_1d = accumulate(map(int, line))
    cumsum_2d = list(map(add, prev, cumsum_1d))
    prev = cumsum_2d
    white_count += cumsum_2d


def get_white(sy, sx, ny, nx):
    a = sy*(w+1) + sx
    b = sy*(w+1) + nx
    c = ny*(w+1) + sx
    d = ny*(w+1) + nx
    return white_count[d] - white_count[c] - white_count[b] + white_count[a]


ans = []
for pattern in range(2**(h-1)):
    dived = [0] + [y+1 for y in range(h-1) if (pattern>>y) & 1] + [h]
    slash_count = len(dived) - 2

    prev_x = 0
    for div_x in range(1, w + 1):
        white_include = 0
        for idx in range(len(dived)-1):
            prev_y = dived[idx]
            div_y = dived[idx+1]
            white = get_white(prev_y, prev_x, div_y, div_x)
            if white > white_include:
                white_include = white

        if white_include > k:
            slash_count += 1
            if prev_x == div_x - 1:
                break
            prev_x = div_x - 1

    else:
        ans.append(slash_count)

print(min(ans))


### FIXED CODE ###

h, w, k = map(int, input().split())
chocolate = ['0' + input() for _ in range(h)]

white_count = [[0] * (w+1)]
for line in chocolate:
    prev = white_count[-1]
    cumsum = []
    total = 0
    for color, count in zip(line, prev):
        if color == '1':
            total += 1
        cumsum.append(total + count)
    white_count.append(cumsum)

ans = []
for pattern in range(2**(h-1)):
    dived = []
    for y in range(h-1):
        if (pattern >> y) & 1:
            dived.append(y + 1)

    dived.append(h)
    slash_count = len(dived) - 1

    prev_x = 0
    for nx in range(1, w + 1):
        prev_y = 0
        possible = True
        for ny in dived:
            white = white_count[ny][nx] - white_count[prev_y][nx] - (white_count[ny][prev_x] - white_count[prev_y][prev_x])
            prev_y = ny
            if white <= k:
                continue
            else:
                slash_count += 1
                slash = nx - 1
                if prev_x == slash:
                    possible = False
                prev_x = slash
                break

        if not possible:
            break

    else:
        ans.append(slash_count)

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

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

As = []
for i in range(m):
  As.append(int(input()))

nums = [1]
if 1 in As:
  nums.append(0)
else:
  nums.append(1)
  
for i in range(2, n + 1):
  if i in As:
    nums.append(0)
  else:
    nums.append(nums[i-1] + nums[i-2])
    
print(nums[-1] % 1000000007)

### FIXED CODE ###

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

if m > 0:
  As = set(map(int, sys.stdin))
else:
  As = set()

nums = [0] * (n + 1)
nums[0] = 1
if 1 in As:
  pass
else:
  nums[1] = 1
  
for i in range(2, n + 1):
  if i in As:
    continue
  else:
    nums[i] = (nums[i-1] + nums[i-2]) % 1000000007
    
print(nums[-1])
### BUGGY CODE ###

import copy
n = int(input())
nums = []
for i in range(n):
  nums.append(int(input()))
#print(nums)  

for i in range(n):
  new_list = copy.copy(nums)
  del new_list[i]
  print(max(new_list))

### FIXED CODE ###

import copy
n = int(input())
nums = []
for i in range(n):
  nums.append(int(input()))  

nums_sorted = sorted(nums)  
biggest = nums_sorted[-1]
second_biggest = nums_sorted[-2]
max_ind = nums.index(biggest)

if nums.count(biggest) == 1:
  for i in range(n):
    if i == max_ind:
      print(second_biggest)
    else:
      print(biggest)
else:
  for i in range(n):
    print(biggest)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * (N+2)
cnt = 0

for i in range(1,N+1):
    #if S[i]+S[i+1]=='AC':
        #c[i+1]+=1
    c[i] = S[:i].count('AC')

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    print(c[j]-c[i])

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lr = [list(map(int,input().split()))for _ in range(Q)]
l = [lr[i][0] for i in range(Q)]
r = [lr[i][1] for i in range(Q)]
#print(lr)
#print(l)
#print(r)

c = [0] * N
cnt = 0

for i in range(N-1):
    if S[i:i+2] == 'AC':
        c[i+1]=c[i]+1
    else:
        c[i+1]=c[i]
    #c[i] = S[:i].count('AC')

#print(c)

for i,j in zip(l,r):
    #print(sum(c[:j])-sum(c[:i]))
    #l,r = map(int,input().split())
    print(c[j-1]-c[i-1])