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

s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = [0 for j in range(13)]
if s[0] == '?':
    for i in range(10):
        dp[i] = 1
else:
    num = int(s[0])
    dp[num] = 1

for i in range(1, n):
    dp_new = [0 for j in range(13)]
    if s[i] == '?':
        for m in range(10):
            num = (m * 10**i) % 13
            for j in range(13):
                dp_new[(j+num)%13] = (dp_new[(j+num)%13] + dp[j]) % mod
    else:
        num = (int(s[i]) * 10**i) % 13
        for j in range(13):
            dp_new[(j+num)%13] = (dp_new[(j+num)%13] + dp[j]) % mod
    dp = dp_new

print(dp[5])

### FIXED CODE ###

s = input()
s = s[::-1]
n = len(s)
mod = 10**9 + 7

dp = [[0 for j in range(13)] for i in range(n)]
if s[0] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    num = int(s[0])
    dp[0][num] = 1

mul = 1
for i in range(1, n):
    mul = (mul*10) % 13
    if s[i] == '?':
        for m in range(10):
            num = (m * mul) % 13
            for j in range(13):
                dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod
    else:
        num = (int(s[i]) * mul) % 13
        for j in range(13):
            dp[i][(j+num)%13] = (dp[i][(j+num)%13] + dp[i-1][j]) % mod

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

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
ans = 0

for i in range(N):
  x = sum(A[i+1:]) % MOD
  ans = (ans + A[i] * x) % MOD

print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
x = sum(A)
ans = 0
 
for i in range(N):
  x -= A[i]
  y = x % MOD
  z = (A[i] * y) % MOD
  ans += z
  ans %= MOD

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

from sys import stdin
import sys
sys.setrecursionlimit(10**7)

ans = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    #print(S, N)

    #% (10^9 + 7)
    #return count_0
    N_l = len(N)
    for i in range(N_l):
        b(N, N[i], i)
    #print(list(set(ans)))
    #print(10**9 + 7)

    # 2
    #return len(list(set(ans))) % (10**9 + 7)
    for i in range(N_l):
        ans.append(N[i])
    #print(ans)
    return len(ans) % (10**9 + 7)


def b(org_array, temp, i):
    if len(org_array)-1 == i:
        return
    else:
        #print("org array:"+org_array)
        #ans.append(temp)
        #print(temp)
        if org_array[i+1] not in temp:
            b(org_array, temp, i+1)
            temp += org_array[i+1]
            ans.append(temp)
        #print("org: "+org_array[i+1])
        #print(temp)
        b(org_array, temp, i+1)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin
import math
import itertools


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

# これだと、O(n*n)
"""
temp_ans = []


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    N_l = len(N)
    global temp_ans
    for i in range(N_l)[::-1]:
        temp_ans += N[i]
        #print(temp_ans)
        for s in temp_ans:
            #print(s)
            if N[i] not in s:
                temp_ans.append(N[i]+s)
    #print(temp_ans)
    return len(temp_ans) % (10**9 + 7)
"""


def problem_a(input_string):
    S = int(input_string[0].rstrip())
    N = input_string[1].rstrip()
    #print(S)
    dic = {}
    c = 0
    for i in range(S)[::-1]:
        if N[i] not in dic:
            dic[N[i]] = 1
            #c += i+1
        else:
            dic[N[i]] += 1

    c = 1
    for key, value in dic.items():
        c *= (value+1)
    c -= 1
    """
    c += 2**len(dic.keys())-1
    #print(c)
    #c += S
    for key, value in dic.items():
        if value > 1:
            #c -= (value-1)
            c += 2**(len(dic.keys()))-1
            #print(c)
    #for key, value in dic.items():
    for key, value in dic.items():
        if value > 1:
            if len(dic.keys()) != S:
                c -= 2**(S-len(dic.keys())-1)
    """
            #print(c)
        #else:
    #c += (S-len(dic.keys()))
    """
    s_N = sorted(N)
    for i in range(S-1):
        if s_N[i] != s_N[i+1]:
            c += 2**(i+2)
    """
    """
    for key, value in dic.items():
        if value > 1:
            c += 2**(len(dic.items())-value)
        else:
            c += 2**(len(dic.items())-value)
    """
    #combinations_count(len(, r)

    return c % (10**9 + 7)


