Harryxun/stf_run huggingface dataset:
import sys
from time import time
from random import randint
from numpy import int64

def func(s, x, score, t1, t2, t3):
    if t1 == -1:
        for i in range(26):
            last = 0
            for j, v in enumerate(x, 1):
                if v == i:
                    last = j
                    score[i] += s[j * 26 + v]
                score[i] -= s[i] * (j - last)    
    if t1 > -1:
        last = score[t1] = 0
        for i, v in enumerate(x, 1):
            if v == t1:
                last = i
                score[t1] += s[i * 26 + v]
            score[t1] -= s[t1] * (i - last)
    if t2 > -1:
        last = score[t2] = 0
        for i, v in enumerate(x, 1):
            if v == t2:
                last = i
                score[t2] += s[i * 26 + v]
            score[t2] -= s[t2] * (i - last)
    if t3 > -1:
        last = score[t3] = 0
        for i, v in enumerate(x, 1):
            if v == t3:
                last = i
                score[t3] += s[i * 26 + v]
            score[t3] -= s[t3] * (i - last)
    score[26] = score[:26].sum()
    return score

def main():
    start = time()
    d, *s = map(int, sys.stdin.buffer.read().split())
    s = int64(s)
    x = int64(([*range(26)] * 15)[:d])
    score = func(s, x, int64([0] * 27), -1, -1, -1)
    while time() - start < 1.8:
        y = x.copy()
        if randint(0, 1):
            i = randint(0, d - 1)
            j = k = -1
            y[i] = randint(0, 25)
        elif randint(0, 1):
            i = randint(0, d - 16)
            j = randint(i + 1, i + 15)
            k = -1
            y[i], y[j] = y[j], y[i]
        else:
            i = randint(0, d - 15)
            j = randint(i + 1, i + 7)
            k = randint(j + 1, j + 7)
            if randint(0, 1):
                y[i], y[j], y[k] = y[j], y[k], y[i]
            else:
                y[i], y[j], y[k] = y[k], y[i], y[j]
        t = func(s, y, score, i, j, k)
        if t[26] > score[26]:
            score = t
            x = y
    print(*x + 1, sep='\n')

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('func', 'i8[:](i8[:], i8[:], i8[:], i8, i8, i8)')(func)
    cc.compile()

if __name__ == '__main__':
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import func
    main()

### FIXED CODE ###

from time import time
from random import randint

from numba import njit
from numpy import int64

@njit('i8(i8[:],i8[:])')
def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(last[j]-i)
        score=score+s[i*26+v]-c
    return score

def main():
    start=time()
    d,*s=map(int,open(0).read().split())
    s=int64(s)
    x=int64(([*range(26)]*15)[:d])
    M=func(s,x)
    while time()-start<1:
        y=x.copy()
        y[randint(0,d-1)]=randint(0,25)
        t=func(s,y)
        if t>M:
            M=t
            x=y
    print(*x+1,sep='\n')

main()
from heapq import heappop, heappush


def calculate(N,M,arr):
    ret = 0

    j = 0

    res = []

    # 1,2,3,4,5
    #         ↑
    # 4,3,2,1

    # M = 4
    # range(1,5) => 1,2,3,4

    for i in range(1,M+1):
        # i = 1,2,3
        # 比如M=4的话，第三天(最多1天),第二天(最多2天),第一天(最多3天)

        # 记下来循环打工信息资源,以j为标记
        # j为资源编号
        # arr[j][0]为该编号资源的天数


        # 候补的资源，满足所有天数，因为是满足后续的天数来算的

        while (j < N) and (arr[j][0] <= i):

                heappush(res, -arr[j][1])
                j = j + 1 #j找到的话就往上顶一格，一共这一天，或者前一天寻找的时候以下一个资源天为开始

        if len(res) > 0:
            ret -= heappop(res)

    return ret


N,M = map(int,input().split())


# 后面的逻辑是基于前面的从小到大的排序的
list = [list(map(int,input().split())) for i in range(N)]

