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

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

As = []
a_ = -1
for i in range(m):
  a = int(input())
  if a == a_ + 1:
    print(0)
    sys.exit()
  As.append(a)
  a_ = a

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 ###

s = input()
ans = 0
count = 0
for i in range(len(s)-3):
    for j in range(i+3,len(s)+1):
        ans = int(s[i:j])
        if ans % 2019 == 0:
            count += 1
print(count)


### FIXED CODE ###

s = input()
counts = [0]*2019
counts[0] += 1
num = 0
d = 1
for c in reversed(s):
    num += int(c) * d
    counts[num % 2019] += 1
    d *= 10
    d %= 2019
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
c = 0
n = 0
list = []
for l in range(1,N+1):
    list = []
    for i in range(1,int(N**0.5)):
        if i*i > l:
            break;       
        for j in range(1,int(N**0.5)):
            a = i*i + j*j + i*j
            for k in range(1,int(N**0.5)):
                if i*i + j*j + k*k + i*j +j*k + i*k == l:
                    list.append(1)
                    break;
    print(sum(list))

### FIXED CODE ###

N = int(input())
list = [0]*(N+1)
for i in range(1,100):  
    for j in range(1,100):
        a = i*i + j*j + i*j
        for k in range(1,100):
            a = i*i + j*j + k*k + i*j +j*k + i*k
            if a <= N:
                list[a] += 1
for i in range(1,N+1):
    print(list[i])
### BUGGY CODE ###

import math
from functools import reduce
import itertools

limit_num = int(input())

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

result = 0

num_list = list(itertools.product(range(1, limit_num + 1), repeat=3))
for num in num_list:
	result = result + gcd(num)

print(int(result))


### FIXED CODE ###

import math
from functools import reduce
import itertools

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

limit_num = int(input())
result_list = []
for num in itertools.product(range(1, limit_num + 1), repeat=3):
	result_list.append(gcd(num))

print(sum(result_list))
### BUGGY CODE ###

from collections import deque

# input
N, A, B, C = map(int, input().split())
S = []
for _ in range(N):
    S.append(input())

# process
dq = deque()
dq.append((A, B, C, ""))

for i, s in enumerate(S):
    l = len(dq)
    for _ in range(l):
        a, b, c, op = list(dq.popleft())

        if s == "AB":
            if b != 0:
                dq.append((a+1, b-1, c, op+"A"))
            if a != 0:
                dq.append((a-1, b+1, c, op+"B"))
        elif s == "BC":
            if c != 0:
                dq.append((a, b+1, c-1, op+"B"))
            if b != 0:
                dq.append((a, b-1, c+1, op+"C"))
        else:
            if c != 0:
                dq.append((a+1, b, c-1, op+"A"))
            if a != 0:
                dq.append((a-1, b, c+1, op+"C"))

# output
if len(dq) == 0:
    print("No")
else:
    print("Yes")
    _, _, _, op = dq[0]
    [print(x) for x in op]


### FIXED CODE ###

# input
N, A, B, C = map(int, input().split())
S = [input() for _ in range(N)]

# process
V = {"A":A, "B":B, "C":C}
S.append("XX")
op = ""
for i in range(N):
    s0, s1 = S[i]
    if V[s0] + V[s1] == 0:
        break
    
    x, y = s0, s1
    if V[s1] == 0 or (V[s0] != 0 and s1 in S[i+1]):
        x, y = s1, s0

    V[x] += 1
    V[y] -= 1
    op += x

# output
if len(op) != N:
    print("No")
else:
    print("Yes")
    [print(x) for x in op]
### BUGGY CODE ###

def calc_minus(n):
    return n - 1

n, k, q = map(int, input().split())
a_list = []
for _ in range(n):
    a_list.append(k)
#print(a_list)
for _ in range(q):
    a = int(input())
    a_list = list(map(calc_minus, a_list))
    #print(a_list)
    a_list[a-1] = a_list[a-1] + 1
    #print(a_list)

#print(a_list)
for j in a_list:
    if int(j) > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q = map(int, input().split()) #N人、K点、Q問
A = [int(input()) - 1 for i in range(Q)] #受験番号とリスト番号のズレを補正
# print(A)
P = [0] * N #持ち点
for j in range(Q):
    P[A[j]] +=1
for k in range(N):
    if P[k] > Q - K:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


