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

M=10**9+7
remain=[1,0,0,0,0,0,0,0,0,0,0,0,0]

#リストに入力（文字列）
text=input()
lst=list(text)
lst.reverse()


##漸化式を用意
ind=[1,-3,-4,-1,3,4]
def rec(ls,num,dig):
  val_ls=[0]*13
  if num!="?":
    for i in range(13):
      val_ls[i]=val_ls[i]+ls[(i-ind[dig]*int(num))%13]%M
  else:
    for i in range(13):
      for j in range(10):
        val_ls[i]=val_ls[i]+ls[(i-ind[dig]*j)%13]
        val_ls[i]=val_ls[i]%M
  return val_ls

##漸化式をremainに適用
for k in range(len(lst)):
  remain=rec(remain,lst[k],k%6)
  
print(remain[5])


### FIXED CODE ###

M=10**9+7
#リストに入力（文字列）
text=input()
lst=list(text)
lst.reverse()
digit=len(lst)
six=[[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]]
for i in range(digit):
  if(lst[i]=="?"):
    six[i%6][1]=six[i%6][1]+1
  else:
    six[i%6][0]=(six[i%6][0]+int(lst[i]))%13
rem=-(six[0][0]+10*six[1][0]+9*six[2][0]+12*six[3][0]+3*six[4][0]+4*six[5][0]-5)%13
######(?のいじったもの)+rem=0(mod13)
######(?*1+?*10+?*9+?*12+?*3+?*4)+rem=0
modulos=[1,0,0,0,0,0,0,0,0,0,0,0,0]
def mat1(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-1)%13]+ls[(i-2)%13]+ls[(i-3)%13]+ls[(i-4)%13]+ls[(i-5)%13]+ls[(i-6)%13]+ls[(i-7)%13]+ls[(i-8)%13]+ls[(i-9)%13])%M
  return val_ls
def mat10(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-10)%13]+ls[(i-20)%13]+ls[(i-30)%13]+ls[(i-40)%13]+ls[(i-50)%13]+ls[(i-60)%13]+ls[(i-70)%13]+ls[(i-80)%13]+ls[(i-90)%13])%M
  return val_ls
def mat100(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-9)%13]+ls[(i-18)%13]+ls[(i-27)%13]+ls[(i-36)%13]+ls[(i-45)%13]+ls[(i-54)%13]+ls[(i-63)%13]+ls[(i-72)%13]+ls[(i-81)%13])%M
  return val_ls
def mat1000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i+1)%13]+ls[(i+2)%13]+ls[(i+3)%13]+ls[(i+4)%13]+ls[(i+5)%13]+ls[(i+6)%13]+ls[(i+7)%13]+ls[(i+8)%13]+ls[(i+9)%13])%M
  return val_ls
def mat10000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-3)%13]+ls[(i-6)%13]+ls[(i-9)%13]+ls[(i-12)%13]+ls[(i-15)%13]+ls[(i-18)%13]+ls[(i-21)%13]+ls[(i-24)%13]+ls[(i-27)%13])%M
  return val_ls
def mat100000(ls):
  val_ls=[0]*13
  for i in range(13):
    val_ls[i]=(ls[i]+ls[(i-4)%13]+ls[(i-8)%13]+ls[(i-12)%13]+ls[(i-16)%13]+ls[(i-20)%13]+ls[(i-24)%13]+ls[(i-28)%13]+ls[(i-32)%13]+ls[(i-36)%13])%M
  return val_ls
for j in range(six[0][1]):
  modulos=mat1(modulos)
for j in range(six[1][1]):
  modulos=mat10(modulos)
for j in range(six[2][1]):
  modulos=mat100(modulos)
for j in range(six[3][1]):
  modulos=mat1000(modulos)
for j in range(six[4][1]):
  modulos=mat10000(modulos)
for j in range(six[5][1]):
  modulos=mat100000(modulos)
print(modulos[rem])
### BUGGY CODE ###

##N T
#t1 t2 ... tN
N, T = map(int,input().split())
a = list(map(int, input().split()))
b = []
"""
for i in range(N):
    set1 = set()
    for j in range(T):
        set1.add(a[i] + j)
    b.append(set1)
d = set()
for n in range(len(b)):
    d = d | b[n]
"""
d = set()
for i in range(N):
    d = d | set(range(a[i], a[i] + T))