arr = sorted(list,key=lambda x:x[0])

result = calculate(5,3,arr)

print(result)



### FIXED CODE ###

from heapq import heappush, heappop
n, m = map(int, input().split())
jobs = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a > m:
    continue
  if a in jobs:
    jobs[a].append(b)
  else:
    jobs[a] = [b]
result = 0
candidates = []
for a in range(1, m + 1):
  if a in jobs:
    for b in jobs[a]:
      heappush(candidates, -b)
  else:
    if len(candidates) == 0:
      continue
  result += -heappop(candidates)
print(result)
n = int(input())
x = sorted([list(map(int, input().split())) for _ in range(n)])

cnt = n
j = 0
for i in range(n):
    if x[j][0] + x[j][1] > x[j + 1][0] - x[j][1]:
        cnt -= 1
        j += 1
    j += 1
    if j >= n - 1:
        break
print(cnt)

### FIXED CODE ###

n = int(input())
robots = []
for i in range(n):
    x, l = map(int, input().split())
    robots.append([x + l, x - l])
robots.sort()

r = - 10 ** 9 - 1
cnt = 0
for i in range(n):
    if r <= robots[i][1]:
        cnt += 1
        r = robots[i][0]
print(cnt)
# PrimeNumber
# エラトステネスの篩

from itertools import product
import math

if __name__ == "__main__":
    while True:
        try:
            # 数値の入力があった
            n = int(input())
            nlist = []
            nlist2 = []
            plist = []

            # for i in range(2, n + 1):
            #    nlist.append(i)  # [2,3,4,5,6,...,n]
            nlist = range(2, n + 1, 1)

            while True:
                #print(nlist, " ", math.sqrt(n))
                sqrtn = math.sqrt(n)
                if nlist[0] > sqrtn:  # 終了条件
                    #plist.append(map(int,nlist))
                    plist.extend(nlist)
                    break
                else:
                    plist.append(nlist[0])

                    #i = 0
                    for j in nlist:
                        if j % nlist[0] != 0:
                            #nlist.pop(i)
                            #nlist.remove(j)
                            nlist2.append(j)
                            #i += 1
                    nlist = nlist2
                    nlist2 = []
            #print("fin: {}".format(plist))
            print(len(plist))

        except EOFError:
            break  # escape from while loop

pass
#

### FIXED CODE ###

if __name__ == "__main__":
	maxn = 1000000
	plist = [False if i%2==0 or i%3==0 or i%5==0 else True for i in range(maxn)]

	plist[0] = plist[1] = False
	plist[2] = plist[3] = plist[5] = True

	for chki in range(3, maxn, 2):
		for j in range(chki**2, maxn, chki):
			plist[j] = False

	while True:
		try:
			#start = time.time()
			inn = int(raw_input())
			print plist[0:inn+1].count(True)
			#print plist
			#print plist.count(True)
			#print plist[0:10].count(True)
			#print plist[0:100000].count(True)
			#print plist[0:1000000].count(True)

			#elapsedTime = time.time() -start
			#print elapsedTime
		except:
			break
n = int(input())
a = list(map(int,input().split()))
a.sort()

if a[0]>=0:
    g=sum(a[1:])-a[0]
    print(g)
    for i in range(n-1):
        if len(a)>2:
            print(str(a[0])+" "+str(a[-1]))
            a[0]-=a[-1]
            a.remove(a[-1])
        else:
            print(str(a[1])+" "+str(a[0]))
    
elif a[-1]<=0:
    g=a[-1]-sum(a[:-1])
    print(g)
    for i in range(n-1):
        print(str(a[-1])+" "+str(a[0]))
        a[-1]-=a[0]
        a.remove(a[0])
else:
    g=0 
    for i in range(n):
        g+=abs(a[i])
    print(g)
    for _ in range(n-1):
        if a[-2]>=0:
            print(str(a[0])+" "+str(a[-1]))
            a[0]-=a[-1]
            a.remove(a[-1])
        else:
            print(str(a[-1])+" "+str(a[0]))
            a[-1]-=a[0]
            a.remove(a[0])