import numpy as np


# In[71]:


N,M = map(int, input().split())
data = []
for i in range(N):
    data.append(list(map(int, input().split())))


# In[72]:


data = np.array(data)


# In[84]:


sorted_data = data[np.argsort(data[:, 0])]


# In[86]:


ans = 0
for i in range(N):
    if sum(sorted_data[:, 1][:i + 1]) < M:
        ans += sorted_data[i, 0] * sorted_data[i, 1]
        #print(i, sorted_data[i, 0], sum(sorted_data[:, 1][:i + 1]), ans)
    else:
        ans += sorted_data[i, 0] * (M - sum(sorted_data[:, 1][:i]))
        #print(i, sorted_data[i, 0], (M - sum(sorted_data[:, 1][:i])), ans)
        break

print(ans)


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[14]:


N,M = map(int, input().split())
AB = []
for _ in range(N):
    AB.append(list(map(int, input().split())))


# In[15]:


AB_s = sorted(AB, key=lambda x: x[0])

cnt = 0
ans = 0
for idx,lst in enumerate(AB_s):
#     print(lst)
    c = lst[0]
    n = lst[1]
    if n <= M-cnt:
        ans += c*n
        cnt += n
#         print(cnt)
    else:
        ans += c*(M-cnt)
        cnt += (M-cnt)
#         print(cnt)
        break
print(ans)


# In[ ]:
### BUGGY CODE ###

import numpy as np
input()
def f(s):
    if len(s)==0:
        return 0
    k=len(s)
    g=np.argmin(s)
    return s[g]*(g+1)*(k-g)+f(s[:g])+f(s[g+1:])
print(f(list(map(int,input().split()))))

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
p,q,r,d=[0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],0
for i in range(n):
    p[s[i]]=i
for i in range(n,0,-1):
    h=p[i]
    x,y=q[h],r[h]
    d+=i*(h-x+1)*(y-h+1)
    q[y+1],r[x-1]=x,y
print(d)
### BUGGY CODE ###

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

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

INF = float('inf')
dist = [INF]*n # dfsの条件式の書き換えに注意

ans = [-1]*(n)

from functools import lru_cache
@lru_cache(None)
def dfs(now,d):
    for next_v in es[now]:
        if dist[next_v] > d+1:
            dist[next_v] = d+1
            ans[next_v] = now+1
            dfs(next_v, dist[next_v])

start = 0
dist[start]=0 #初期化
dfs(start,0)

print('Yes')
print(*ans[1:],sep='\n')


### FIXED CODE ###

import heapq
n,m = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(m)]

es = [[] for i in range(n)]
for x,y in src:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

INF = float('inf')
ds = [INF] * n
ans = [-1]*(n)

def dijkstra(start, dists):
    dists[start] = 0
    hq = [(0,start)]
    heapq.heapify(hq)
    while hq:
        dist,v = heapq.heappop(hq)
        for to in es[v]:
            if dist+1 >= dists[to]: continue
            dists[to] = dist+1
            ans[to]=v+1
            heapq.heappush(hq, (dist+1,to))

dijkstra(0,ds)

print('Yes')
print(*ans[1:],sep='\n')
### BUGGY CODE ###

#https://atcoder.jp/contests/abc084/tasks/abc084_c
N = int(input())
CSF = [list(map(int,input().split())) for _ in range(N-1)]
for i in range(1,N+1):
    if i == N:
        print(0)
        break
    time = 0
    for j in range(i,N):
        if time == 0:
            time += CSF[j-1][1]  #はじめはS[j]秒経過  
        else:
            if time < CSF[j-1][1]:
                time = CSF[j-1][1]
            lv = CSF[j-1][1]
            while time > lv:  #timeがS[j]+F[j]またはS[j]より小さいなら
                lv += CSF[j-1][2]   #F[j]経過
        time += CSF[j-1][0]  #その後C[j]秒経過
    print(time)

### FIXED CODE ###

#https://atcoder.jp/contests/abc084/tasks/abc084_c
N = int(input())
CSF = [list(map(int,input().split())) for _ in range(N-1)]
for i in range(1,N+1):
    if i == N:
        print(0)
        break
    time = 0
    for j in range(i,N):
        if time == 0:
            time += CSF[j-1][1]  #はじめはS[j]秒経過  
        else:
            if time < CSF[j-1][1]:
                time = CSF[j-1][1]
           # lv = CSF[j-1][1]
            while time % CSF[j-1][2] != 0:  #timeがS[j]+F[j]またはS[j]より小さいなら
                time +=1   #F[j]経過
        time += CSF[j-1][0]  #その後C[j]秒経過
    print(time)