print(len(d))

### FIXED CODE ###

##N T
#t1 t2 ... tN
N, T = map(int,input().split())
a = list(map(int, input().split()))
b = []
zo  = [0, T]
leng = T
"""
d = set()
for i in range(N):
    d = d | set(range(a[i], a[i] + T))
"""
for i in range(N):
    if  a[i] + T <= zo[1]:
        pass
    elif a[i] <= zo[1] and zo[1] <= a[i] + T:
        leng += a[i] + T - zo[1]
        zo[1] = a[i] + T
    elif zo[1] <= a[i]:
        zo[0] = a[i]
        zo[1] = a[i] + T
        leng += T






print(leng)
### BUGGY CODE ###

import sys

dp=[[0]*2019 for _ in range(2)]
dig=[int(c) for c in sys.stdin.readline().strip()]
tab=[[0]*2019 for _ in range(10)]

for x in range(10):
    for i in range(2019):
        tab[x][i]=(i*10+x)%2019

p=0
cnt=0
for x in dig:
    np=(p+1)&1
    for i in range(2019):
        dp[np][tab[x][i]]=dp[p][i]
    dp[np][x]+=1
    p=np
    cnt+=dp[p][0]

print(cnt)

### FIXED CODE ###

from collections import Counter
S=input()[::-1]

X=[0]
md=2019

for i,s in enumerate(S):
    X.append((X[-1]+int(s)*pow(10,i,md))%md)

C=Counter(X)
ans=0
for v in C.values():
    ans+=v*(v-1)//2

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

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

for i in range(n):
    l[i]=l[i]-(i+1)

a,b=min(l),max(l)

y=[]
for j in range(a,b+1):
    x=0
    for k in range(n):
        #print(abs(l[k]-j))
        x+=abs(l[k]-j)
    y.append(x)
    #print(x)

#print(n,l,y)
print(min(y))




### FIXED CODE ###

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

for i in range(n):
    l[i]=l[i]-(i+1)

from statistics import mean, median,variance,stdev
z=int(median(l))

x=0
for j in range(n):
    x+=abs(l[j]-z)

print(x)
### BUGGY CODE ###

import itertools
N = int(input())
a = list(map(int,input().split()))
a = [(i+1,a[i]) for i in range(N) if a[i]-i<2*1e5]
ans=0
for i in itertools.combinations(a,2):
  if abs(i[0][0]-i[1][0])==i[0][1]+i[1][1]:
    #print(i[0],i[1])
    ans+=1
print(ans)

### FIXED CODE ###

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

ans = 0

R = []
for i ,Ai in enumerate(A,1):
  R.append(i+Ai)
R.sort()

L = []
for j ,Aj in enumerate(A,1):
  L.append(j-Aj)
L.sort()

for i in range(len(R)):
  r = bisect.bisect_right(L,R[i])
  l = bisect.bisect_left(L,R[i])
  ans+=r-l
 
print(ans)
### BUGGY CODE ###

# coding: utf-8


def main():
    n = int(input())
    result = 1
    for i in range(2, n+1):
        result *= i
    print(result % 1000000007)

if __name__ == '__main__':
    main()

### FIXED CODE ###

# coding: utf-8


def main():
    n = int(input())
    result = 1
    for i in range(2, n+1):
        result *= i
        result %= 1000000007
    print(result)

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

a,b,x=map(int,input().split())
ans=0
for i in range(a,b+1):
    if i%x==0:
        ans+=1
    else:
        pass
print(ans)


### FIXED CODE ###