### FIXED CODE ###

a,b = map(int,input().split())
if b==1:
  print(0)
else:
  print(a-b)
n = input()
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
X = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
color = [0 for i in range(n)]
t = 0
 
def DFS_v(u):
    color[u] = 1
    t += 1
    d[u] = t
    for v in range(n):
        if M[u][v] == 1 and color[v] == 0:
            DFS_visit(v)
    color[u] = 2
    t += 1
    f[u] = t
 
def DFS():
    for u in range(n):
        if color[u] == 0:
            DFS_v(u)
    for u in range(n):
        print "%d %d %d" %(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
n=int(input())
a=[list(input()) for i in range(n)]
if max(a[i].count("#") for i in range(n)) ==0:
  print(-1)
  exit()
minus=0
for i in range(n):
  if a[i].count(".")==0:
    minus=n
    break
  if a[i][i]=="#":
    minus=max(minus,a[i].count("#"))
b=zip(*a)
for j in range(n):
  if b[j].count(".")==0:
    minus+=1
print(2*n-minus)

### FIXED CODE ###

n=int(input())
a=[list(input()) for i in range(n)]
if max([a[i].count("#") for i in range(n)]) ==0:
  print(-1)
  exit()
minus=0
b=list(zip(*a))
for i in range(n):
  if b[i].count("#")>=1:
    minus=max(minus,a[i].count("#"))
  else:
    minus=max(minus,a[i].count("#")-1)
for j in range(n):
  if b[j].count(".")==0:
    minus+=1
print(2*n-minus)
n = int(input())
d = list(map(int,input().split()))
p = 0
q = 0
d.sort(key=int)
if (len(d))%2 == 0:
  m = (d[(len(d)//2)-1]+d[len(d)//2])/2
else:
  m = d[(len(d)//2)]
for i in range(len(d)):
  if d[i]>=m:
    if d[i] == d[i+1]:
        p = d[i]
        q = d[i+1]
        break
    else:
      p = d[i]
      q = d[i-1]
      break
print(p-q)

### FIXED CODE ###

n = int(input())
d = sorted(list(map(int,input().split())))
print(d[n//2]-d[n//2-1])
from scipy.special import comb
n,k=map(int,input().split())
mod=10**9+7
ans=[n-k+1]
for i in range(2,k+1):
        if n-k+1<i:
                ans.append(0)
        else:
                k_sep=(comb(k-1,i-1,exact=True))%mod
                if n-k==i-1:
                        l_sep=1
                elif n-k==i:
                        l_sep=n-k+1
                else:
                        l_sep=(comb(n-k-1,i-2,exact=True)+2*comb(n-k-1,i-1,exact=True)+comb(n-k-1,i,exact=True))%mod
                ans.append(k_sep*l_sep)
for ii in range(k):
        print(ans[ii])

### FIXED CODE ###

from math import factorial

def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))

n,k=map(int,input().split())
mod=10**9+7
ans=[n-k+1]
for i in range(2,k+1):
        if n-k+1<i:
                ans.append(0)
        else:
                k_sep=(combinations_count(k-1,i-1))%mod
                if n-k==i-1:
                        l_sep=1
                elif n-k==i:
                        l_sep=n-k+1
                else:
                        l_sep=(combinations_count(n-k-1,i-2)+2*combinations_count(n-k-1,i-1)+combinations_count(n-k-1,i))%mod
                ans.append((k_sep*l_sep)%mod)
for ii in range(k):
        print(ans[ii])
s=input()
t=input()
o=0
for x,y in s,t:
  if x != y:
    o+=1
print(o)
  

### FIXED CODE ###

s=input()
t=input()
o=0
for i in range(len(s)):
  if s[i]!=t[i]:
    o+=1
print(o)
N, M = map(int, input().split())
A = list(map(int, input().split()))

if len([c for c in A if c >= sum(A) / (4 * M)]) >= M:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# 1行、2変数を受け取るとき
X, Y, Z = map(int, input().split())

print("{} {} {}".format(Z, X, Y))
# -*- coding: utf-8 -*-
a,b,c = [int(i) for i in input().split()]
if 1 <= a and b and c m<= 100:
    if b - a == c - b:
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b,c = [int(i) for i in input().split()]
if 1 <= a and b and c <= 100:
    if b - a == c - b:
        print("YES")
    else:
        print("NO")
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from math import factorial

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  min = 0
  max = 0
  for i in range(n-k+1):
    x = (factorial(n-(i+1)) / factorial(k-1) / factorial((n-(i+1)) - (k-1)))
    min += As[i]      * int(x)
    max += As[-(i+1)] * int(x)
  print((max - min) % (10**9 + 7))

if __name__=='__main__':
  main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

import random

MAX = 10**9 + 7

def pow_mod_p(n, k, p):
  x = 1
  while k > 0:
    if k % 2 == 1:
      x *= n
      x %= p
    n **= 2
    n %= p
    k >>= 1
  return x

def comb_mod_p(n, k, p):
  x = 1
  for ik in range(k):
    x *= ((n-ik) * pow_mod_p(ik+1, p-2, p))
    x %= p
  return x

def main():
  n, k = map(int, input().strip().split())
  As = list(map(int, input().strip().split()))
  As.sort()
  min = 0
  max = 0
  x = comb_mod_p(n-1, k-1, MAX)
  for i in range(n-k+1):
    min += As[i]      * int(x)
    min %= MAX
    max += As[-(i+1)] * int(x)
    max %= MAX
    x *= (pow_mod_p(n-(i+1), MAX-2, MAX) * (n-(i+1)-(k-1)))
    x %= MAX
  print((max - min) % (MAX))

if __name__=='__main__':
  main()
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
L = [0]*n
R = [0]*n
def left(i):
    if L[i]:
        return L[i]
    if i < 1:
        return 0
    L[i] = gcd(left(i-1), A[i-1])
    return L[i]
def right(i):
    if R[i]:
        return R[i]
    if i+1 > n-1:
        return 0
    R[i] = gcd(right(i+1), A[i+1])
    return R[i]
ans = 0
for i in range(n):
    g = gcd(left(i), right(i))
    if ans < g:
        ans = g
print(ans)

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
n = int(input())
A = list(map(int, input().split()))
L = [0]*n
R = [0]*n
for i in range(n-1):
    R [i+1] = gcd(R[i], A[i])
    L[i+1] = gcd(L[i], A[-i-1])
print(max(gcd(R[i], L[-i-1]) for i in range(n)))
N, M = input().split()
A = input().split()

N = int(N)
M = int(M)
#print(N,M,A)

sum = 0
for i in A:
    sum += int(i)

#print(sum)

ans = N - sum
if(ans > = 0):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

N, M = input().split()
A = input().split()

N = int(N)
M = int(M)
#print(N,M,A)

sum = 0
for i in A:
    sum += int(i)

#print(sum)

ans = N - sum
if(ans >= 0):
    print(ans)
else:
    print(-1)
n,m=map(int,input().split())
a=0
if m!=0:
    a=int(input())
b=1
s=[1]*(n+1)
for i in range(1,n+1):
    if i!=a:
        if i-2>=0:
            s[i]=(s[i-1]+s[i-2])%1000000007
        else:
            s[i]=s[i-1]%1000000007
    elif b!=m:
        s[i]=0
        a=int(input())
        b+=1
    else:
        s[i]=0
print(s[n])
        


### FIXED CODE ###

li=list(map(int,input().split()))
print(min(li[0]+li[1],li[0]+li[2],li[1]+li[2]))
if A%2==0 or B%2==0:
  return 'Yes'
else:
  return 'No'

### FIXED CODE ###

A,B=list(map(int,input().split()))
x=A*B
if x%2==0:
  print('No')
else:
  print('Yes')
N = int(input())
l = list()

for n in range(N):
    a = input()
    l.append(a)

l_uniq = list(set(l))

if len(l) == len(l_uniq):
    for i in range(0, N-1):
        if a[i+1][0] != a[i][-1]:
            print("No")
            break
    print("Yes")
else:
    print("No")
    


### FIXED CODE ###

N = int(input())
l = list()

for n in range(N):
    a = input()
    l.append(a)

l_uniq = list(set(l))

if len(l) == len(l_uniq):
    for i in range(0, N-1):
        if l[i+1][0] != l[i][-1]:
            print("No")
            break
    else:
        print("Yes")
else:
    print("No")
N,Y=map(int,input().split())
flag=False

for i in range(0,N+1):
  if flag==False:
    for j in range(0,N-i+1):
      P=10000*i+5000*j+1000*(N-i-j)
      if Y==P:
        print(i,j,N-i-j)
        flag=True
        break
      
if flag==False::
  print(-1,-1,-1)

### FIXED CODE ###

N,Y=map(int,input().split())
flag=False

for i in range(0,N+1):
  if flag==False:
    for j in range(0,N-i+1):
      P=10000*i+5000*j+1000*(N-i-j)
      if Y==P:
        print(i,j,N-i-j)
        flag=True
        break
      
if flag==False:
  print(-1,-1,-1)
print(min(set(map(chr, range(97, 123))) - set(input())))

### FIXED CODE ###

print(min(set(map(chr, range(97, 123))) - set(input()) or ["None"]))
s = input()
x,y = map(int,input().split(" "))
l = [len(c) for c in s.split("T")]
X = l[::2]
Y = l[1::2]

ansX = set([X[0]])
for i in range(1,len(X)):
    ansX = set([c+X[i] for c in ansX]+[c-X[i] for c in ansX]))

ansY = set([0])
for i in range(0,len(Y)):
    ansY = set([c+Y[i] for c in ansY]+[c-Y[i] for c in ansY]))
    
if x in ansX and y in ansY:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

s = input()
x,y = map(int,input().split(" "))
l = [len(c) for c in s.split("T")]
X = l[::2]
Y = l[1::2]

ansX = [X[0]]
for i in range(1,len(X)):
    if not X[i] == 0:
        ansX = list(set([c+X[i] for c in ansX]+[c-X[i] for c in ansX]))

ansY = [0]
for i in range(0,len(Y)):
    if not Y[i] == 0:
        ansY = list(set([c+Y[i] for c in ansY]+[c-Y[i] for c in ansY]))
    
if x in ansX and y in ansY:
    print("Yes")
else:
    print("No")
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

N = int(input())
ans = 1
for i in range(0,N):
    t = int(input())
    ans = int(t * (ans / gcd(ans, t)))
print(ans)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

N = int(input())
ans = 1

for i in range(0,N):
    t = int(input())
    ans = t * ans // gcd(ans, t)

print(ans)
n = int(input())
an = list(map(int,input().split()))

odd = filter((lambda x:x%2==1),an)
div4 = filter((lambda x:x%4 ==0),an)
div2 = set(an).difference(set(odd)).difference(set(div4))
if len(div2) == 0:
  div4.append(0)
if len(odd) <= len(div4)+1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

_ = int(input())
an = list(map(int,input().split()))

odd = list(filter((lambda x:x%2==1),an))
div4 = list(filter((lambda x:x%4 ==0),an))
div2 = set(an).difference(set(odd)).difference(set(div4))
if len(div2) == 0:
  div4.append(0)
if len(odd) <= len(div4):
  print('Yes')
else:
  print('No')
import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = read().rstrip().decode()

if N is.upper():
	print('A')
else:
	print('a')

### FIXED CODE ###

S = input() # 標準入力がStringの場合
if S.isupper():
  print('A')
else:
  print('a')
import sys
input = sys.stdin.readline

class Unionfind:
    __slots__ = ["nodaes","diff_weight"]

    def __init__(self, n):
        self.nodes = [-1]*n
        self.diff_weight = [0]*n

    def root(self, x):
        if self.nodes[x] < 0:
            return x
        else:
            root_x = self.root(self.nodes[x])
            self.diff_weight[x] += self.diff_weight[self.nodes[x]]
            self.nodes[x] = root_x
            return root_x
    
    def unite(self, x, y, w=0):
        w += self.weight(x); w -= self.weight(y)
        x = self.root(x); y = self.root(y)
        if x == y:
            return
        rank_x = -self.nodes[x]; rank_y = -self.nodes[y]
        if rank_x < rank_y:
            x, y = y, x; w = -w
        if rank_x == rank_y:
            self.nodes[x] -= 1
        self.nodes[y] = x
        self.diff_weight[y] = w

    def weight(self, x):
        self.root(x)
        return self.diff_weight[x]
    
    def diff(self, x, y):
        return self.weight(y) - self.weight(x)
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def rank(self, x):
        return -self.nodes[self.root(x)]
    
N,M = map(int,input().split())
uf = Unionfind(N)
ans = "Yes"
for _ in range(M):
    L, R, D = map(int,input().split())
    L -= 1; R -= 1
    uf.unite(L, R, D)   
    if uf.diff(L, R) != D:
        ans = "No"
        break
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
info = [list(map(int,input().split())) for i in range(M)]
nodes = [i for i in range(N)]
rank = [0]*N
diff_weight = [0]*N

def root(x):
    if nodes[x] == x:
        return x
    root_x = root(nodes[x])
    diff_weight[x] += diff_weight[nodes[x]]
    nodes[x] = root_x
    return nodes[x]

def weight(x):
    root(x)
    return diff_weight[x]

def unite(x,y,w):
    w += weight(x); w -= weight(y)
    x = root(x); y = root(y)
    if x == y:
        return
    if rank[x] >= rank[y]:
        nodes[y] = x
        diff_weight[y] = w
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        nodes[x] = y
        diff_weight[x] = -w

def same(x,y):
    return root(x) == root(y)

def diff(x,y):
    return weight(y) - weight(x)

ans = "Yes"

for L,R,D in info:
    L -= 1; R -= 1
    if same(L,R):
        if diff(L,R) != D:
            ans = "No"
            break
    else:
        unite(L,R,D)

print(ans)
def paths(i,j):

    if a[i][0][j]=='#':

        return 0
    if i==h-1 and j==w-1:
        return 1
    if i<h-1 and j<w-1:
        if dp[i][j]==-1:
          dp[i][j]=paths(i+1,j)+paths(i,j+1)
          return dp[i][j]
        else:
            return paths(i+1,j)+paths(i,j+1)
    elif i==h-1 and j<w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i,j+1)
           return dp[i][j]
        else:
            return dp[i][j]
    elif i<h-1 and j==w-1:
        if dp[i][j]==-1:
           dp[i][j]=paths(i+1,j)
           return dp[i][j]
        else:
            return dp[i][j]


h,w=map(int,input().split())
a=[[]for _ in range(h)]
m=1000000007
for i in range(h):
   a[i].extend(input().split())
dp=[[-1 for _ in range(w)]for _ in range(h)]
print(paths(0,0)%m)

### FIXED CODE ###

import sys
sys.setrecursionlimit(20000)

def paths(i, j):

    if i == h - 1 and j == w - 1:
        return 1
    if a[i][0][j] == '#':
        return 0
    if i < h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j) + paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i == h - 1 and j < w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i, j + 1)
            return dp[i][j]
        else:
            return dp[i][j]
    elif i < h - 1 and j == w - 1:
        if dp[i][j] == -1:
            dp[i][j] = paths(i + 1, j)
            return dp[i][j]
        else:
            return dp[i][j]


h, w = map(int, input().split())
a = [[] for _ in range(h)]
m = 1000000007
for i in range(h):
    a[i].append(input())
dp = [[-1 for _ in range(1000)] for _ in range(1000)]
print(paths(0, 0) % m)