def main():
    input_line = stdin.readlines()
    answer = problem_a(input_line)
    print(answer)


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

a, b = map(int, input().split())
res = 1
for i in range(a, b + 1):
    res *= i
if res > 0:
    print('Positive')
elif res == 0:
    print('Zero')
else:
    print('Negative')

### FIXED CODE ###

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

if a <= 0 <= b:
    print('Zero')
elif 0 < a:
    print('Positive')
elif (b - a + 1)%2 == 0:
    print('Positive')
else:
    print('Negative')
### BUGGY CODE ###

def main():
    a, b, k = map(int, input().split())
    
    li = list(filter(lambda x: x <= a+k-1 or b-k+1 <= x 
        , [x for x in range(a, b+1)]))
    
    for i in li:
        print(i)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    a, b, k = map(int, input().split())
    
    s = set()

    for i in range(a, a+k):
        s.add(i)

    for i in range(b-k+1, b+1):
        s.add(i)

    for i in sorted(s):
        if a <= i and i <= b:
            print(i)

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

import math
n = int(input())
s = 0
for i in range(0,n):
    for j in range(0,n):
        for k in range(0, n):
            s += math.gcd(i+1, math.gcd(j+1, k+1))
print(s)

### FIXED CODE ###

import math
n = int(input())
s = 0
for i in range(0,n):
    for j in range(0,n):
        for k in range(0, n):
            s += math.gcd(i+1, math.gcd(j+1, k+1))
print(s)
### BUGGY CODE ###

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

result = 0
for i in range(60):
    on = sum([(1 << i) & a for a in A]) >> i
    result += (on * (N - on)) << i
    result %= ((10**9) + 7)

print(result)


### FIXED CODE ###

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

result = 0
for i in range(60):
    target = 1 << i
    on = sum([target & a for a in A]) >> i
    result += (on * (N - on)) << i
    result %= ((10**9) + 7)

print(result)
### BUGGY CODE ###

X,Y,A,B,C = map(int,input().split())

p = sorted(list(map(int,input().split()))) #A
q = sorted(list(map(int,input().split()))) #B
r = sorted(list(map(int,input().split()))) #C

xlist = p[-X:] #X
ylist = q[-Y:] #Y

def main(X,Y,xlist,ylist,r):
    for i in range(min(X,Y)):
        if xlist[i] < ylist[i] and min(xlist) < max(r):
            xlist.remove(min(xlist))
            xlist.append(r.pop())
            
        elif ylist[i] < xlist[i] and min(ylist) < max(r):
            ylist.remove(min(ylist))
            ylist.append(r.pop())
            
        else:
            continue
    
    print(sum(xlist)+sum(ylist))

main(X,Y,xlist,ylist,r)

### FIXED CODE ###

X,Y,A,B,C = map(int,input().split())

p = sorted(list(map(int,input().split()))) #A
q = sorted(list(map(int,input().split()))) #B
r = sorted(list(map(int,input().split()))) #C

xlist = p[-X:] #X
ylist = q[-Y:] #Y

"""
def main(X,Y,xlist,ylist,r):
    for i in range(min(X,Y)):
        if xlist[i] < ylist[i] and min(xlist) < max(r):
            xlist.remove(min(xlist))
            xlist.append(r.pop())
            
        elif ylist[i] < xlist[i] and min(ylist) < max(r):
            ylist.remove(min(ylist))
            ylist.append(r.pop())
            
        elif min(xlist) >= max(r) and min(ylist) >= max(r):
            break
        else:
            continue
    
    print(sum(xlist + ylist))

main(X,Y,xlist,ylist,r)
"""
all_apples = sorted(xlist + ylist + r)
print(sum(all_apples[-(X+Y):]))
### BUGGY CODE ###

