Harryxun/stf_run huggingface dataset:
def c(i, p, f, g, k, vis):
    if vis[i]:
        return
    vis[i] = True
    w = f[i] + p
    k[i] = w
    ch = g[i]
    for x in ch:
        c(x, w, f, g, k, vis)


def main():
    import sys
    n, q, *abpx = map(int, sys.stdin.read().split())

    g = [[] for _ in range(n + 1)]
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = [0 for _ in range(n + 1)]

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    k = [0 for _ in range(n + 1)]
    vis = [False for _ in range(n + 1)]

    c(1, 0, f, g, k, vis)
    ans = ' '.join(map(str, k[1:]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def c(i, p, f, g, k, vis):
    if vis[i]:
        return
    vis[i] = True
    w = f[i] + p
    k[i] = w
    ch = g[i]
    for x in ch:
        c(x, w, f, g, k, vis)


def main():
    import sys
    sys.setrecursionlimit(300000)
    n, q, *abpx = map(int, sys.stdin.read().split())

    g = [[] for _ in range(n + 1)]
    for u, v in zip(*[iter(abpx[:2 * (n - 1)])] * 2):
        g[u].append(v)
        g[v].append(u)

    f = [0 for _ in range(n + 1)]

    for p, x in zip(*[iter(abpx[2 * (n - 1):])] * 2):
        f[p] += x

    k = [0 for _ in range(n + 1)]
    vis = [False for _ in range(n + 1)]

    c(1, 0, f, g, k, vis)
    ans = ' '.join(map(str, k[1:]))
    print(ans)


if __name__ == '__main__':
    main()
for char in input():
  S.append(char)
#route 1
C1=0
for i in range(len(S)):
  if i%2==0:
    if S[i]=='1':
      C1+=1
  else:
    if S[i]=='0':
      C1+=1
      
#route 2
C2=0
for n in range(len(S)):
  if n%2==0:
    if S[n]=='0':
      C2+=1
  else:
    if S[n]=='1':
      C2+=1
      
if C1>=C2:
  print(C1)
else:
  print(C2)

### FIXED CODE ###

S=[]
for char in input():
  S.append(char)
#route 1
C1=0
for i in range(len(S)):
  if i%2==0:
    if S[i]=='1':
      C1+=1
  else:
    if S[i]=='0':
      C1+=1

#route 2
C2=0
for n in range(len(S)):
  if n%2==0:
    if S[n]=='0':
      C2+=1
  else:
    if S[n]=='1':
      C2+=1

if C2>=C1:
  print(C1)
else:
  print(C2)
N, M = map(int, input().split())
EdgeTo = [[] for _ in range(N)]

for _ in range(M):
    x, y = map(int, input().split())
    EdgeTo[x-1].append(y-1)


DP = [-1] * N
def From(i):
    if DP[i] != -1: return DP[i]
    else:
        maxLength = 0
        if not EdgeTo[i]:
            DP[i] = maxLength
        else:
            for node in EdgeTo[i]:
                maxLength = max(maxLength, 1 + From(node))
            DP[i] = maxLength
        return maxLength

Ans = 0
for i in range(N):
    Ans = max(Ans, From(i))
print(Ans)

### FIXED CODE ###

import sys

N, M = map(int, input().split())
EdgeTo = [[] for _ in range(N)]
sys.setrecursionlimit(N+M)

for _ in range(M):
    x, y = map(int, input().split())
    EdgeTo[x-1].append(y-1)


DP = [-1] * N
def From(i):
    if DP[i] != -1: return DP[i]
    else:
        maxLength = 0
        if not EdgeTo[i]:
            DP[i] = maxLength
        else:
            for node in EdgeTo[i]:
                maxLength = max(maxLength, 1 + From(node))
            DP[i] = maxLength
        return maxLength

Ans = 0
for i in range(N):
    Ans = max(Ans, From(i))
print(Ans)
t = int(input())
x = int(input())
ans = t / x
print(ans)

### FIXED CODE ###

x,y = map(int,input().split())
ans = x / y
print(ans)
#!/usr/bin/env pypy3
# -*- coding: UTF-8 -*-
import sys
import re
import math
import itertools
import collections
import bisect
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.1415926535897932
IS=float('inf')
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def niten(a,b): return abs(a-b) if a>=0 and b>=0 else  a+abs(b) if a>=0 else abs(a)+b if b>=0 else abs(abs(a)-abs(b))
def fib(n): return [(seq.append(seq[i-2] + seq[i-1]), seq[i-2])[1] for seq in [[0, 1]] for i in range(2, n)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
def pscl(num,l=[1]):
    for i in range(num):
        l = map(lambda x,y:x+y,[0]+l,l+[0])
    return l

n=int(input())
n,k=map(int,input().split())
l=[int(i) for i in input().split()]
ans=chk=0
print(ans)

### FIXED CODE ###

# -*- coding: UTF-8 -*-
def prime_t(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
p=[]

for i in range(2,1008):
    if prime_t(i):
        p.append(i)
d={i:0 for i in p}
mod=10**9+7
n=int(input())
tmp=1
ans=1
R=[i for i in range(168)]
for i in range(1,n+1):
    tmp*=i
    for j in R:
        while tmp%p[j]==0:
            d[p[j]]+=1
            tmp//=p[j]
        if tmp<p[j]:
            break
for i in d:
    ans*=(d[i]+1)
    ans%=mod
print(ans)
import sys
n,k=map(int,input().split())
ab=[[0,0]for i in range(n)]
for i in range(n):
  ab[i][0],ab[i][1]=map(int,input.split())
ab.sort()
x=0
for i in range(n):
  x+=ab[i][1]
  if(x>=k):
    print(ab[i][0])
    sys.exit()
print(ab[-1][0])

### FIXED CODE ###

import sys
n,k=map(int,input().split())
ab=[[0,0]for i in range(n)]
for i in range(n):
  ab[i][0],ab[i][1]=map(int,input().split())
ab.sort()
x=0
for i in range(n):
  x+=ab[i][1]
  if(x>=k):
    print(ab[i][0])
    sys.exit()
print(ab[-1][0])
n=int(input())
s=list(map(int,input().split()))

changed=sorted(s,reverse=True)


    if changed[int(n/2-1)]==changed[int(n/2)]:
        print(0)
    else:
        print(-changed[int(n/2)]+changed[int(n/2-1)])



### FIXED CODE ###

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

changed=sorted(s,reverse=True)


if changed[int(n/2-1)]==changed[int(n/2)]:
        print(0)
else:
        print(-changed[int(n/2)]+changed[int(n/2-1)])
n = int(input())
for i in range(n):
    a.append(input())

# 1 / sum_i(1/a_i)
print(1 / sum([1/i for i in a]))

### FIXED CODE ###

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

print(1 / sum([1/i for i in a]))
nums = []
while True:
    n = raw_input()
    if not n: break
    nums.append(int(n))
nums.sort(reverse=True)
for i in range(3): print nums[i]

### FIXED CODE ###

nums = []
while True:
    try:
        nums.append(int(raw_input()))
    except (EOFError):
        break
nums.sort(reverse=True)
for i in range(3): print nums[i]
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

dp=[3]
col=[1]
for i in range(1,N):
    if A[i]==0:
        col.append(1)
        dp.append(dp[-1]*(4-len(col)))
    else:
        p=0
        for c in range(len(col)):
            if col[c]==A[i]:
                if p==0:
                    col[c]+=1
                p+=1
        dp.append(dp[-1]*p%mod)
        if p==0:
            print(A[N])
print(dp[-1]%mod)


### FIXED CODE ###

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

dp=[1]
col=[]
for i in range(N):
    if A[i]==0:
        col.append(1)
        dp.append(dp[-1]*(4-len(col)))
    else:
        p=0
        for c in range(len(col)):
            if col[c]==A[i]:
                p+=1
                if p==1:
                    col[c]+=1
        dp.append(dp[-1]*p%mod)

print(dp[-1]%mod)
import sys
sys.setrecursionlimit(100**6)


class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	for i in range(n):
		if colors[i] != -1:
			continue
		dfs(i, g, colors)
	for c in colors:
		print(c)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100**4)

class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	for i in range(n):
		if colors[i] != -1:
			continue
		dfs(i, g, colors)
	for c in colors:
		print(c)
resolve()
n=int(input())
s=str(n)
if s[-1] in [2, 4, 5, 7, 9]:
  print("hon")
else if s[-1] == 3:
  print("bon")
else:
  print("pon")

### FIXED CODE ###

S = str(input())[-1]
tmp = ['0', '1', '6', '8']
if S == '3':
    print('bon')
elif S in tmp:
    print('pon')
else:
    print('hon')
l,r=map(int,input().split())
if r-l>=2018:
  print(0)
  exit()
min1=2018
else:
  for i in range(l,r):
    for j in range(i+1,r+1):
      min=min(i*j%2019,min1)
print(min1)
      

### FIXED CODE ###

l,r=map(int,input().split())
min1=2018
if r-l>=2018:
  print(0)
  exit()
else:
  for i in range(l,r):
    for j in range(i+1,r+1):
      min1=min(i*j%2019,min1)
print(min1)
while True:
    m, n = list(map(int, input().split()))
    print(m * (m - 1) / 2 + n * (n - 1) / 2)


### FIXED CODE ###

m, n = list(map(int, input().split()))
print(int(m * (m - 1) / 2 + n * (n - 1) / 2))
import numpy as np
n = int(input())
a = list(map(int,input().split()))
w = np.zeros(9,dtype=int)
count = 0
for i in range(n):
    if a[i] < 3200 and w[a[i]//400]==0:
        count+=1
    w[a[i]//400]+=1
if count == 0:
    print(1,w[8])
elif w[7] == 0:
    print(count,count)
else:
    print(count,count+w[8])

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
w = [0 for i in range(8)]
count = 0
sup = 0
for i in a:
    if i < 3200 and w[i//400]==0:
        count+=1
        w[i//400] += 1
    elif i >= 3200:
        sup += 1
if count == 0:
    print(1,sup)
elif sup == 0:
    print(count,count)
else:
    b= count+sup
    print(count,b)
import sys
input = sys.stdin.readline
import math
def print_ans(A, B):
    """Test Case
    >>> print_ans(2, 3)
    6
    >>> print_ans(123, 456)
    18696
    >>> print_ans(100000, 99999)
    9999900000
    """
    def lcm(a, b):
        g = math.gcd(a, b)
        c = a * b
        return c//g
    print(lcm(A, B))
if __name__ == '__main__':
    A, B = map(int, input().rstrip().split())
    print_ans(A, B)


### FIXED CODE ###

import sys
input = sys.stdin.readline
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def print_ans(A, B):
    """Test Case
    >>> print_ans(2, 3)
    6
    >>> print_ans(123, 456)
    18696
    >>> print_ans(100000, 99999)
    9999900000
    """
    print(A * B // gcd(A, B))
if __name__ == '__main__':
    # test
    A, B = map(int, input().rstrip().split())
    print_ans(A, B)
L, R = map(int, input().split(" "))

ans = 2019
for i in range(L, min(R, (L + 2019 * 1000 )):
    ans = min(ans, (i * (i + 1)) % 2019)


print(ans)

### FIXED CODE ###

L, R = map(int, input().split(" "))

ans = 2019
for i in range(L, min(R, L + 2019 * 10)):
    for j in range(i + 1, min(R+1, L + 2019 * 10)):
        ans = min(ans, (i * j) % 2019)
        if ans == 0:
            break

print(ans)
import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def dfs(G, v):
	seen[v] += 1
	#print('v :', v)
	
	for nv in G[v]:
		if seen[nv]: continue
		#print('v nv :', v, nv, 'Recursion')
		dfs(G, nv)

N, M = MAP()
A = [MAP() for _ in range(M)]

#print(A)

ans = 0
for i in range(M):
	G = [[] for _ in range(N)]
	for j, m in enumerate(A):
		# i!=jのとき辺を追加しない
		if i != j:
			a, b = m
			G[a-1].append(b-1)
			G[b-1].append(a-1)
		
	seen = [0] * N
	dfs(G, 1)
	#print(i, j, seen)
	
	if sum(seen) != N: ans += 1

print(ans)import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def dfs(G, v):
	seen[v] += 1
	#print('v :', v)
	
	for nv in G[v]:
		if seen[nv]: continue
		#print('v nv :', v, nv, 'Recursion')
		dfs(G, nv)

N, M = MAP()
A = [MAP() for _ in range(M)]

#print(A)

ans = 0
for i in range(M):
	G = [[] for _ in range(N)]
	for j, m in enumerate(A):
		# i!=jのとき辺を追加しない
		if i != j:
			a, b = m
			G[a-1].append(b-1)
			G[b-1].append(a-1)
		
	seen = [0] * N
	dfs(G, 1)
	#print(i, j, seen)
	
	if sum(seen) != N: ans += 1

print(ans)

### FIXED CODE ###

import sys

if sys.platform =='ios':
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def dfs(G, v):
	seen[v] += 1
	#print('v :', v)
	
	for nv in G[v]:
		if seen[nv]: continue
		#print('v nv :', v, nv, 'Recursion')
		dfs(G, nv)

N, M = MAP()
A = [MAP() for _ in range(M)]

#print(A)

ans = 0
for i in range(M):
	G = [[] for _ in range(N)]
	for j, m in enumerate(A):
		# i!=jのとき辺を追加しない
		if i != j:
			a, b = m
			G[a-1].append(b-1)
			G[b-1].append(a-1)
		
	seen = [0] * N
	dfs(G, 1)
	#print(i, j, seen)
	
	if sum(seen) != N: ans += 1

print(ans)
import fractions
n,m = map(int,input().split())
l = input().split()
for i in range(len(l)):
    lcm = (int(l[i]) * int(l[i + 1])) // fractions.gcd(int(l[i]), int(l[i + 1]))
x = m // (int(lcm)/2)
y = m // lcm
print(int(x-y))

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def div_ceil(x, y): return (x + y - 1) // y
 
N, M = map(int, input().split())
*A, = map(int, input().split())
A = list(set([a // 2 for a in A]))
L = A[0]
for a in A[1:]:
    L *= a // gcd(L, a)
for a in A:
    if (L // a) % 2 == 0:
        ans = 0
        break
else:
    ans = div_ceil(M // L, 2)
print(ans)
K,S = map(int,input().split())
print(sum(range(S+1))


### FIXED CODE ###

K, S = map(int, input().split())
answer = 0
for x in range(K+1):
    for y in range(K+1):
        if 0 <= S - x - y <= K:
            answer += 1
print(answer)
# import heapq
# import collection
# import bisect
import numpy


def binary_search(arry, target):
    result = None
    left = 0
    right = len(arry) - 1

    while left <= right:
        mid = (left + right) // 2
        if arry[mid] == target:
            result = mid
            break
        elif arry[mid] > target:
            right = mid - 1
        else:
            left = mid + 1

    # print(left, right)
    if result is None:
        return left
    else:
        return result


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

A = sorted(A)

# A = [i for i in range(10**5)]
# M = 10**5

while M > 0:
    index = binary_search(A, A[N-1] // 2)
    for i in range(index+1):
        if M <= 0:
            break
        A[N-1-i] = A[N-1-i] // 2
        M -= 1

print(numpy.sum(A))


### FIXED CODE ###

import heapq
# import collection
# import bisect
# import numpy

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

# N = 10**5
# A = [10 for i in range(10**5)]
# M = 10**5

# A = sorted(A)
A = []
for i in input().split():
    heapq.heappush(A, -int(i))

while M > 0:
    heapq.heappush(A, -((-heapq.heappop(A))//2))
    M -= 1

print(-sum(A))
def main():
n,m=map(int,input().split())
  def hashh(x1,y1,x2,y2):
      if x1>x2:
          x1,y1,x2,y2=x2,y2,x1,y1
      if x1==x2 and y1>y2:
          x1,y1,x2,y2=x2,y2,x1,y1
      return x1*27000000000+y1*9000000+x2*3000+y2
  abc_l=[list(map(int,input().split()))for _ in range(n)]
  def_l=[list(map(int,input().split()))for _ in range(m)]
  x=[0]
  y=[0]
  for a,b,c in abc_l:
      x.append(a)
      x.append(b)
      y.append(c)
  for d,e,f in def_l:
      x.append(d)
      y.append(e)
      y.append(f)
  x=sorted(list(set(x)))
  y=sorted(list(set(y)))
  h=len(x)+1
  w=len(y)+1
  dicx={}
  dicy={}
  for i in range(len(x)):dicx[x[i]]=i
  for i in range(len(y)):dicy[y[i]]=i
  grid=[[0]*w for _ in range(h)]
  dont=set()
  for a,b,c in abc_l:
      for i in range(dicx[a],dicx[b]):
          dont.add(hashh(i+1,dicy[c],i+1,dicy[c]+1))
  for d,e,f in def_l:
      for j in range(dicy[e],dicy[f]):
          dont.add(hashh(dicx[d],j+1,dicx[d]+1,j+1))
  if dicx[0]==0 or dicx[0]==h-1 or dicy[0]==0 or dicy[0]==w-1:
      exit(print("INF"))
  stack=[(dicx[0],dicy[0])]
  grid[dicx[0]][dicy[0]]=1
  ans=0
  for sx,sy in stack:
      ans+=(x[sx]-x[sx-1])*(y[sy]-y[sy-1])
      for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
          tx=sx+dx
          ty=sy+dy
          if grid[tx][ty]:continue
          if hashh(sx,sy,tx,ty) in dont:continue
          if tx==0 or tx==h-1 or ty==0 or ty==w-1:
              exit(print("INF"))
          grid[tx][ty]=1
          stack.append((tx,ty))
  print(ans)
main()


### FIXED CODE ###

n,m=map(int,input().split())
def hashh(x,y,f):
    return (x*3000+y)*2+f
abc_l=[list(map(int,input().split()))for _ in range(n)]
def_l=[list(map(int,input().split()))for _ in range(m)]
x=[0]
y=[0]
for a,b,c in abc_l:
    x.append(a)
    x.append(b)
    y.append(c)
for d,e,f in def_l:
    x.append(d)
    y.append(e)
    y.append(f)
x=sorted(list(set(x)))
y=sorted(list(set(y)))
h=len(x)+1
w=len(y)+1
dicx={}
dicy={}
for i in range(len(x)):dicx[x[i]]=i
for i in range(len(y)):dicy[y[i]]=i
grid=[[0]*w for _ in range(h)]
dont=set()
for a,b,c in abc_l:
    for i in range(dicx[a],dicx[b]):
        dont.add(hashh(i+1,dicy[c],1))
for d,e,f in def_l:
    for j in range(dicy[e],dicy[f]):
        dont.add(hashh(dicx[d],j+1,0))
if dicx[0]==0 or dicx[0]==h-1 or dicy[0]==0 or dicy[0]==w-1:
    exit(print("INF"))
stack=[(dicx[0],dicy[0])]
grid[dicx[0]][dicy[0]]=1
ans=0
for sx,sy in stack:
    ans+=(x[sx]-x[sx-1])*(y[sy]-y[sy-1])
    for dx,dy in ((-1,0),(1,0),(0,-1),(0,1)):
        tx=sx+dx
        ty=sy+dy
        if grid[tx][ty]:continue
        if hashh(min(sx,tx),min(sy,ty),1 if sx==tx else 0) in dont:continue
        if tx==0 or tx==h-1 or ty==0 or ty==w-1:
            exit(print("INF"))
        grid[tx][ty]=1
        stack.append((tx,ty))
print(ans)
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.sort()
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if a[0]!=1 else 0

a = [i for i in range(2, N+1) if i in a]
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
 
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0
 
a = set(list(range(2,N+1))) - set(a)
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)
import copy
H, W = list(map(int , input().split(' ')))

arr =  []
h_ar = []
for _ in range(W):
    h_ar.append(0)
dp =[]
for _ in range(H):
    dp.append(copy.deepcopy(h_ar))


for _ in range(H):
    w  =  list(map(str , input().split(' ')))
    arr.append(w)
print(arr)


flag= False
for h in range(H-1,-1,-1):
    if arr[h][W-1]=='#':

        dp[h][W-1]=-1
        flag =  True
    if flag:
        dp[h][W-1]=-1
    else:
        dp[h][W-1]=1
    
flag = False
for w in range(W-1,-1,-1):
    if arr[H-1][w]=='#':
        dp[H-1][w]=-1
        flag =  True
    if flag:
        dp[H-1][w]=-1
    else:
        dp[H-1][w]=1



for row in range(H-1,0,-1):
    for col in range(W-1,0,-1):
        if arr[row-1][col-1]=='#':
            dp[row-1][col-1]=-1
        elif dp[row][col-1] ==-1 or dp[row-1][col]==-1:
            dp[row-1][col-1] = max(dp[row][col-1],  dp[row-1][col])
        elif dp[row][col-1] > -1 and dp[row-1][col]>-1:
             dp[row-1][col-1] = dp[row][col-1] +  dp[row-1][col]

print(dp[0][0]%(10**9+7))



            
    


### FIXED CODE ###



H, W = map(int, input().split())
arr = ['']*H
for i in range(H):
    arr[i] = input()
 
#print(arr)
dp = [[0]*W for _ in range(H)]

# arr =[
# ['.','.'],
# ['#','.'],
# ['.','.'],
# ['.','#'],
# ['.','.']
# ]








flag= False
#print(arr)
for h in range(H-1,-1,-1):
    #print(h,W-1)

    if arr[h][W-1]=='#':
        dp[h][W-1]=0
        flag =  True
    if flag:
        dp[h][W-1]=0
    else:
        dp[h][W-1]=1
#print(dp)
    
flag = False
for w in range(W-1,-1,-1):
    #print(h,W-1)
    if arr[H-1][w]=='#':
        dp[H-1][w]=0
        flag =  True
    if flag:
        dp[H-1][w]=0
    else:
        dp[H-1][w]=1


#print(dp)

MOD = 10**9+7

dp[H-1][W-1]=0

for row in range(H-1,0,-1):
    for col in range(W-1,0,-1):
        if arr[row-1][col-1]=='#':
            dp[row-1][col-1]=0
        elif dp[row][col-1] ==0 or dp[row-1][col]==0:
            dp[row-1][col-1] = max(dp[row][col-1],  dp[row-1][col])
            dp[row-1][col-1]%=MOD

        elif dp[row][col-1] > 0 and dp[row-1][col]>0:
            dp[row-1][col-1] = dp[row][col-1] +  dp[row-1][col]
            dp[row-1][col-1]%=MOD
        elif  dp[row][col-1] == 0 and dp[row-1][col] == 0:
            dp[row-1][col-1]==0


print(dp[0][0])
n = int(input())

t=[]
for i in range(n):
    t=list(map(int, input().split(" ")))
    t.append(t)

def dis(t1, t2):
    x1, y1 = t1
    x2, y2 = t2
    return ((x1- x2)**2 + (y1-y2)**2)**0.5

total_dis = 0

for i in range(0, len(t)):
    t1=t[i]
    for j in range(0, len(t)):
        t2 = t[j]
        total_dis += dis(t1, t2)

ans = (1/n)*total_dis
print(ans)

### FIXED CODE ###

n=int(input())
xy=[]
for _ in range(n):
    x,y=map(int,input().split())
    xy.append([x,y])
ans=0
for i in range(n):
    for j in range(n):
        ans +=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5
print(ans/n)
d=list(map(int,input().split()))
c=list(input())

class dice(object):
	def __init__(self, d):
		self.d = d

	def roll(self,com):
		a1,a2,a3,a4,a5,a6=self.d
		if com=="E":
			self.d = [a4,a2,a1,a6,a5,a3]
		elif com=="W":
			self.d = [a3,a2,a6,a1,a5,a4]
		elif com=="S":
			self.d = [a5,a1,a3,a4,a6,a2]
		elif com=="N":
			self.d = [a2,a6,a3,a4,a1,a5]

dice1=dice(d)	
for com in c:
	roll(com)
print(dice1.d[0])

### FIXED CODE ###

d=list(map(int,input().split()))
c=list(input())

class dice(object):
	def __init__(self, d):
		self.d = d

	def roll(self,com):
		a1,a2,a3,a4,a5,a6=self.d
		if com=="E":
			self.d = [a4,a2,a1,a6,a5,a3]
		elif com=="W":
			self.d = [a3,a2,a6,a1,a5,a4]
		elif com=="S":
			self.d = [a5,a1,a3,a4,a6,a2]
		elif com=="N":
			self.d = [a2,a6,a3,a4,a1,a5]

dice1=dice(d)	
for com in c:
	dice1.roll(com)
print(dice1.d[0])
n,p= map(int,input().split())
res=1
if n==1:
    res=p
else:
    for i in range(2,int(p**(1/n))+2):
        x=i**n
        if x>p:
            break
        if p%x==0:
            res=i
print(res)

### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
a,b = map(input().split(' '))
print(maximum(a-2*b,0))

### FIXED CODE ###

a,b = map(int,input().split(' '))
print(max(a-2*b,0))
H = int(input())

def f(hp):
    if hp == 1:
        return 1
    return f(hp/2)*2+1

print(f(H))

### FIXED CODE ###

def f(hp):
    if hp == 1:
        return 1
    return 2 * f(int(hp/2)) + 1

H = int(input())
print(f(H))
def diff4(x,y,z):
    temp1 = x
    temp2 = z
    z = temp2 - (diff//4)
    if z < 0:
        choge #RE CHECK
        sys.exit(0)
    x = temp1 + ((diff//4)*10)
    print('%d %d %d' % (x,y,z))
def diff9(x,y,z):
    temp1 = x
    temp2 = z
    z = temp2 - (diff//9)
    if z < 0:
        choge #RE CHECK
        sys.exit(0)
    x = temp1 + ((diff//9)*10)
    print('%d %d %d' % (x,y,z))
def diff1(x,y,z):
    temp1 = z
    temp2 = y
    z = temp1 - 1
    y = temp2 + 2

#C - Otoshidama
import sys
N,Y = map(int,input().split())
#10000yen,5000yen,1000yen
#N mai Y yen
if 10000 * N < Y:
    print('-1 -1 -1')
    sys.exit(0)
z = Y//10000
y = (Y-z*10000) // 5000
x = (Y-z*10000-y*5000) // 1000
#x = 4,y = 0,z = 123
diff = abs(N-(x+y+z))
if diff % 9 == 0:
    diff9(x,y,z)
    sys.exit(0)
elif diff % 4 == 0:
    diff4(x,y,z)
    sys.exit(0)
else:
    while diff % 4 == 0:
        diff1(x,y,z)
        diff = abs(N-(x+y+z))
    diff4(x,y,z)
    sys.exit(0)

### FIXED CODE ###

import sys
N,Y = map(int,input().split())
for x in range(0,N+1):
    for y in range(0,N+1-x):
        if 10000*x+5000*y + (N-x-y)* 1000 == Y:
            print('%d %d %d' % (x,y,N-x-y))
            sys.exit(0)
print('-1 -1 -1')