### BUGGY CODE ###

num = int(input())

words = []
for _ in range(num):
    words.append(input())


max_words = []
max_count = 0
for word in words:
    if word in max_words:
        continue

    if words.count(word) > max_count:
        max_count = words.count(word)
        max_words = [word]
    elif words.count(word) == max_count:
        max_words.append(word)

max_words.sort()

for max_word in max_words:
    print(max_word)

### FIXED CODE ###

import numpy as np

num = int(input())

words = []
for _ in range(num):
    words.append(input())

words = tuple(words)

d = {}
for word in words:
    if word in d:
        d[word] += 1
    else:
        d[word] =1


# keyをndarrayで取得
keys = np.array([a[0] for a in d.items()])

# valueをndarrayで取得
values = np.array([a[1] for a in d.items()])

# valueがmaxであるkeyを探してくる
keys_of_max_val = keys[values == values.max()]

keys_of_max_val.sort()

print('\n'.join(keys_of_max_val))
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0 for a in range(N)]

for i in range(1,N):
  dpa = []
  for j in range(max(0,i-K),i):
      dpx = abs(h[i]-h[j])+dp[j]
      dpa.append(dpx)
  dp[i] = min(dpa)


print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

l = int(input())

lst = list(str(l))
lin = list(map(int,lst[:]))

#print(l)
#print(lst)
#print(lin)

le = len(lin)

dp1 = [0] * le#A+BがL以下だとわかっている
dp2 = [0] * le#A+BがL以下だとわかっていない

dp1[0] = 1
dp2[0] = 2

for i in range(1,le):
    if lin[i] == 0:
        dp1[i] = (dp1[i-1] * 3)%(10**9+7)
        dp2[i] = dp2[i-1]
    else:
        dp1[i] = (dp1[i-1] * 3 + dp2[i-1])%(10**9+7)
        dp2[i] = dp2[i-1] * 2

print((dp1[-1]+dp2[-1])%(10**9+7))


### FIXED CODE ###

L = list(map(int,list(input())))
num = len(L)
mod = 10 ** 9 + 7

dp1 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点で
#既にA+BがL以下であることが分かっているような値組(A, B)の個数
dp2 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点では
#まだA+BがL以下になるかどうか分かっていないような値組 (A, B) の個数

dp1[0] = 1 #(A,B)=(0,0)
dp2[0] = 2 #(A,B)=(1,0),(0,1)

for i in range(1,num):
    if L[i] == 1:
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2
    else:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    dp1[i] %= mod
    dp2[i] %= mod

print((dp1[num-1] + dp2[num-1])%mod)
### BUGGY CODE ###

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

result = 0
for i in range(k,n+2):
  numbers = range(0,n+1)
  mins = sum(numbers[0:i])
  maxs = sum(numbers[-i:])
  result += maxs - mins +1


print(result)

### FIXED CODE ###

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

result = 0
for i in range(k,n+2):
  result += n*i-i*i+i+1


print(result%1000000007)
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())

def solve(w,v):
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    ans = dp[-1][-1]
    return ans
print(solve(w,v))

### FIXED CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())

def solve(w,v):
    dp = [[0]*(W+1) for i in range(N+1)]
    for i in range(1,N+1):
        for j in range(W+1):
            if j < w[i-1]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1])
    ans = dp[-1][-1]
    return ans
print(solve(w,v))
### BUGGY CODE ###

import bisect
n = int(input())
a = int(input())

color = [a]
color_min = a

for i in range(1, n):
    a = int(input())
    if color_min >= a:
        bisect.insort_left(color, a)
        color_min = a
    else:
        j = bisect.bisect_left(color, a)
        color.pop(j-1)
        bisect.insort_left(color, a)
        color_min = color[0]

print(len(color))


### FIXED CODE ###

from collections import deque
from bisect import bisect_left

n = int(input())
a = [int(input()) for _ in range(n)]

b = deque([])