N = int(input())
T = []
for k in range(N-1):
    t = list(map(int,input().split()))
    T.append(t)

T = sorted(T, key = lambda x: (x[0],x[1]))

A = [-1 for k in range(N)]
A[0] = 0
for t in T:
    u = t[0]-1
    v = t[1]-1
    w = t[2]
    if w%2 == 0:
        if A[u] == 0 and A[v] == -1:
            A[v] = 0
        elif A[u] == 1 and A[v] == -1:
            A[v] = 1
        elif A[u] == -1 and A[v] == 0:
            A[u] = 0
        elif A[u] == -1 and A[v] == 1:
            A[u] = 1
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])
    else:
        if A[u] == 0 and A[v] == -1:
            A[v] = 1
        elif A[u] == 1 and A[v] == -1:
            A[v] = 0
        elif A[u] == -1 and A[v] == 0:
            A[u] = 1
        elif A[u] == -1 and A[v] == 1:
            A[u] = 0
        elif A[u] == -1 and A[v] == -1:
            T.append([u+1,v+1,w])

print(*A, sep="\n")

### FIXED CODE ###

N = int(input())
T = [[] for k in range(N)]
for k in range(N-1):
    u,v,w = map(int,input().split())
    T[u-1].append([v-1,w])
    T[v-1].append([u-1,w])

kyori = [-1 for k in range(N)]
kyori[T[0][0][0]] = 0
que = [T[0][0][0]]

while len(que) > 0:
    now = que.pop()
    for tsugi in T[now]:
        if kyori[tsugi[0]] == -1:
            kyori[tsugi[0]] = kyori[now] + tsugi[1]
            que.append(tsugi[0])

for a in kyori:
    print(a%2)
### BUGGY CODE ###

n,m = map(int,input().split())
py = []

od = [[]*1 for i in range(n)]
rank = [[]*1 for i in range(n)]

for i in range(0,m):
    p,y = map(int,input().split())
    py.append([p,y])
       
    odlen = len(od[p-1])
    if odlen >= 1 :

        low = 0
        high = odlen - 1
        mid = odlen//2

        while low <= high:
            mid = (low + high) >> 1
            guess = od[p-1][mid]

            if guess == y:
                break
            if guess > y :
                high = mid - 1
            else:
                low  = mid + 1        

        od[p-1].insert(low,y)

        for j in range (len(rank[p-1])):
            if rank[p-1][j] >= low :
                rank[p-1][j] +=1

        for r in rank :
            r.append(0)
        rank[p-1][i] = low

    else:
        od[p-1].append(y)

        for r in rank :
            r.append(0)        
        rank[p-1][i] = 0

for i in range(0,m):
    r = rank[py[i][0]-1][i]

    tmp = py[i][0]
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = py[i][0] // 10
    
    for j in range(6-digit):
        print('0',end="")
    print(py[i][0],end="")

    tmp = r + 1
    digit = 0
    while tmp > 0 :        
        digit += 1
        tmp = r // 10

    for j in range(6-digit):
        print('0',end="")
    print(r+1)

### FIXED CODE ###

import sys as sys

lines =  input().split()
n = int(lines[0])
m = int(lines[1])

py = []
od = {}

#lines = sys.stdin.readlines()

for i in range(0,m):


    #l =  lines[i].split()
    l = input().split()
    p = int(l[0])
    y = int(l[1])
    
    if p in od :
        od[p].append([i,y])
    else:
        od[p] = [[i,y]]

a = []
for p in od.keys():
    od[p].sort(key=lambda x:x[1])
    r = 1

    for o in od[p]:
        cs = ""

        tmp = p
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10
        
        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(p)

        tmp = r 
        digit = 0
        while tmp > 0 :        
            digit += 1
            tmp = tmp // 10

        l = 6-digit
        for j in range(l):
            cs += '0'
        cs += str(r)        

        a.append([o[0],cs])
        r += 1

a.sort(key=lambda x:x[0])
for aa in a:
    print(aa[1])
