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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement 
from heapq import heapify, heappop, heappush
def main():
    s = readline().rstrip().decode()
    K = int(readline())
    N = len(s)
    p = [int(i) for i in range(N)]
    hp = []
    heapify(hp)
    #K番目のsubsitringは長さがK以下のsubstrigの集合に必ず含まれる
    #K<=5であるから列挙される要素数は最大でも26^5(およそ10,000,000)
    for l, r in combinations_with_replacement(p, 2):
        sub = s[l:r+1]
        ln = len(sub)
        if ln <= K:  
            heappush(hp, sub)
    S = set()
    while len(hp)>0:
        v = heappop(hp)
        S.add(v)
        if len(S) == K:
            print(v)
            return 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(1000000)

def main():
    s = readline().rstrip().decode()
    K = int(readline())
    #sに含まれる文字を一文字ずつ抽出する.
    #ここで抽出した文字を組み合わせて辞書順に文字列を構成していく
    #K<=5だから高々26^5個の文字列を構成することになる
    l = sorted(list(set(s)))
    #cnd:=構成した文字列を辞書順に格納するリスト
    cnd = []
    #f(sub):=subから構成可能なK文字以下のSの部分文字列を構成する関数
    def f(sub):
        cnd.append(sub)
        if len(sub) < K: 
            #lから選んでsubに一文字追加する
            for i in l:
                nx = sub+i
                if nx in s:
                    f(nx)
    for i in l:
        f(i) 
    print(cnd[K-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
BC=list(list(map(int,input().split())) for  _ in range(M))
BC.sort(key=lambda x: x[1],reverse=True)

for b,c in BC:
    A.extend([c]*b)
    if len(A)>N*N:
        break
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC.sort(key = lambda x: -x[1])

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

b = list()
lenB = 0
for a in A:
    b.append(a)
    lenB += 1
    if len(set(b)) != lenB:
        b.pop(-1)
        b.remove(a)
        lenB -= 2
print(len(b))


### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

b = set()
lenB = 0
for a in A:
    b.add(a)
    lenB += 1
    if len(b) != lenB:
        b.remove(a)
        lenB -= 2
print(len(b))
### BUGGY CODE ###

N = int(input())

for i in range(1,N+1):
    ans = 0
    for x in range(1,101):
        if (x**2 > i):
            break
        for y in range(1,101):
            if (y**2 > i):
                break
            for z in range(1,101):
                if (z**2 > i):
                    break
                if x**2 + y**2 + z**2 + x*y + y*z + z*x == i:
                    ans += 1
    print(ans)


### FIXED CODE ###

import collections

N = int(input())

dp = []
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a <= N:
                dp.append(a)

dpc = collections.Counter(dp)

for i in range(1,N+1):
    print(dpc[i])
### BUGGY CODE ###

def resolve():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    dp = [dict() for _ in range(s + 1)]
    dp[0][0] = 1
    for i in a:
        for j in range(s - i, -1, -1):
            for k, v in dp[j].items():
                if k + 1 in dp[j + i]:
                    dp[j + i][k + 1] += v
                else:
                    dp[j + i][k + 1] = v
    ans = 0
    for k, v in dp[-1].items():
        ans += pow(2, n - k, mod) * v
    ans %= mod
    print(ans)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    modinv = pow(2, mod - 2, mod)
    dp = [0] * (s + 1)
    dp[0] = pow(2, n, mod)
    for i in a:
        for j in range(s - i, -1, -1):
            dp[j + i] += dp[j] * modinv
            dp[j + i] %= mod
    print(dp[-1])


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

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cards = [list(map(int, input().split())) for i in range(M)]

for card in cards:
    A += [card[1]]*card[0]
A.sort(reverse=True)

print(sum(A[:N]))


### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cards = [list(map(int, input().split())) for i in range(M)]
cards = sorted(cards, key=lambda x: x[1], reverse=True)

cnt = 0
for card in cards:
    A += [card[1]]*card[0]
    cnt += card[0]
    if cnt >= N:
        break
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

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

filled = [0 for _ in range(n)]
ans = []
for i in range(n-1, -1, -1):
  if sum(filled[i:][::i+1]) % 2 != A[i]:
    filled[i] = 1
    ans.append(i+1)
print(len(ans))
if len(ans) > 0:
	print(' '.join(map(str, ans)))

### FIXED CODE ###

# from other person's code
n = int(input())
a = list(map(int, input().split()))
ls = [0]*(n+1)
ans = []
for i in reversed(list(range(n))):
    if sum(ls[::i+1][1:]) % 2 != a[i]:
        ls[i+1] = 1
        ans.append(i+1)
print(sum(ls))
if ans: print(' '.join(map(str, ans)))
### BUGGY CODE ###

N, M = map(int, input().split())
mod = 10**9 + 7

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, M + 1):
  fact.append((fact[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod // i)) % mod)
  factinv.append((factinv[-1] * inv[-1]) % mod)

ans = fact[M]*factinv[M-N]%mod #Aの選び方

y = [fact[M-N]]
x = factinv[N]*y[-1]%mod
for k in range(1, N):
  minus = 0
  for j in range(k):
    minus = (minus+fact[k]*factinv[k-j]%mod*factinv[j]%mod)%mod
  y.append((fact[M-N+k] - minus)%mod)
  x = (x+y[-1]*factinv[k]%mod*factinv[N-k]%mod)%mod
x = x*fact[N]%mod*factinv[M-N]%mod
print(ans*(ans-x)%mod)

### FIXED CODE ###

N, M = map(int, input().split())
mod = 10**9 + 7

fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, M + 1):
  fact.append((fact[-1] * i) % mod)
  inv.append((-inv[mod % i] * (mod // i)) % mod)
  factinv.append((factinv[-1] * inv[-1]) % mod)

ans = 0
for k in range(N+1):
  if k%2 == 0:
    ans = (ans+factinv[N-k]*factinv[k]%mod*fact[M-k]%mod)%mod
  else:
    ans = (ans-factinv[N-k]*factinv[k]%mod*fact[M-k]%mod)%mod
ans = ans*fact[N]%mod*fact[M]%mod*factinv[M-N]%mod*factinv[M-N]%mod
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
x = a.count(max(a))
if 2 <= x:
    for i in range(n):
        print(max(a))
else:
    for i in range(n):
        if a[i] == max(a):
            print(max(a[:i] + a[i+1:]))
        else:
            print(max(a))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = tuple(a)
a.sort()
for i in b:
    if i == a[n-1]:
        print(a[n-2])
    else:
        print(a[n-1])
### BUGGY CODE ###

n,m=map(int,input().split())
k=[[] for _ in range(n)]
p=[0 for _ in range(m)]
y=[0 for _ in range(m)]
for i in range(m):
	a,b = map(int,input().split())
	y[i] = b
	p[i] = a
	k[a-1].append(b)
for i in range(n):
	k[i].sort()
ansl = []
for i in range(m):
	d1 = str(p[i]).zfill(6)
	d2 = str(k[p[i]-1].index(y[i])+1).zfill(6)
	ansl.append(d1+d2)
print("\n".join(ansl))

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
k=[[] for _ in range(n)]
p=[0 for _ in range(m)]
y=[0 for _ in range(m)]
for i in range(m):
	a,b = map(int,input().split())
	y[i] = b
	p[i] = a
	k[a-1].append(b)
for i in range(n):
	k[i].sort()
ansl = []
for i in range(m):
	d1 = str(p[i]).zfill(6)
	d2 = str(bisect.bisect_right(k[p[i]-1], y[i])).zfill(6)
	ansl.append(d1+d2)
print("\n".join(ansl))
### BUGGY CODE ###

from sys import stdin

N, K = [int(x) for x in stdin.readline().rstrip().split()]
ab = [[int(x) - 1 for x in stdin.readline().rstrip().split()] for _ in range(N - 1)]
inf = 1000000007

graph = [[] for _ in range(N)]
for n in range(N - 1):
    graph[ab[n][0]].append(ab[n][1])
    graph[ab[n][1]].append(ab[n][0])

stack = [(0, -1)]
ans = 1
done = [False for _ in range(N)]
cnt = 0
parent = -1
while len(stack) > 0:
    now = stack.pop(0)
    done[now[0]] = True
    for x in graph[now[0]]:
        if not done[x]:
            stack.append((x, now[0]))
    if now[0] == 0:
        ans = K * ans % inf
    else:
        if parent != now[1]:
            cnt = 0
        else:
            cnt += 1
        parent = now[1]
        if parent == 0:
            ans = (K - 1 - cnt) * ans % inf
        else:
            ans = (K - 2 - cnt) * ans % inf
print(ans % inf)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))
 
def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

Ans = 0
for i in range(N):
  s = S[i]
  a = 0
  b = 0
  L = ["B","G","R"]
  L.remove(s)
  for j in range(i+1,N):
    t = S[j]
    if s != t:
      if t == L[0]:
        a +=1
      else:
        b +=1
  Ans += a*b

for i in range(N):
  s = S[i]
  n = min(N,(N+i-1)//2+1)
  for j in range(i+1,n):
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)

### FIXED CODE ###

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

L = [0,0,0]
for i in range(N):
    if S[i] == "R":
        L[0] +=1
    elif S[i] == "G":
        L[1] +=1
    else:
        L[2] +=1

Ans = L[0]*L[1]*L[2]

for i in range(N):
  s = S[i]
  n = min(N, (N+i)//2 + 1)
  for j in range(i+1,n):
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)
### BUGGY CODE ###

def main():
    N = int(input())
    X = int(input(),2)
    LIST = []
    PM = [-1]*N
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N
    bit = 1
    for i in range(N):
        LIST.append(X^bit)
        PM[i] += (X & bit == 0)*2
        bit = bit<<1

    for i in range(N):
        cnt = count_ones_by_bitmask(X)
        if LIST[i]!=0:
            TEMP[i] += LIST[i] % (cnt+PM[i])
            ANS[i] += 1

    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])





def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    X = input()
    XINT = int(X,2)
    ANS = [0]*N
    TEMP = [0]*N
    CHAIND = [0]*N

    cnt = count_ones_by_bitmask(XINT)
    
    if cnt == 0:
        for i in range(N):
            print(1)
            return
    if cnt ==1:
        for i in  range(N):
            if X[i] == '1':
                print(0) #全てが0になる
            else:
                if i==N-1:
                    print((int(X[N-1])+1)%2+1) # 2の剰余の反転
                else:
                    print((int(X[N-1]))%2+1) # 2の剰余
        return

    p = XINT % (cnt+1)
    m = XINT % (cnt-1)
    pmod = 1
    mmod = 1
    for i in range(N):
        ANS[i] = 1
        if (X[N-i-1] == '0'):
            TEMP[i] = (p + pmod) % (cnt+1)
        else:
            TEMP[i] = (m - mmod) % (cnt-1)
        pmod = (pmod*2) % (cnt+1)
        mmod = (mmod*2) % (cnt-1)


    CHA = list(set(TEMP))

    for i in range(len(CHA)):
        an = 0
        cha = CHA[i]
        cnt = count_ones_by_bitmask(CHA[i])
        while cnt>0:
            an += 1
            cha = cha%cnt
            cnt = count_ones_by_bitmask(cha)
        CHAIND[CHA[i]] = an

    for i in reversed(range(N)):
        print(ANS[i]+CHAIND[TEMP[i]])


def count_ones_by_bitmask(num):
    count = 0
    while num:
        count += num & 1
        num >>= 1
    return count

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

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

ans = [0]*N
for i in range(N):
    if i%2 == 0:
        ans[i] = sum(A[0:i:2])-sum(A[1:i:2])+A[i]+sum(A[i+1::2])-sum(A[i+2::2])
    else:
        ans[i] = -sum(A[0:i:2])+sum(A[1:i:2])+A[i]+sum(A[i+1::2])-sum(A[i+2::2])
ans.insert(0, ans.pop(-1))
print(*ans)

### FIXED CODE ###

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

ans = [0]*N

#TLE解
# for i in range(N):
#     if i%2 == 0:
#         ans[i] = sum(A[0:i:2])-sum(A[1:i:2])+A[i]+sum(A[i+1::2])-sum(A[i+2::2])
#     else:
#         ans[i] = -sum(A[0:i:2])+sum(A[1:i:2])+A[i]+sum(A[i+1::2])-sum(A[i+2::2])
# ans.insert(0, ans.pop(-1))

ans[0] = sum(A)-sum(A[1::2])*2
for i in range(1, N):
    ans[i] = A[i-1]*2-ans[i-1]
print(*ans)
### BUGGY CODE ###

def main():
    MOD = 10 ** 9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    lst = [-1] * n

    # O(N)
    for i in range(n + 1):
        if lst[a[i] - 1] != -1:
            first = lst[a[i] - 1]
            second = i
            break
        lst[a[i] - 1] = i

    # print (first, second)    
    left = first
    right = n - second
    # print (left, right)

    N = n + 1
    tmp1 = 1
    tmp2 = 1
    # O(N ^ 2)
    for i in range(1, n + 2):
        tmp1 = (tmp1 * (N + 1 - i))//i
        if i == 1:
            tmp2 = 1
        elif left + right < i - 1:
            tmp2 = 0
        else:
            tmp2 = (tmp2 * (left + right + 1 - (i - 1))) // (i - 1)
        print ((tmp1 % MOD - tmp2 % MOD) % MOD)

if __name__ == '__main__':
    main()

### FIXED CODE ###

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
lst = [-1] * n

# O(N)
for i in range(n + 1):
    if lst[a[i] - 1] != -1:
        first = lst[a[i] - 1]
        second = i
        break
    lst[a[i] - 1] = i

# print (first, second)    
left = first
right = n - second

U = 10 ** 5 + 1
def power_mod(a, n):
    if n == 0:
        return 1
    x = power_mod(a//2)

def make_fact(fact, fact_inv):
    for i in range(1, U + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    fact_inv[U] = pow(fact[U], MOD - 2, MOD)
    for i in range(U, 0, -1):
        fact_inv[i - 1] = (fact_inv[i] * i) % MOD

def comb(n, k):
    if k < 0 or n < k:
        return 0
    x = fact[n]
    x *= fact_inv[k]
    x %= MOD
    x *= fact_inv[n - k]
    x %= MOD
    return x

fact = [1] * (U + 1)
fact_inv = [1] * (U + 1)
make_fact(fact, fact_inv)

for i in range(1, n + 2):
    ans = comb(n + 1, i) - comb(left + right, i - 1)
    print (ans % MOD)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(10**8)
#input = sys.stdin.readline
from math import factorial
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  
def solve():
  x,y = (int(i) for i in input().split())
  mod = 10**9+7
  ct = 0
  for k in range(10**6+1):
    if x < k:
      break
    else:
      #y構成可能？
      remx = x-k
      remy = y-2*k
      if remy*2 == remx:
        times = k+remy
        res = 1
        for i in range(1,times+1):
          res = res*i%mod
        for i in range(1,remy+1):
          res = res*mod_inv(i,mod)%mod
        for i in range(1,k+1):
          res = res*mod_inv(i,mod)%mod
        ct += res
      ct %= mod
      
  print(ct)
  
solve()


### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(10**8)
#input = sys.stdin.readline
from math import factorial
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m
  
def solve():
  x,y = (int(i) for i in input().split())
  mod = 10**9+7
  ct = 0
  for k in range(10**6+1):
    if x < k:
      break
    else:
      #y構成可能？
      remx = x-k
      remy = y-2*k
      if remy*2 == remx:
        times = k+remy
        res = 1
        for i in range(1,times+1):
          res = res*i%mod
        for i in range(1,remy+1):
          res = res*mod_inv(i,mod)%mod
        for i in range(1,k+1):
          res = res*mod_inv(i,mod)%mod
        ct += res
      ct %= mod
      
  print(ct)
  
solve()
### BUGGY CODE ###

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

while len(s) < n:
    for i in range(a):
        s += "b"
        if len(s) >= n :
            break
    for i in range(b):
        s += "a"
        if len(s) >= n :
            break
            
print(s.count("b"))

### FIXED CODE ###

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

x = n // (a + b)
num += (x * a)

y = n % (a + b)

if y <= a:
    num += y
else:
    num += a

print(num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def eratosthenes(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [i for i in range(1, n+1) if is_prime[i-1]]
    return table


def main():
    q = int(input())
    lr = [list(map(int, input().split())) for _ in range(q)]
    e = set(eratosthenes(10**5))

    for l, r in lr:
        cnt = 0
        for i in range(l, r+1, 2):
            if i in e and (i+1) // 2 in e:
                cnt += 1
        print(cnt)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from itertools import accumulate
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


MAX = 10**5


def eratosthenes(n):
    is_prime = [1] * n
    is_prime[0] = 0

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = 0
                j += i
    return is_prime


def main():
    q = int(input())
    is_prime = eratosthenes(MAX)

    a = [0] * (MAX+1)
    for i in range(MAX+1):
        if is_prime[i-1] and is_prime[(i+1)//2-1]:
            a[i] = 1

    s = [0] + a
    s = list(accumulate(s))

    for _ in range(q):
        l, r = map(int, input().split())
        print(s[r+1] - s[l])


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

n = int(input())

p = list(map(int, input().split(' ')))

ans = 0
for i in range(n):
    flag = True
    for j in range(i+1):
        if p[i] > p[j]:
            flag = False

    if flag:
        ans += 1

print(ans)


### FIXED CODE ###

n = int(input())

p = list(map(int, input().split(' ')))


ans = 1
min_num = p[0]

for i in range(n-1):
    if p[i+1] < min_num:
        ans += 1
        min_num = p[i+1]

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

MOD = 10 ** 9 + 7

S = input()
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
	if s == "?":
		for n in range(13):
			for m in range(10):
				mod = (n * 10 + m) % 13
				dp[i + 1][mod] += dp[i][n]
				dp[i + 1][mod] %= MOD
	else:
		m = int(s)
		for n in range(13):
			mod = (n * 10 + m) % 13
			dp[i + 1][mod] += dp[i][n]
			dp[i + 1][mod] %= MOD

#for l in dp:
#	print(l)

print(dp[-1][5])


### FIXED CODE ###

MOD = 10 ** 9 + 7

S = input()
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
	if s == "?":
		for n in range(13):
			for m in range(10):
				mod = (n * 10 + m) % 13
				dp[i + 1][mod] += dp[i][n]
				dp[i + 1][mod] %= MOD
	else:
		m = int(s)
		for n in range(13):
			mod = (n * 10 + m) % 13
			dp[i + 1][mod] += dp[i][n]
			dp[i + 1][mod] %= MOD

#for l in dp:
#	print(l)

print(dp[-1][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
weight = []
value = []
for _ in range(N):
    w, v = map(int, input().split())
    weight.append(w)
    value.append(v)
def knapsack():
    dp = [[-1] * (W + 1) for _ in range(N + 1)]

    def solve(i, w):
        if dp[i][w] != -1:
            return dp[i][w]
        if N == i:
            ret_val = 0
        elif w - weight[i] < 0:
            ret_val = solve(i + 1, w)
        else:
            ret_val = max(solve(i + 1, w), solve(i + 1, w - weight[i]) + value[i])
        dp[i][w] = ret_val
        return dp[i][w]
    return solve(0, W)
if __name__ == "__main__":
    print(knapsack())

### FIXED CODE ###

import numpy as np
N , W = map(int, input().split())
goods = np.array([list(map(int , input().split())) for _ in range(N)])
dp = np.zeros((N + 1 , W + 1) , dtype = np.int)

for i in range(0,N):
    w, v = goods[i,:]
    dp[i + 1, w:] = np.maximum(dp[i,w:] , dp[i,:-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1,:],dp[i,:])
print(int(dp[N,W]))
### BUGGY CODE ###

MOD = 10**9 + 7
MOD_t_MAX = 2 * 10**6 + 100

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    r1, c1, r2, c2 = map(int, input().split())
    MOD_COM_init()
    a = MOD_COM(r2+1+c2+1, r2+1) - 1
    b = MOD_COM(r2+1+c1, c1) - 1
    c = MOD_COM(r1+c2+1, r1) - 1
    d = MOD_COM(r1+c1, c1) - 1
    ans = a - b - c + d
    print(ans % MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

MOD = 10**9 + 7
MOD_t_MAX = 2 * 10**6 + 10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    r1, c1, r2, c2 = map(int, input().split())
    MOD_COM_init()
    a = MOD_COM(r2+1+c2+1, r2+1) - 1
    b = MOD_COM(r2+1+c1, c1) - 1
    c = MOD_COM(r1+c2+1, r1) - 1
    d = MOD_COM(r1+c1, c1) - 1
    ans = a - (b + c) + d
    print(ans % MOD)

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

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
idx = [i for i in range(N - 1) if S[i:i+2] == 'AC']

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(sum([i >= l - 1 and i <= r - 2 for i in idx]))


### FIXED CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
m = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        m[i] = m[i-1] + 1
    else:
        m[i] = m[i-1]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(m[r - 1] - m[l - 1])