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

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())

total = 0
for i in range(N):
    total = S.count("AC")

left = [0] * N
right = [0] * N
if S[0:2] == "AC":
    left[1] = 1
if S[N-2:N] == "AC":
    right[N-2] = 1
for i in range(2,N):
    if S[i-1:i+1] == "AC":
        left[i] = left[i-2]+1
    else:
        left[i] = left[i-1]

for i in range(N-3,-1,-1):
    if S[i:i+2] == "AC":
        right[i] = right[i+2]+1
    else:
        right[i] = right[i+1]

left = [0] + left
left.append(0)
right = [0] + right
right.append(0)

for i in range(Q):
    res = total - (left[l[i]-1] + right[r[i]+1])
    if l[i] >= 2 and S[l[i]-2] == "A" and S[l[i]-1] == "C":
        res -= 1
    if r[i] <= N-1 and S[r[i]-1] == "A" and S[r[i]] == "C":
        res -= 1
    print(res)

### FIXED CODE ###

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())

left = [0] * N
if S[0:2] == "AC":
    left[1] = 1
for i in range(2,N):
    if S[i-1:i+1] == "AC":
        left[i] = left[i-2]+1
    else:
        left[i] = left[i-1]

for i in range(Q):
    if (l[i] == 1):
        res = left[r[i]-1]
    else:
        res = left[r[i]-1] - left[l[i]-2]
    if l[i] >= 2 and S[l[i]-1] == "C" and S[l[i]-2] == "A":
        res -= 1
    print(res)
### BUGGY CODE ###

N =int(input())
A_n =list(map(int,input().split()))
ans =1
for i in range(N):
  ans *= A_n[i]
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

N =int(input())
A_n =list(map(int,input().split()))
ans =1
i = 0

while ans <= 10**18 and i < N:
  ans *= A_n[i]
  i +=1
if ans > 10**18:
  if 0 in A_n:
    print(0)
  else:
    print(-1)
else:
  print(ans)
### BUGGY CODE ###

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

for i in range(n):
	b[i].sort()

for i, j in a:
	x = b[i-1].index(j)
	p = "00000" + str(i)
	p = p[-6:]
	y = "00000" + str(x+1)
	y = y[-6:]
	print (p+y)
	#print ("{:06d}".format(i) + "{:06d}".format(x+1))

### FIXED CODE ###

n, m = map(int, input().split())
a = []
b = [[] for i in range(n)]
for i in range(m):
	p, y = map(int, input().split())
	a.append([p,y])
	b[p-1].append(y)
dic = {}
for i in range(n):
	b[i].sort()
	for j,k in enumerate(b[i]):
		dic[k] = j+1

for i, j in a:
	print ("{:06d}".format(i) + "{:06d}".format(dic[j]))
### BUGGY CODE ###

from collections import deque

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

ANS = deque(S)

for _ in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        ANS = list(ANS)
        ANS = ANS[::-1]
        ANS = deque(ANS)
    else:
        f, c = query[1:]
        if f == '1':
            ANS.appendleft(c)
        else:
            ANS.append(c)

print(''.join(ANS))

### FIXED CODE ###

from collections import deque

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

ANS = deque(S)

rev = 0

for _ in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        rev = rev ^ 1
    else:
        f, c = int(query[1]), query[2]
        if (f - 1) ^ rev:
            ANS.append(c)
        else:
            ANS.appendleft(c)

if rev:
    ANS.reverse()

print(''.join(ANS))
### BUGGY CODE ###

S = input()
k = int(input())

begin, end = 0, 1

# 辞書順先頭となる1文字目を探索

top = S[0]
idxs = {0}

for idx, s in enumerate(S):
    if ord(s) < ord(top):
        idxs = {idx}
        top = s
    elif ord(s) == ord(top):
        idxs.add(idx)

orders = {top}
while len(orders) < k:
    flag = False
    for idx in idxs:
        ptr = 2
        while idx + ptr < len(S) + 1 and ptr < 7:
            orders.add(S[idx: idx + ptr])
            flag = True
            ptr += 1
    if not flag:
        break