for ai in a:
    if len(b) == 0:
        b.append(ai)
    else:
        if ai <= b[0]:
            b.appendleft(ai)
        else:
            idx = bisect_left(b, ai)
            b[idx-1] = ai

print(len(b))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

a.sort()

for b, c in bc:
        if c > a[0]:
                for i in range(b):
                        if c > a[0]:
                                del a[0]
                                a.append(c)
                        else:
                                break
        else:
                break


print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [[int(i) for i in input().split()] for i in range(m)]

bc.sort(key = lambda x:x[1], reverse = True)

a.sort()

a_count = 0
for b, c in bc:
        if c > a[a_count]:
                for i in range(b):
                        if c > a[a_count]:
                                a[a_count] = c
                                a_count += 1    
                        else:
                                break
                        if a_count == n:
                                        break

        else:
                break
        if a_count == n:
                break        

print(sum(a))
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    else:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    else:
        d[b].append(a)

q = deque([1])
alr = [1]
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
        if i in alr:
            continue
        alr.append(i)
        q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    for j in ans[1:]:
        print(j)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
d = [[] for _ in range(n+1)]
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)
### BUGGY CODE ###

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

for i in range(a, b+1):
    if i <= a + k - 1 or b + 1 - k <= i:
        print(i)

### FIXED CODE ###

import sys

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

for i in range(a, min(b, a + k)):
    print(i)

 # 左側の幅だけで全部網羅する場合
if b < a + k:
    print(b)
    sys.exit()

 # ベン図みたいにかぶってる時
for i in range(max( a + k, b + 1 - k ), b + 1):
    print(i)
### BUGGY CODE ###

def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def warshal_floyd(d,N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])

    return d

def main():
    N, M, L = map(int, input().split())
    d = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        A -= 1
        B -= 1
        d[A][B] = C
        d[B][A] = C

    e = warshal_floyd(d,N)
    f = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if e[i][j] <= L:
                f[i][j] = 1

    g = warshal_floyd(f,N)
    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if g[s][t] == float('inf'):
            print(-1)
        else:
            print(g[s][t]-1)
    



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

import itertools
import collections

n, m = map(int, input().split(" "))
t = [ [-1] * m for i in range(n) ]

NG='#'
OK='.'

ok_list = []
for i in range(n):
    for j,s in enumerate(input()):
        t[i][j] = s
        if s == OK:
            ok_list.append( (i, j ) )


def depth(t, src, dest):
    q = collections.deque()
    deadlist = { src: 0 }
    q.append( (src[0], src[1], 0) )

    while len(q) != 0:
        x, y, cost = q.popleft()
        for _x, _y in [(x+1, y), (x-1,y), (x,y+1),(x,y-1)]:
            if ((_x,_y) not in deadlist ) and \
                ( 0 <= _x < n) and (0 <= _y < m) and t[_x][_y] == OK:
                deadlist[(_x, _y)] = cost+1
                q.append((_x, _y, cost+1))

    return deadlist.get(dest, -1)


ans = 0
for src, dest in itertools.combinations(ok_list, 2):
    tmp = depth(t, src, dest)
    if ans < tmp:
        ans = tmp
print(ans)

### FIXED CODE ###

import itertools
import collections

n, m = map(int, input().split(" "))
t = [ [-1] * m for i in range(n) ]

NG='#'
OK='.'

ok_list = []
for i in range(n):
    for j,s in enumerate(input()):
        t[i][j] = s
        if s == OK:
            ok_list.append( (i, j ) )


def depth(t, src):
    q = collections.deque()
    deadlist = { src: 0 }
    q.append( (src[0], src[1], 0) )

    while len(q) != 0:
        x, y, cost = q.popleft()
        for _x, _y in [(x+1, y), (x-1,y), (x,y+1),(x,y-1)]:
            if ((_x,_y) not in deadlist ) and \
                ( 0 <= _x < n) and (0 <= _y < m) and t[_x][_y] == OK:
                deadlist[(_x, _y)] = cost+1
                q.append((_x, _y, cost+1))

    return max(deadlist.values())


ans = 0
for src in ok_list:
    tmp = depth(t, src)
    if ans < tmp:
        ans = tmp
print(ans)
### BUGGY CODE ###

N = int(input())
X = list(map(int, list(str(N))))


dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))


### FIXED CODE ###

N = input()
X = list(map(int, list(str(N))))

dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := 上からi番目の金額を丁度払う場合の最小値
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := 上からi番目の金額を１周り大きい額で支払う場合の最小値
dp1[0] = 0
for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))
### BUGGY CODE ###

S = input()
dp = [[0 for _ in range(13)] for l in range(len(S))]
S_li = [_ for _ in S]
S_li = S_li[::-1]
if S_li[0] == '?':
    dp[0][0:10] = [1,1,1,1,1,1,1,1,1,1]
else:
    dp[0][int(S_li[0])] = 1
for _ in range(1,len(S)):
    if S_li[_] == '?':
        for x in range(10):
            for y in range(13):
                dp[_][((x * (10 ** _)) + y) % 13] += dp[_ - 1][y] 
    else:
        for y in range(13):
            dp[_][((int(S_li[_]) * (10 ** _)) + y) % 13] += dp[_ - 1][y] 
print(dp[-1][5] % ((10 ** 9) + 7))

### FIXED CODE ###

MOD = 1000000007;
 
s = [int(x) if x!="?" else -1 for x in input()]
#print(s)
n=len(s)
 
r=[0]*13
 
c=s[0]
if (c!=-1):
    r[c]=1
else:
    for i in range(10):r[i]=1
for i in range(1,n):
    dp=[0]*26
    for j in range(13):dp[j*10%13]+=(r[j]%MOD)
    dp[13:26]=dp[0:13]
    c=s[i]
    r=[0]*13
    if (c==-1):
        w=sum(dp[4:14])
        for j in range(13):
            r[j]+=w
            w=w+dp[j+1]-dp[4+j]
    else:
        for j in range(13):
            r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###

def resolve():
    from collections import deque
    n, m = map(int, input().split())
    michi=s = [[0 for i in range(n)] for j in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        michi[a-1][b-1]=1
        michi[b - 1][a - 1] = 1
    heya=[-1]*n

    def f():
        check=0
        que = deque([])
        que.append(0)
        while que:
            if check==n:
                break
            else:
                p=que.popleft()
                for i in range(n):
                    if michi[p][i]==1 and heya[i]==-1:
                        heya[i]=p+1
                        check+=1
                        que.append(i)
        return

    f()
    print("Yes")
    for i in heya[1:]:
        print(i)
resolve()

### FIXED CODE ###

def resolve():
    from collections import deque
    n, m = map(int, input().split())
    michi = [[] for j in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        michi[a-1].append(b-1)
        michi[b - 1].append(a - 1)
    heya=[-1]*n

    def f():
        check=0
        que = deque([])
        que.append(0)
        while que:
            p = que.popleft()
            for i in michi[p]:
                if heya[i] == -1:
                    heya[i] = p + 1
                    check += 1
                    if check == n :
                        break
                    que.append(i)

        return

    f()
    print("Yes")
    for i in heya[1:]:
        print(i)
resolve()
### BUGGY CODE ###

def remain(pos):
  p=pos
  if p<0 or p>=n:
    return False
  for i in range(q):
    if s[p]==places[i]:
      if moves[i]=='L':
        p-=1
      if moves[i]=='R':
        p+=1
    if p<0 or p>=n:
      return False
    if p>q-i and n-p>q-i:
      return True
  return True

n,q=map(int,input().split())
s=input()
places=[]
moves=[]
for _ in range(q):
  p,m=map(str,input().split())
  places.append(p)
  moves.append(m)
l=-1
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid)==True:
    r=mid
  else:
    l=mid
remain_left=r
l=remain_left
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid)==True:
    l=mid
  else:
    r=mid
remain_right=l
print(remain_right-remain_left+1)

### FIXED CODE ###

def remain(pos,length):
  p=pos
  for c,d in moves:
    if s[p]==c:
      if d=='L':
        p-=1
      if d=='R':
        p+=1
    if p<0 or p>=length:
      return False
  return True

n,q=map(int,input().split())
s=input()
moves=[list(map(str,input().split())) for _ in range(q)]
l=-1
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid,n)==True:
    r=mid
  else:
    l=mid
remain_left=r
if remain_left==n:
  print(0)
  exit()
l=remain_left
r=n
while r-l!=1:
  mid=(l+r)//2
  if remain(mid,n)==True:
    l=mid
  else:
    r=mid
remain_right=l
print(remain_right-remain_left+1)