### BUGGY CODE ###

N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = sorted(list(map(int, input().split(" "))))
bottoms = sorted(list(map(int, input().split(" "))))
# print(tops)
# print(mids)
# print(bottoms)


def left_binary_search(check_list, num, left, right):
    if left > right:
        return left
    mid = (left + right) // 2
    if check_list[mid] >= num:
        return left_binary_search(check_list, num, left, mid - 1)
    else:
        return left_binary_search(check_list, num, mid + 1, right)


def right_binary_search(check_list, num, left, right):
    if left > right:
        return left
    mid = (left + right) // 2
    if check_list[mid] > num:
        return right_binary_search(check_list, num, left, mid - 1)
    else:
        return right_binary_search(check_list, num, mid + 1, right)


total_count = 0
for mid in mids:
    bottom_start_index = right_binary_search(bottoms, mid, 0, N - 1)
    top_end_index = left_binary_search(tops, mid, 0, N - 1)
    total_count += ((N - bottom_start_index) * top_end_index)
print(total_count)


### FIXED CODE ###

import bisect
N = int(input())
# サイズが下の方が大きくないとダメtop<mid<bottom
tops = sorted(list(map(int, input().split(" "))))
mids = list(map(int, input().split(" ")))
bottoms = sorted(list(map(int, input().split(" "))))
# print(tops)
# print(mids)
# print(bottoms)


# def left_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] >= num:
#         return left_binary_search(check_list, num, left, mid - 1)
#     else:
#         return left_binary_search(check_list, num, mid + 1, right)


# def right_binary_search(check_list, num, left, right):
#     if left > right:
#         return left
#     mid = (left + right) // 2
#     if check_list[mid] > num:
#         return right_binary_search(check_list, num, left, mid - 1)
#     else:
#         return right_binary_search(check_list, num, mid + 1, right)


total_count = 0
for mid in mids:
    # bottom_start_index = right_binary_search(bottoms, mid, 0, N - 1)
    bottom_start_index = bisect.bisect_right(bottoms, mid)
    # top_end_index = left_binary_search(tops, mid, 0, N - 1)
    top_end_index = bisect.bisect_left(tops, mid)
    total_count += ((N - bottom_start_index) * top_end_index)
print(total_count)
### BUGGY CODE ###

from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
table = [[INF] * L for _ in range(M + 1)]
table[0][0] = 0
for m in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    for l in range(L):
        now = table[m][l]
        if l and not now:
            continue
        table[m + 1][l] = min(now, table[m + 1][l])
        table[m + 1][l | match] = min(now + cost, table[m + 1][l | match])
print(table[M][L - 1] if table[M][L - 1] != INF else -1)

### FIXED CODE ###

from functools import reduce
INF = 10 ** 7
N, M = map(int, input().split())
L = 1 << N
keys = [0] * M
for m in range(M):
    cost, _ = map(int, input().split())
    match = reduce(lambda a, b: a | b, (1 << shamt for shamt in map(lambda n: int(n) - 1, input().split())))
    keys[m] = cost, match
table = [[INF] * L for _ in range(M + 1)]
table[0][0] = 0
for m in range(M):
    cost, match = keys[m]
    for l in range(L):
        now = table[m][l]
        if l and not now:
            continue
        table[m + 1][l] = min(now, table[m + 1][l])
        table[m + 1][l | match] = min(now + cost, table[m + 1][l | match])
print(table[M][L - 1] if table[M][L - 1] != INF else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(h)]
b = [tuple(map(int, input().split())) for _ in range(h)]
c = [[a[i][j] - b[i][j] for j in range(w)] for i in range(h)]

MAX_K = 12805
dp = [[[False] * (MAX_K + 80) for _ in range(w)] for _ in range(h)]
dp[0][0][abs(c[0][0])] = True