if len(orders) < k:
    second = chr(123)
    idxs = set()
    for idx, s in enumerate(S):
        if s != top:
            if ord(s) < ord(second):
                idxs = {idx}
                second = s
            elif ord(s) == ord(second):
                idxs.add(idx)

    orders.add(second)
    ptr = 2
    while len(orders) < 5:
        flag = False
        for idx in idxs:
            ptr = 2
            while idx + ptr < len(S) + 1 and ptr < 7:
                orders.add(S[idx: idx + ptr])
                flag = True
                ptr += 1
        if not flag:
            break

print(sorted(list(orders))[k - 1])


### FIXED CODE ###

S = input()
k = int(input())
n = len(S)

orders = set()

for i in range(n):
    for j in range(1, 6):
        if i + j < n + 1:
            orders.add(S[i:i + j])

print(sorted(list(orders))[k - 1])
### BUGGY CODE ###

from fractions import gcd


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


l = 1

for a in A:
    l = l * a // gcd(l, a)


ans = 0
for a in A:
    ans += (l // a)
ans %= MOD

print(ans)


### FIXED CODE ###

from fractions import gcd


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


    l = 1

    for a in A:
        l = l * a // gcd(l, a)


    ans = 0
    for a in A:
        ans += (l // a)
    ans %= MOD

    print(ans)


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

import sys
sys.setrecursionlimit(100000)

N,S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
P = []

def BFS(now,i,pattern):
    if now == S:
        P.append(pattern)
    else:
        if i < N:
            if now + A[i] <= S:
                BFS(now+A[i],i+1,pattern+1)

            BFS(now,i+1,pattern)

BFS(0,0,0)

pow_2 = [1]*3010
for i in range(1,3010):
    pow_2[i] = (2*pow_2[i-1])%mod


ans = 0
n = len(P)
for i in range(n):
    l = P[i]
    ans += pow_2[N-l]
    ans %= mod
print(ans)



### FIXED CODE ###

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

dp = [[0]*3005 for _ in range(3005)]
dp[0][0] = 1
for i in range(0,N):
    for s in range(0,S+1):
        if s-A[i] >= 0:
            dp[i+1][s] = dp[i][s]*2 + dp[i][s-A[i]]
        else:
            dp[i+1][s] = dp[i][s]*2
        dp[i+1][s] %= mod

print(dp[N][S])
### BUGGY CODE ###

import sys
from fractions import gcd
from itertools import permutations, combinations, accumulate
from collections import deque
from heapq import heappush, heappop, heapify

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n = int(input())
    a= [0] * (n-1)
    b = [0] * (n-1)
    g = [[] for _ in range(n+1)]
    c = [[0]*(n+1) for _ in range(n+1)]
    cn = 0

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

    for i in range(1, n+1):
        cc = [_ for _ in range(1, n) if _ not in c[i]]
        heapify(cc)
        for j in g[i]:
            c[i][j] = c[j][i] = heappop(cc)
            cn = max(cn, c[i][j])

    print(cn)
    for p, q in zip(a, b):
        print(c[p][q])



if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from fractions import gcd
from itertools import permutations, combinations, accumulate
from collections import deque
from heapq import heappush, heappop, heapify
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

class Edge:
    def __init__(self, first, second):
        self.color = 0
        self.first = first
        self.second = second

def main():
    def dfs(i, par, pcol):
        cc = 1
        for e in v[i]:
            if cc == pcol:
                cc += 1
            if e.color == 0:
                e.color = cc
                dfs(e.second, par, cc)
                cc += 1

    n = int(input())
    e = [[] for _ in range(n-1)]
    v = [[] for _ in range(n+1)]

    for i in range(n-1):
        a, b = list(map(int,input().split()))
        e[i] = Edge(a, b)
        v[a].append(e[i])

    dfs(1, -1, 0)

    m = 0
    for i in range(n-1):
        m = max(m,e[i].color)

    print(m)
    for i in range(n-1):
        print(e[i].color)

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

K, S = map(int,input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k ==S:
                count +=1
print(count)

### FIXED CODE ###

K, S = map(int,input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        k = S - i - j
        if k >= 0 and k <=K:
                count +=1
print(count)
### BUGGY CODE ###

#ABC179-c

import sys,math,collections,itertools
input = sys.stdin.readline

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

N = int(input())
cnt = 0
for c in range(1,N-1):
    arr = factorize(N-c)
    tmp = 1
    for ar in arr:
        tmp *= (ar[1]+1)
    cnt += tmp
cnt +=1
print(cnt)


### FIXED CODE ###

#ABC179-c

import sys,math,collections,itertools
input = sys.stdin.readline

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def fact_fast(n):
    arr = []
    temp = n
    i=2
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])
    i =3
    while i*i<=temp:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
        i += 2
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

N = int(input())
cnt = 0
for c in range(1,N-1):
    arr = fact_fast(N-c)
    tmp = 1
    for ar in arr:
        tmp *= (ar[1]+1)
    cnt += tmp
cnt +=1
print(cnt)
### BUGGY CODE ###

def resolve():
    inp = input()
    orginp = inp
    while True:
        update = 0
        for i in range(len(inp)-1):
            if inp[i] != inp[i+1]:
                if len(inp) > i+2:
                    inp = inp[:i] + inp[i+2:]
                else:
                    inp = inp[:i]
                update += 1
                break
        if update == 0:
            break
    print(len(orginp)-len(inp))

resolve()

### FIXED CODE ###

def resolve():
    inp = input()

    c0 = inp.count('0')
    c1 = inp.count('1')

    print(min(c0, c1)*2)

resolve()
### BUGGY CODE ###

import numpy as np
from collections import Counter
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
ans = np.zeros([N, N])
for i in range(N):
  for j in range(i, N):
    ans[i][j] = min(abs(j-i), abs(j-X)+1+abs(Y-i), abs(i-X)+1+abs(j-Y))
c = Counter(ans.reshape(-1))
for k in range(1, N):
  print(c[k])

### FIXED CODE ###

x = input().split()
N = int(x[0])
X = int(x[1])
Y = int(x[2])

L = [0 for _ in range(N+1)]

for i in range(1,N):
    for j in range(i+1,N+1):
        L[min(j-i,abs(X-i)+abs(Y-j)+1)] +=1
            
for k in range(1,N):
    print(L[k])
### BUGGY CODE ###

import collections

N = int(input())
arr = list(map(int, input().split()))
i_arr =[]
j_arr =[]

ans = 0
for i in range(N):
    i_arr.append(i+arr[i])
    dic = collections.Counter(i_arr)
    j_arr.append(-1*arr[i]+i)
    ans += dic[j_arr[-1]]

print(ans)


### FIXED CODE ###

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

dic = {}
j_arr =[]

ans = 0
for i in range(N):
    if i+arr[i] not in dic:
        dic[i+arr[i]] = 0
    dic[i+arr[i]] += 1
    j_arr.append(-1*arr[i]+i)
    if -1*arr[i]+i in dic:
        ans += dic[-1*arr[i]+i]

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

def C(m):
    if xsort[m] > x[i]: 
        return True
    return False


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

for i in range(n):
    mb = 0
    lb = n
    m = (mb+lb) // 2
    xsort = sorted(x)
    for j in range(100):
        if C(m):
            lb = m
        else: 
            mb = m
    if mb < n//2:
        print(xsort[n//2])
    else:
        print(xsort[n//2-1])

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = sorted(X)
m1 = Y[N//2]
m2 = Y[N//2-1]
 
for i in range(N):
    if m1 > X[i]:
        print(m1)  # left
    else:
        print(m2)  # right
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
  a.sort()
  a[-1]=a[-1]//2
print(sum(a))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(lambda x:int(x)*(-1), input().split()))
heapq.heapify(a)
for i in range(m):
  d=heapq.heappop(a)*(-1)
  heapq.heappush(a,(-1)*(d//2))
print(-sum(a))
### BUGGY CODE ###

def resolve():
    A, B, K = map(int, input().split())
    count = []
    for _ in range(B-A+1):
        count.append(A+_)
    if K > B-A-1:
        K = B-A+1
    for i in range(K):
        print(count[i])
    for j in range(K):
        if count[(K*-1)+j] > count[K-1]:
            print(count[(K*-1)+j])
resolve()

### FIXED CODE ###

def resolve():
    A, B, K = map(int, input().split())
    if 2*K > B-A+1:
        for _ in range(B-A+1):
            print(A+_)
    else:
        for i in range(K):
            print(A+i)
        for j in range(K):
            print(B-K+j+1)
resolve()
### BUGGY CODE ###

from decimal import *
import math


n = int(input())
ans = 0
vec = [Decimal(input()) for i in range(n)]
vec25 = [[-9, -9] for i in range(n)]  # 整数にするのに余っている2,5の数
for i in range(n):
    a = vec[i] * 1000000000
    while a%2 == 0:
        a //= 2
        vec25[i][0] += 1
    while a%5 == 0:
        a //= 5
        vec25[i][1] += 1
mp = {}
for p in vec25:
    k = p[0] * 10000 + p[1]
    if k in mp:
        mp[k] += 1
    else:
        mp[k] = 1
for k1, v1 in mp.items():
    x5 = k1 % 10000
    while x5 > 100:
        x5 -= 10000
    x2 = (k1 - x5) // 10000
    # print(k1, x2, x5)
    if x5 >= 0 and x2 >= 0:
        ans += v1 * (v1 - 1) // 2
    for k2, v2 in mp.items():
        y5 = k2 % 10000
        while y5 > 100:
            y5 -= 10000
        y2 = (k2 - y5) // 10000
        if x5 + y5 >= 0 and x2 + y2 >= 0 and k1 > k2:
            ans += v1 * v2
print(ans)

### FIXED CODE ###

from decimal import *

n = int(input())
ans = 0
vec = [Decimal(input()) for i in range(n)]
vec25 = [[0 for i in range(50)] for i in range(50)]  # 整数にするのに余っている2,5の数
for i in range(n):
    a = int(vec[i] * 1000000000)
    num2 = -9
    num5 = -9
    while a%2 == 0:
        a //= 2
        num2 += 1
    while a%5 == 0:
        a //= 5
        num5 += 1
    vec25[num2][num5] += 1
for i in range(-9, 40): 
    for j in range(-9, 20):
        for k in range(max(-9, -i), 40):
            for l in range(max(-9, -j), 20):
                if i+k >= 0 and j+l >= 0 :
                    if i != k or j != l :
                        ans += vec25[i][j] * vec25[k][l]
                    else :
                        ans += vec25[i][j] * (vec25[i][j] - 1)
ans //= 2
print(ans)
### BUGGY CODE ###

import numpy as np
import math 
n = np.arange(int(input()))+1

sum = 0
for i in n:
  for j in n:
    for k in n:
      sum += math.gcd(math.gcd(i,j),k)
print(sum)

### FIXED CODE ###

import numpy as np
import math 
n = int(input())

s = np.zeros(3) # *3,*6

s[0] = n*(n+1)//2
for i in np.arange(n)+1:
  for j in np.arange(i+1,n+1):
    s[1] += math.gcd(i,j)
    for k in np.arange(j+1, n+1):
      s[2] += math.gcd(math.gcd(i,j),k)
print(int(sum(s*[1,6,6])))
### BUGGY CODE ###

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

parent=dict()
An=set(A)

for i in An:
    parent[i]=A.count(i)
parecou=0

#print(parent)
for i in parent:
    f=parent[i]
    parecou+=int((f*(f-1)/2))

#print(parecou)
for i in range(N):
    anko=parent[A[i]]
    #print(parecou-int((anko*(anko-1)/2))+int(((anko-2)*(anko-1)/2)))
    print(parecou-anko+1)


### FIXED CODE ###

from collections import Counter
N=int(input())
A=list(map(int,input().split()))

parent=dict()
An=set(A)
parecou=0
aaa=Counter(A)
for i in aaa.values():
    parecou+=int((i*(i-1)/2))
"""
for i in An:
    f=A.count(i)
    parent[i]=f
    parecou+=int((f*(f-1)/2))
"""


#print(parecou)
for i in range(N):
    anko=aaa[A[i]]
    print(parecou-int((anko*(anko-1)/2))+int(((anko-2)*(anko-1)/2)))
    #print(parecou-anko+1)
### BUGGY CODE ###

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

list_ans = []

for i in range(n-k+1):
    list_sum = list_score[i:i+k]
    list_ans.append(sum(list_sum))

list_ans.sort()


ans = list_ans[-1]*0.5 + 0.5*k

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
list_P = list(map(int, input().split()))
cnt = 0

for i in range(k):
    p = list_P[i]
    cnt += (1+p)/2

ans = cnt
for i in range(k, n):
    p, q = list_P[i-k], list_P[i]
    cnt -= (1+p)/2
    cnt += (1+q)/2
    ans = max(ans, cnt)

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

from collections import Counter
import numpy as np

N, K, Q = input().split()
A = np.array([int(input()) for i in range(int(Q))])
T = np.full(int(N), int(K))
#unique, counts = np.unique(A, return_counts=True)
#s =  dict(zip(unique, counts))
s = Counter(A)
for key, value in s.items():
    T[0:(key-1)] -= value
    T[key:len(T)] -= value
for i in T:
    if i <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

from collections import Counter
import numpy as np

N, K, Q = input().split()
A = np.array([int(input()) for i in range(int(Q))])
T = np.full(int(N), int(K))
T -= int(Q)
#unique, counts = np.unique(A, return_counts=True)
#s =  dict(zip(unique, counts))
s = Counter(A)
for key, value in s.items():
    T[(key-1)] += value
for i in T:
    if i <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

h = int(input())

log = {'1': 1 , '2': 3, '3': 3, '4': 7 }
i = 1
for i in range(1, h+1, 1):
    if not (str(i) in log):
        n = i // 2
        log.setdefault(str(i), log[str(n)]*2 +1)
        ##print("N(" + str(i)+ "):" + str(log[str(i)]))

print(log[str(h)])


### FIXED CODE ###

def input_int():
    return int(input())

def suss(num):
  result = 2
  while num > 1:
    num = num // 2
    result = result * 2
  return result - 1

h = input_int()
print(suss(h))
### BUGGY CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * n
r = [n] * n
mc = n
mr = n
for _ in range(q):
  m,q = list(map(int, input().split()))
  if m == 1:
    pos = r[q-1]
    if q < mc:
        mc = q
        c[:pos] = [q]*pos
    if q not in [1,n]:
      count -= max(0, pos - 2)
  else:
    pos = c[q-1]
    if q < mr:
        mr = q
        r[:pos] = [q] * pos
    if q not in [1,n]:
      count -= max(0, pos-2)
print(count)

### FIXED CODE ###

import os
import io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline


n, q = list(map(int, input().split()))
count = (n - 2) ** 2
c = [n] * (n + 1)
r = [n] * (n + 1)
mc = n
mr = n
for _ in range(q):
    m,q = list(map(int, input().split()))
    if m == 1:
        if q <= mc:
            count -= mr -2
            for p in range(q+1, mc):
                c[p] = mr
            c[q] = 0
            mc = q
        else:
            count -= c[q] - 2
    else:
        if q <= mr:
            count -= mc -2
            for p in range(q+1, mr):
                r[p] = mc
            r[q] = 0
            mr = q
        else:
            count -= r[q] - 2
print(count)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
 
def xor_(x, y):
    p, q = list(sorted([x, y]))
    p = bin(p)
    q = bin(q)
 
    i = -1
    r = str()
    while p[i] != 'b':
        if p[i] == q[i]:
            r = '0' + r
        else:
            r = '1' + r
        i -= 1
 
    while q[i] != 'b':
        r = q[i] + r
        i -= 1
    
    r = '0b' + r
 
    return(int(r, 0))
 
sum = 0
for i in range(n-1):
    for j in range(i+1, n):
        sum += xor_(a[i], a[j])
        sum = sum % (10**9 + 7)
 
print(sum)

### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    ret = 0
    magni = 1
    for j in range(60):
        bin_cnt = [0, 0]
        for i in range(n):
            a[i], b = divmod(a[i], 2)
            bin_cnt[b] += 1
        x, y = bin_cnt
        ret += x * y * magni % mod
        magni = magni * 2 % mod

    ret %= mod

    print(ret)


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

S = input()
dp = [[0]*13 for i in range(len(S)+1)]
dp[0][0] = 1
#print(dp[0])
for i in range(len(S)):
  c = S[i]
  if c == "?":
    for d in range(10):
      n = (d*(10**(len(S)-i-1)))%13
      for j in range(13):
        dp[i+1][j] += dp[i][(j+13-n)%13]
  else:
    n = (int(c)*(10**(len(S)-i-1)))%13
    for j in range(13):
      dp[i+1][j] = dp[i][(j+13-n)%13]
  for j in range(13):
    dp[i+1][j] = dp[i+1][j]%1000000007
  #print(dp[i+1])
print(dp[len(S)][5])


### FIXED CODE ###

S = input()
dp0 = [0]*13
dp0[0] = 1
dp = [dp0]
#print(dp[0])
for i in range(len(S)):
  dpi = dp[i]
  dpn = [0]*13
  c = S[i]
  e = (10**((len(S)-i-1)%12))%13
  if c == "?":
    for j in range(13):
      r = 0
      for d in range(10):
        r += dpi[(j+13-d*e)%13]
      dpn[j] = r%1000000007
  else:
    d = int(c)
    for j in range(13):
      dpn[j] = dpi[(j+13-d*e)%13]
  #print(dp[i+1])
  dp.append(dpn)
print(dp[len(S)][5])
### BUGGY CODE ###

K,S = map(int,input().split())
cnt = 0

for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i + j + k == S:
        cnt+=1

print(cnt)

### FIXED CODE ###

K,S = map(int,input().split())
cnt = 0

for i in range(K+1):
  for j in range(K+1):
      if (S - i - j) <= K:
        if S - i - j >= 0:
          cnt+=1
          
print(cnt)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    query = input().split()
    if query[0] == '1':
        s = s[::-1]
    elif query[1] == '1':
        s = query[2] + s
    elif query[1] == '2':
        s = s + query[2]
print(s)


### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
flag = 1
for i in range(q):
    query = input().split()
    if query[0] == '1':
        flag *= -1
    elif query[1] == '1':
        if flag == 1:
            s.appendleft(query[2])
        else:
            s.append(query[2])
    elif query[1] == '2':
        if flag == -1:
            s.appendleft(query[2])
        else:
            s.append(query[2])
if flag == 1:
    print(''.join(s))
else:
    print(''.join(list(s)[::-1]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
num,product = map(int,input().split())
order = math.ceil(len(str(product)) / num)

cnt = 10 ** order
gcd = 1
while(cnt > 1):
    calc = cnt ** num
    if calc > product:
        cnt = cnt - 1
    elif product % calc == 0:
        gcd = cnt
        break
    else:
        cnt = cnt - 1
print(gcd)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
from math import sqrt,floor
num,product = map(int,input().split())
cnt = int(sqrt(product) + 2)
dd = defaultdict(int)

for i in range(2,cnt):
    if product % i == 0:
        a = 0
        while product % i == 0:
            a += 1
            product = product // i
        dd[i] = a
if product != 1:
    dd[product] =  1
ans = 1
for p,n in dd.items():
    ans *= pow(p,floor(n/num))
print(ans)
### BUGGY CODE ###

import numpy as np

N,M=map(int,input().strip().split())
PY=np.array([list(map(int,input().strip().split())) for _ in range(M)])

l=[[] for n in range(N)]
for m in range(M):
    tmp=PY[m][0]
    l[tmp-1].append(PY[m][1])

for n in range(N):
    l[n].sort()

dp=[[0 for i in range(max(PY[:,1]))] for j in range(max(PY[:,0]))]
for n in range(N):
    if l[n]:
        for i in range(len(l[n])):
            city="000000"+str(n+1)
            year="000000"+str(i+1)
            dp[n][l[n][i]-1]=str(city[-6:]+year[-6:])
for n in range(len(PY)):
    print(dp[PY[n,0]-1][PY[n,1]-1])

### FIXED CODE ###

import numpy as np

N,M=map(int,input().strip().split())
PY=np.array([list(map(int,input().strip().split())) for _ in range(M)])

l=[[] for n in range(N)]
for m in range(M):
    l[PY[m,0]-1].append(PY[m,1])

dp={}
for n in range(N):
    if l[n]:
        l[n].sort()
        for i in range(len(l[n])):
            city="000000"+str(n+1)
            num="000000"+str(i+1)
            dp[(n,l[n][i]-1)]=str(city[-6:]+num[-6:])
for m in range(M):
    print(dp[(PY[m,0]-1,PY[m,1]-1)])