a,b,x=map(int,input().split())
ans=0
if (b-a+1)>=x:
    if a%x==0 and b%x==0:
        ans=((b-a)//x)+1
    elif not a%x==0 and not b%x==0:
        a=a+x-a%x
        b=b-b%x
        ans=((b-a)//x)+1
    elif not a%x==0 and b%x==0:
        a=a+x-a%x
        ans=((b-a)//x)+1
    elif a%x==0 and not b%x==0:
        b=b-b%x
        ans=((b-a)//x)+1
else:
    if a%x==0:
        ans=1
    else:
        if a+x-a%x<=b:
            ans=1
        else:
            ans=0
print(ans)
### BUGGY CODE ###


def main():
  n=int(input())
  s=input()
  ans=0
  for i in range(n):
    Z=[0]*n
    j=i+1
    while j<n:
      k=0
      while i+k<j and j+k<n and s[i+k]==s[j+k]:
        k+=1
        Z[j]=k
      if k>1:
        j+=k
      else:
        j+=1
      #j+=max(k,1)
    t=max(Z)
    if ans<t:
      ans=t
  print(ans)


if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  n=int(input())
  s=input()
  dp=[[0]*(n+1) for i in range(n+1)]
  for i in range(n-1,-1,-1):
    for j in range(n-1,i,-1):
      if s[i]==s[j]:
        dp[i][j]=dp[i+1][j+1]+1
  #for i in dp:
  #  print(i)
  
  ans=0
  for i in range(n-1):
    for j in range(i+1,n):
      ans=max(ans,min(j-i,dp[i][j]))
  print(ans)      
        

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

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
l.reverse()
cnt = 0 
flag = False
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if i == j:
            continue
        for k in range(j+1,n):
            if i == k and j == k:
                continue
            a = l[i]
            b = l[j]
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                cnt+=1
            else:
                flag=True
                break
print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
import bisect
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = bisect.bisect_left(l,target,j+1,n)
        cnt+= f1 - 1- j
   #     print("cnt: ",cnt)
print(cnt)
### BUGGY CODE ###

import math

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

for i in range(M):
  if (A[N - 1] < A[N - 2]):
    A.sort()
  A[N - 1] /= 2.0
amount = 0
for a in A:
  amount += math.floor(a)
print(amount)

### FIXED CODE ###

import math
import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda a: -int(a), input().split()))
A.sort()
heapq.heapify(A)

for i in range(M):
  a = heapq.heappop(A)
  a = -(-a / 2.0)
  heapq.heappush(A, a)

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)
### BUGGY CODE ###

N,K=map(int,input().split())
a=input().split()
A=[int(b) for b in a]

numbers=[]

for n in range(N-K+1):
    suuji=A[n:n+K]
    answer=1
    for k in suuji:
        answer*=k
    numbers.append(answer)

for k in range(N-K):
    if numbers[k]<numbers[k+1]:
        print('Yes')
    else:
        print('No')
        

### FIXED CODE ###

N,K=map(int,input().split())
a=input().split()
A=[int(b) for b in a]

for k in range(N-K):
    if A[k]<A[k+K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

s = input()
mod = 1000000007
a = 0
mae = 0
usi = s.count("?")
c = s.count("C")
ans = 0
for i in range(len(s)):
  if s[i] == "B":
    ans += (a*c*(3**(usi+mae)))%mod+(mae*c*(3**(mae-1+usi)))%mod+(usi*a*(3**(mae-1+usi)))%mod+(usi*mae*(3**(mae-2+usi)))%mod
  if s[i] == "?":
    usi -= 1
    ans += (a*c*(3**(usi+mae)))%mod+(mae*c*(3**(mae-1+usi)))%mod+(usi*a*(3**(mae-1+usi)))%mod+(usi*mae*(3**(mae-2+usi)))%mod
    mae +=1
  if s[i] == "A":
    a +=1
  if s[i] == "C":
    c -=1
print(int(ans%mod))

### FIXED CODE ###

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
s = input()
mod = 1000000007
a = 0
mae = 0
usi = s.count("?")
c = s.count("C")
ans = 0
for i in range(len(s)):
  if s[i] == "B":
    ans += (a*c*(power_func(3,usi+mae,mod)))%mod+(mae*c*(power_func(3,usi+mae-1,mod)))%mod+(usi*a*(power_func(3,usi+mae-1,mod)))%mod+(usi*mae*(power_func(3,usi+mae-2,mod)))%mod
  if s[i] == "?":
    usi -= 1
    ans += (a*c*(power_func(3,usi+mae,mod)))%mod+(mae*c*(power_func(3,usi+mae-1,mod)))%mod+(usi*a*(power_func(3,usi+mae-1,mod)))%mod+(usi*mae*(power_func(3,usi+mae-2,mod)))%mod
    mae +=1
  if s[i] == "A":
    a +=1
  if s[i] == "C":
    c -=1
print(int(ans%mod))
### BUGGY CODE ###

n = int(input())
a = [0 for i in range(22369621)]
for i in range(n):
    s = input().split(" ")
    num = 0
    p = 1
    for j in range(len(s[1])):
        if s[1][j] == "A":
            num += p * 1
        elif s[1][j] == "C":
            num += p * 2
        elif s[1][j] == "G":
            num += p * 3
        else:
            num += p * 4
        p *= 4
    if s[0][0] == "i":
        a[num] = 1
    else:
        if a[num] == 1:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

n = int(input())
dic = set()
for i in range(n):
    Cmd, Key = input().split(" ")
    if Cmd == "insert":
	    dic.add(Key)
    else:
        if Key in dic:
	        print("yes")
        else:
            print("no")
### BUGGY CODE ###

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

result = 0

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

print(result)

### FIXED CODE ###

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

result = 0

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

N=int(input())
x=[int(input()) for _ in range(N)]

#x=dict(zip(range(1,N+1),a))
route=[1,]
while 2 not in route:
  #print(x[route[-1]])
  if x[route[-1]-1] not in route:
    route.append(x[route[-1]-1])
  else:
    print(-1)
    exit()
print(len(route)-1)

### FIXED CODE ###

N=int(input())
x=[int(input()) for _ in range(N)]

on=1
ans=0
for _ in range(N):
  on=x[on-1]
  ans=ans+1
  if on==2:
    print(ans)
    exit()
  
print(-1)
### BUGGY CODE ###

n = int(input())
l = input().split(' ')
l = [int(i) for i in l]
l.sort(reverse=True)

addList = []
for i in range(n):
    for j in range(i+1, n):
        addList.append({
            "num": l[i] + l[j],
            "i": i,
            "j": j
        })

# print(l)
cnt = 0
st = 0
for a in addList:
    for i in range(st, n):
        if a["i"] <= i or a["j"] <= i:
            # print(i, a["i"], a["j"])
            continue
        if a["num"] > l[i]:
            cnt += 1
            # print(i, a["i"], a["j"])
        else:
            st = i

print(cnt)


### FIXED CODE ###

import bisect

n = int(input())
l = input().split(' ')
l = [int(i) for i in l]
l.sort()

cnt = 0
for i in range(n):
    for j in range(i+1, n):
        num = l[i] + l[j]
        index = bisect.bisect_left(l, num)
        # print(index, j)
        # print(index-2)
        cnt += (index-j-1)

print(cnt)
### BUGGY CODE ###

H, N = map(int, input().split())
AB = []
INF = 10**8 + 1

dp = [INF]*(H+1)
dp[0] = 0

for _ in range(N):
  a, b = map(int, input().split())
  AB.append((a, b))

for i in range(1, H+1):
  for j in range(N):
    dp[i] = min(dp[i], dp[max(0, i - AB[j][0])] + AB[j][1])

print(dp[-1])

### FIXED CODE ###

H, N = map(int, input().split())
AB = []
INF = 10**8 + 1

dp = [INF]*(H+1)
dp[0] = 0

for _ in range(N):
  a, b = map(int, input().split())
  AB.append((a, b))

for i in range(1, H+1):
  for j in range(N):
    dp[i] = min(dp[i], dp[max(0, i - AB[j][0])] + AB[j][1])

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

from itertools import combinations
import sys

input = sys.stdin.buffer.readline

n = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
# LCAが必要そう
# 慣れないけどdoublingしてみる？
# 実行時間に余裕があるし、毎回DFSしていい気がしてきた。
# 通った辺を(a,b)の形でsetに打ち込んで全部白になる場合の数を調べる方針


def dfs(s, g):
    kouho = set()
    par = [-1] * (n + 1)
    depth = [0] * (n + 1)
    stack = []
    stack.append(s)
    while stack:
        v = stack.pop()
        if v == g:
            break
        d = depth[v]
        for u in graph[v]:
            if u == par[v]:
                continue
            par[u] = v
            depth[u] = d + 1
            stack.append(u)
    # 経路復元
    p = g
    q = par[g]
    while q > 0:
        kouho.add((min(p, q), max(p, q)))
        p = q
        q = par[q]
    return kouho


m = int(input())
sets = [[] for _ in range(m)]
for i in range(m):
    u, v = map(int, input().split())
    sets[i] = dfs(u, v)
ans = 0
for i in range(1, m + 1):
    kumiawase = list(combinations(range(m), i))
    for kumi in kumiawase:
        temp = set()
        for j in range(i):
            temp |= sets[kumi[j]]
        num = len(list(temp))
        ans += (-1) ** (i + 1) * (pow(2, n - 1) - pow(2, n - 1 - num))

print(ans)


### FIXED CODE ###

from itertools import combinations
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n = int(readline())
AB = list(list(map(int, readline().split())) for _ in range(n - 1))
m = int(readline())
UV = list(list(map(int, readline().split())) for _ in range(m))

graph = [[] for _ in range(n + 1)]
for i, (a, b) in enumerate(AB):
    graph[a].append((b, i))
    graph[b].append((a, i))


def dfs(s, g):
    kouho = 0
    par = [(0, 0)] * (n + 1)
    stack = []
    stack.append(s)
    while stack:
        v = stack.pop()
        if v == g:
            break
        for u, i in graph[v]:
            if u == par[v][0]:
                continue
            par[u] = (v, i)
            stack.append(u)
    # 経路復元
    p = g
    q, i = par[p]
    while q > 0:
        kouho |= 1 << i
        p = q
        q, i = par[q]
    return kouho


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


sets = [0 for _ in range(m)]

for idx, (u, v) in enumerate(UV):
    sets[idx] = dfs(u, v)
ans = 0
for i in range(1, m + 1):
    kumiawase = list(combinations(range(m), i))
    for kumi in kumiawase:
        temp = 0
        for j in range(i):
            temp |= sets[kumi[j]]
        num = popcnt(temp)
        ans += (-1) ** (i + 1) * (pow(2, n - 1) - pow(2, n - 1 - num))

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

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

order = []


for i in range(1,n+1):
    order.append(a.index(i)+1)
    

for i in range(n):
    order[i] = str(order[i])

print(' '.join(order))

### FIXED CODE ###

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

ans = [0 for i in range(n)]

for i in range(n):
    ans[a[i]-1] = i+1

print(' '.join(map(str,ans)))
### BUGGY CODE ###

S = input()
K = int(input())
N = len(S)
C = []
for i in range(N):
    for j in range(i,N):
        C.append(S[i:j+1])
C.sort()
b = ""
k = 0
for c in C:
    if b!=c:
        k+=1
        b=c
    if k==K:
        print(b)
        break

### FIXED CODE ###

S = input()
K = int(input())
N = len(S)
C = set()
for i in range(N):
    for j in range(i,min(i+K,N)):
        C.add(S[i:j+1])
C = sorted(C)
print(C[K-1])
### BUGGY CODE ###

a, b, x = [int(s) for s in input().rstrip().split()]
for i in range(a, a+x):
    if i % x == 0:
        min = i
        break
for i in range(b, b-x, -1):
    if i % x == 0:
        max = i
        break
print((max - min) // x + 1)

### FIXED CODE ###

a, b, x = [int(s) for s in input().rstrip().split()]
if a % x == 0:
    ans = b // x - a // x + 1
else:
    ans = b // x - a // x
print(ans)
### BUGGY CODE ###

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

y=x
A=[]
A.append(y)
cnt=1
su=x

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)
        su+=y

c=A.index(y) #周期のはじめ
d=cnt-(c+1)  #周期のはじめから次の周期のはじめで個数を求める

e=sum(A[:c]) 
#周期に入るまえまでを足しておく

f=0
for w in range((n-c)%d):
    f+=A[c:][w]
    #周期からはみでた最後の部分

g=su-e#1周期分
h=g*((n-c)//d)#かけざん

print(e+h+f)

### FIXED CODE ###

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

y=x
A=[]
A.append(y)
cnt=1
su=x

for i in range(m):
    y=(y**2)%m
    cnt+=1
    if y in A:
        break
    else:
        A.append(y)
        su+=y

c=A.index(y) #周期のはじめ
d=cnt-(c+1)  #周期のはじめから次の周期のはじめで個数を求める

e=sum(A[:c]) 
#周期に入るまえまでを足しておく


f=sum(A[c:c+(n-c)%d])
    #周期からはみでた最後の部分

g=su-e#1周期分
h=g*((n-c)//d)#かけざん

print(e+h+f)
### BUGGY CODE ###

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, readline().split()))
    a = [list(str(readline().rstrip().decode('utf-8'))) for _ in range(h)]

    ql = [[0, 0, 0]]
    ql = collections.deque(ql)
    cl = collections.defaultdict(int)
    cl[0, 0] = 1
    while True:
        if len(ql) != 0:
            cost, x, y = ql.popleft()
            for xv, yv in [[x + 1, y], [x, y + 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if a[xv][yv] != "#":
                        ql.append([cost + 1, xv, yv])
                        cl[xv, yv] = cl[x, y]
                        a[xv][yv] = "#"
                    else:
                        cl[xv, yv] += cl[x, y]
                        cl[xv, yv] % mod
        else:
            break
    print(cl[h-1, w-1] % mod)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    dp = [[0] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                dp[i][j] = 0
            elif i == 0 and j == 0:
                dp[i][j] = 1
            elif i == 0:
                dp[i][j] = dp[i][j-1]
            elif j == 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % mod
    print(dp[-1][-1])


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

import random

def used(dp,u,v,w):
    n=len(dp)
    for i in range(n):
        for j in range(i+1,n):
            if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                return True
    return False

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    random.shuffle(es)

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    print(sum(int(not used(dp,u,v,w)) for u,v,w in es))


### FIXED CODE ###

def used(dp,u,v,w):
    n=len(dp)
    for i in range(n):
        for j in range(i+1,n):
            if dp[i][j]==dp[i][u]+w+dp[v][j] or dp[i][j]==dp[i][v]+w+dp[u][j]:
                return True
    return False

while 1:
    try:
        n,m=map(int,input().split())
        es=[]
        for _ in range(m):
            u,v,w=map(int,input().split())
            es.append((u-1,v-1,w))
    except: break

    dp=[[float('inf')]*n for _ in range(n)]
    for i in range(n):
        dp[i][i]=0
    for u,v,w in es:
        dp[u][v]=dp[v][u]=w
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
    print(sum(int(not used(dp,u,v,w)) for u,v,w in es))
### BUGGY CODE ###

sta = input("station:")

while len(sta) == 3:
    judge = ""
    count = 0
    result = ""
    for s in sta:
        if count == 0:
            judge = s
            count += 1
        else:
            if s == judge:
                result = "No"
            else:
                result = "Yes"

### FIXED CODE ###

while True:
    sta = input()
    if len(sta) == 3:
        break

judge = ""
count = 0
result = ""
station = [sta[0], sta[1], sta[2]]
for ss in station:
    if count == 0:
        judge = ss
    else:
        if ss == judge:
            result = "No"
        else:
            result = "Yes"
            break
            
    count = 1
print(result)
### BUGGY CODE ###

num, capacity = list(map(int, input().split()))
dp = [0 for i in range(capacity + 1)]

for i in range(1, num + 1):
    weight, value = list(map(int, input().split()))
    for w in range(capacity,-1,-1):
        if w - weight >= 0:
            dp[w] = max( dp[w - weight] + value,  dp[w] )
print(dp[capacity])

### FIXED CODE ###

def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]

num, capacity = map(int, input().split())
print(calc(num,capacity))
### BUGGY CODE ###

N = int(input())
S = 0
for i in range(2*10**5):
  digit = N%10
  S += digit
  N = N//10
T = 0
while S > 0:
  digit = S%10
  T += digit
  S = S//10
if T%9 == 0:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

N = int(input())
if N%9 ==0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import math
L, R = map(int, input().split())
R=min(R,L+2019*2)
m=2018
for i in range(L,R+1):
  for j in range(i,R+1):
    if i==j:
      continue
    if (i*j)%2019<m:
      m=(i*j)%2019
print(m)

### FIXED CODE ###

import math
L, R = map(int, input().split())
R=min(R,L+2019)
m=2018
for i in range(L,R+1):
  for j in range(i,R+1):
    if i==j:
      continue
    if (i*j)%2019<m:
      m=(i*j)%2019
print(m)