for i in range(h):
    for j in range(w):
        for k in range(MAX_K):
            if dp[i][j][k]:
                if i < h - 1:
                    dp[i + 1][j][abs(k + c[i + 1][j])] = True
                    dp[i + 1][j][abs(k - c[i + 1][j])] = True

                if j < w - 1:
                    dp[i][j + 1][abs(k + c[i][j + 1])] = True
                    dp[i][j + 1][abs(k - c[i][j + 1])] = True

for k in range(MAX_K):
    if dp[h - 1][w - 1][k]:
        ans = k
        break
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(h)]
b = [tuple(map(int, input().split())) for _ in range(h)]
c = [[abs(a[i][j] - b[i][j]) for j in range(w)] for i in range(h)]

CONST = 80 * 80 * 2
dp = [[0] * w for _ in range(h)]
dp[0][0] = 1 << (c[0][0] + CONST)

for i in range(h):
    for j in range(w):
        if i < h - 1:
            dp[i + 1][j] |= (dp[i][j] << c[i + 1][j])
            dp[i + 1][j] |= (dp[i][j] >> c[i + 1][j])
        if j < w - 1:
            dp[i][j + 1] |= (dp[i][j] << c[i][j + 1])
            dp[i][j + 1] |= (dp[i][j] >> c[i][j + 1])

for k in range(CONST):
    if dp[h - 1][w - 1] & (1 << (CONST + k)) != 0 or dp[h - 1][w - 1] & (
            1 << (CONST - k)) != 0:
        ans = k
        break

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

q = int(input())
n = 10**5
nums = [False]*2+[True]*(n-2)

for i in range(2, n):
    if nums[i]:
        for j in range(i*2, n, i):
            nums[j] = False
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())
    for i in range(l, r+1, 2):
        if nums[i] == nums[(i+1)//2] == True:
            ans += 1
    print(ans)


### FIXED CODE ###

q = int(input())
n = 10**5
nums = [False]*2+[True]*(n-2)
ans = [0]*n
for i in range(2, n):
    if nums[i]:
        for j in range(i*2, n, i):
            nums[j] = False
pre = 0
for i in range(3, n, 2):
    if nums[i] and nums[(i+1)//2]:
        ans[i] += pre+1
        pre = ans[i]
    else:
        ans[i] = pre
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r]-ans[max(l-2, 1)])
### BUGGY CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque
from copy import deepcopy

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  temp_s=deepcopy(s)

  que=deque()
  que.append((sy,sx))

  while que:
    y,x=que.popleft()
    for dy,dx in [[-1,0],[0,-1],[1,0],[0,1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w:
        if (temp_s[y][x]=='#' and temp_s[ny][nx]=='.') or \
           (temp_s[y][x]=='.' and temp_s[ny][nx]=='#'):
          que.append((ny,nx))
          if temp_s[ny][nx]=='.':
            ans.add(((sy,sx),(ny,nx)))
    temp_s[y][x]='D'

  return ans

ans=set()
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

print(len(ans))

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
s=[list(input()) for i in range(h)]

def BFS(sy,sx,ans):
  s[sy][sx]='B'

  que=deque()
  que.append((sy,sx))

  b_cnt=1
  w_cnt=0

  while que:
    y,x=que.popleft()
    for dy,dx in [[-1,0],[0,-1],[1,0],[0,1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w:
        if s[y][x]=='B' and s[ny][nx]=='.':
          w_cnt+=1
          s[ny][nx]='W'
          que.append((ny,nx))
        if s[y][x]=='W' and s[ny][nx]=='#':
          b_cnt+=1
          s[ny][nx]='B'
          que.append((ny,nx))

  ans+=b_cnt*w_cnt
  return ans

ans=0
for i in range(h):
  for j in range(w):
    if s[i][j]=='#':
      ans=BFS(i,j,ans)

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

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
import numpy as np
A = np.array(A, np.int64)
A = lcm // A
A %= mod
ans += np.sum(A)
ans %= mod
print(ans) 

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
for i in A:
    ans += lcm // i
print(ans % mod)
### BUGGY CODE ###

import math

MOD = 10 ** 9 + 7


def cmb(n, r):
    total = 1
    for i in range(r):
        total *= (n - i) % MOD
    return total * pow(math.factorial(r), MOD - 2, MOD) % MOD


if __name__ == '__main__':
    n, a, b = list(map(int, input().split(" ")))

    total = pow(2, n, MOD)
    a_total = cmb(n, a)
    b_total = cmb(n, b)
    # print((total - a_total - b_total - 1) % MOD)

    print(max(0, (pow(2, n, MOD) - ((cmb(n, a) + cmb(n, b)) % MOD) - 1) % MOD))

### FIXED CODE ###

from math import factorial
N, A, B = map(int, input().split())
MOD = 10 ** 9 + 7

def calc(n):
    ret = 1
    for i in range(n):
        ret = ret * (N - i) % MOD
    return ret * pow(factorial(n), MOD - 2, MOD) % MOD

print(max(0, (pow(2, N, MOD) - ((calc(A) + calc(B)) % MOD) - 1) % MOD))
### BUGGY CODE ###

a, b , n= input().split() 
a = int(a)
b = int(b)
n = int(n)
if b > n :
    print(a*n//b)
else:
    max = 0
    for i in range(1,b,1):
        r = (a*i // b) - a* (i//b)
        if r > max:
            max = r

    print(max)


### FIXED CODE ###

a, b , n= input().split() 
a = int(a)
b = int(b)
n = int(n)
p = min(b,n)
if p % b ==0:
    print(int(a*(p-1)/b))
else:
    print(int(a*p/b))
### BUGGY CODE ###

N = int(input())
A0 = list(map(int, input().split()))
A = [0] + A0 + [0]
for i in range (1, N+1):
    tot = 0
    j = 0
    while j < N+1:
        if j+1 != i:
            tot += abs(A[j+1]-A[j])
            j += 1
        else:
            tot += abs(A[j+2]-A[j])
            j += 2
    print(tot)

### FIXED CODE ###

N = int(input())
A0 = list(map(int, input().split()))
A = [0] + A0 + [0]
tot = 0
for i in range (N+1):
    tot += abs(A[i+1]-A[i])
for i in range (1, N+1):
    print(tot - abs(A[i-1]-A[i]) -abs(A[i]-A[i+1]) + abs(A[i-1]-A[i+1]))
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import sqrt
def main():
    k = int(input())
    if k % 2 == 0:
        print(-1)
        sys.exit()
    ok = k
    while True:
        ks = str(k)
        ksc = [c == '7' for c in ks]
        if all(ksc):
            r = len(ks)
            print(r)
            sys.exit()
        else:
            k += ok

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    k = int(input())
    if k % 2 == 0 or k % 5 == 0:
        print(-1)
        sys.exit()
    p = 7
    plus = 7
    amari = set()
    r = 1
    while (p % k) != 0:
        if p in amari:
            print(r, -1, p)
            sys.exit()
        else:
            amari.add(p)
            plus = (plus * 10) % k
            p += plus
            p = p % k
            r += 1
    print(r)

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

import re
n,q = map(int, input().split())
s = input()

l = [0]*q
r = [0]*q
for i in range(q):
  l[i],r[i] = map(int, input().split())
  
where_a=[0]*n
where_c=[0]*n
pattern = "AC"
result = re.finditer(pattern, s)
i=0
for res in result:
  i+=1
  tmp=res.span()
  where_a[tmp[0]]=i
  where_c[tmp[1]-1]=i

  
for i in range(q):
  tmp1 = where_a[l[i]-1:r[i]]
  tmp2 = where_c[l[i]-1:r[i]]
  tmp3 = set(tmp1) & set(tmp2) -{0}
  #print(tmp3)
  print(len(tmp3))
  

### FIXED CODE ###

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

counts = [1 if s[i:i+2]=="AC" else 0 for i in range(n)]

cum_counts=[0]*n
for i in range(1,n):
  cum_counts[i]=cum_counts[i-1]+counts[i-1]

#print(counts)
#print(cum_counts)

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