Harryxun/stf_run huggingface dataset:
a = int(input())
b = input()

@lru_cache(maxsize=None)
def func(c):
    c = [int(z) for z in c]
    x = int(sum(c))
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(c):
        nsum += n * i
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])




for i in range(a):
    ran = list(b)
    ran[i] = "0" if ran[i] == "1" else "1"
    c = "".join(ran)
    print(func(c))

### FIXED CODE ###

from functools import lru_cache


a = int(input())
b = input()
X = b.count("1")
ans1 = []
ans2 = []

@lru_cache(maxsize=None)
def func1(c):
    x = X + 1
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans1.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum
    
@lru_cache(maxsize=None)
def func2(c):
    x = X - 1
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        ans2.append(n)
        nsum += n * int(c[i])
        n = n % x if n > x else n
        n *= 2
    return nsum    

def func(c):
    x = c.count("1")
    if x == 0:
        return 0
    n = 1
    nsum = 0
    for i in reversed(range(len(c))):
        nsum += n * int(c[i])
        n = n % x if n > x else n
        if n == 0:
            break
        n *= 2
    nsum %= x
    cans = bin(nsum).count("1")
    if cans == 0:
        return 1
    else:
        return 1 + func(bin(nsum)[2:])
    
allans1 = func1(b)
allans2 = func2(b)
ans1 = ans1[::-1]
if allans2 == 0:
    ans2 = [0] * a
else:
    ans2 = ans2[::-1]

c = list(b)
for i in range(a):
    if c[i] == "0":
        ans = (allans1 + ans1[i]) % (X + 1)
        ans = func(bin(ans)[2:]) + 1
        print(str(ans))
    else:
        if allans2 - ans2[i] == 0 and X - 1 == 0:
            print("0")
        else:
            ans = (allans2 - ans2[i]) % (X - 1)
            ans = func(bin(ans)[2:]) + 1
            print(str(ans))
n, m = map(int,input().split())
a = [[0,0] for i in range(n)]
ac = 0
wa = 0

for i in range(m):
    p, s = input().split()
    p = int(p-1)
    if s == "WA" and a[p][1] == 0:
        a[p][0] += 1
    elif s == "AC" and a[p][1] == 0:
        ac += 1
        a[p][1] = 1

for i in a:
    if i[1] == 1:
        wa += i[0]

print(ac,wa)


### FIXED CODE ###

n, m = map(int,input().split())
a = [[0,0] for i in range(n)]
ac = 0
wa = 0

for i in range(m):
    p, s = input().split()
    p = int(p)-1
    if s == "WA" and a[p][1] == 0:
        a[p][0] += 1
    elif s == "AC" and a[p][1] == 0:
        ac += 1
        a[p][1] = 1

for i in a:
    if i[1] == 1:
        wa += i[0]

print(ac,wa)
import math
import queue

def readInt():
	return int(input())

def readInts():
	return list(map(int, input().split()))

def readChars():
	return input().split()


q = queue.Queue()

for i in range(1,9):
	q.put(i)

n = readInt()

for i in range(1,100000):
	a = str(q.get())
	if a[-1]!=0:
		q.put(int(a + str( int(a[-1])-1)))
	q.put(int(a+str(str(int(a[-1])))))
	if a[-1]!=9:
		q.put(int(a+str(int(a[-1])+1)))	
	if i==n:
		print(q.get())
		break

### FIXED CODE ###

def jud(n1,n2):
	if abs(n1-int(str(n2)[0]))<=1:
		return 1
	else:
		return 0

rnrn = [[1,2,3,4,5,6,7,8,9],[10,11,12,21,22,23,32,33,34,43,44,45,54,55,56,65,66,67,76,77,78,87,88,89,98,99]]

for div in range(1,10):
	rnrn.append([])
	for i in range(len(rnrn[div])):
		y = str(rnrn[div][i])
		x = int(y[-1])
		if x-1!=-1:
			rnrn[div+1].append(int(y+str(x-1)))
		rnrn[div+1].append(int(y+str(x)))
		if x+1!=10:
			rnrn[div+1].append(int(y+str(x+1)))
		
rnrn2 = []
for i in range(len(rnrn)):
	rnrn2.extend(rnrn[i])

print(rnrn2[int(input())-1])
N,X=map(int,input().split())
L=list(map(int,input().split()))

D=[0]*(N-1)

D[0]=0
count=1
for i in range(1,N):
  D[i]=D[i-1]+L[i-1]
  if D[i]<=X:
    count+=1
  else:
    break
print(count)

### FIXED CODE ###

N,X=map(int,input().split())
L=list(map(int,input().split()))

D=[0]*(N+1)

D[0]=0
count=1
for i in range(1,N+1):
  D[i]=D[i-1]+L[i-1]
  if D[i]<=X:
    count+=1
  else:
    break
print(count)
-*- coding: utf-8 -*-
# 整数の入力
N = int(input())
K = int(input())
X = int(input())
Y = int(input())

if(N <= K):
  sum = N*X
else:
  sum = K*X + (N-K)*Y

print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
K = int(input())
X = int(input())
Y = int(input())

if(N <= K):
  sum = N*X
else:
  sum = K*X + (N-K)*Y

print('%d' %(sum))
def quick_sort_with_count(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr
    ref = choice(arr)
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1

    if len(left) <= 1000:
        left = count_sort(left)
    else:
        left = quick_sort_with_count(left)

   if len(right) <= 1000:
        right = count_sort(right)
    else:
        right = quick_sort_with_count(right)

    return left + [ref] * ref_count + right
n=input()
S=[]
for i in input().split():
    S.append(int(i))
S=quick_sort_with_count(S)
word=int(int(n)/2)
s=int(S[word])-int(S[word-1])
s2=int(S[word+1])-int(S[word])
print(s)


### FIXED CODE ###

import numpy as np
n=input()
S=[]
for i in input().split():
    S.append(int(i))
S=np.array(S)
word=int(int(n)/2)
asa=S.argsort()
s=int(S[asa[word]])-int(S[asa[word-1]])
print(s)
import fractions
import sys
input=sys.stdin.readline()
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
n,m=map(int,input().split())
s=input()
t=input()
if s[0]!=t[0]:
    print(-1)
    exit()
k=lcm(n,m)
ans=[""for i in range(k)]
ans[0]=s[0]
for i in range(1,n):
    ans[i*(k//n)]=s[i]
for i in range(1,m):
    if not ans[i*(k//m)]:
        ans[i*(k//m)]=t[i]
    else:
        if ans[i*(k//m)]!=t[i]:
            print(-1)
            exit()
print(k)

### FIXED CODE ###

from math import gcd
N,M = map(int, input().split())
S = input()
T = input()
G = gcd(N,M)
for i in range (G):
  if S[N//G * i] != T[M//G * i]:
    print(-1)
    exit()
print(N//G * M//G * G)
K, S = map(int, input().split())

ANS = 0

for x in range(K + 1):
    for y in rage(K + 1):
        z = S - x - y
        if (0 <= z) and z <= K:
            ANS += 1

print(ANS)

### FIXED CODE ###

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

ANS = 0

for x in range(K + 1):
    for y in range(K + 1):
        z = S - x - y
        if (0 <= z) and z <= K:
            ANS += 1

print(ANS)
N,L = map(int, input().split())
S = list((input() for i in range(N))
S = sorted(S)
print(''.join(S))

### FIXED CODE ###

N,L = map(int, input().split())
S = list(input() for i in range(N))
S = sorted(S)
print(''.join(S))
import collections
N = int(input())
S = list(input())
cnt = 0
cntW = 0
cntE = 0
n = N-1
i = 0

index = 0
for i in range(N):
    if S[i] == 'W' and S[i+1] == 'E':
        cnt += 1
        index = i
if cnt == 1:
    m = min(index,n-index)
    print(m)
    exit()
else:
    while i != n-1:
        if S[n] == 'E':
            cntE += 1
        if S[i] == 'W':
            i += 1
            n -= 1
            cntW += 1
        else:
            i += 1
print(cntW+cntE)
    


### FIXED CODE ###

import collections
N = int(input())
S = list(input())
cnt = 0

ans = [0]*N

for i in range(1,N):
    if S[i] == "E":
        cnt += 1
ans[0] = cnt

for i in range(1,N):
    if S[i-1] == 'E' and S[i] == 'E':
        ans[i] = ans[i-1]-1
    elif S[i-1] == "W" and S[i] == 'W':
        ans[i] = ans[i-1]+1
    else:
        ans[i] = ans[i-1]
     
print(min(ans))
N = input()
H_raw = input()
H = H_raw.split(' ')
count = 0
max = 0
for i in range(N):
  if i == 0:
    continue
  if int(H[i]) < int(H[i - 1]):
    count = count + 1
  else:
    if count > max:
      max = count
    count = 0
else:
  if count > max:
    max = count
    
print(max)

### FIXED CODE ###

N = int(input())
H_raw = input()
H = H_raw.split(' ')
count = 0
max = 0
for i in range(N):
  if i == 0:
    continue
  if int(H[i]) <= int(H[i - 1]):
    count = count + 1
  else:
    if count > max:
      max = count
    count = 0
    
if count > max:
  max = count
  
print(max)
, K = map(int, input().rstrip().split())

print(N - K)


### FIXED CODE ###

N, K = map(int, input().rstrip().split())

if K == 1:
    print(0)
else:
    print(N - K)
n,m = map(int,input().split())
a = []
mod = 10**9+7
if m != 0:
    for i in range(m):
        b = int(input())
        a.append(b)
    d = [0 for i in range(n+1)]
    d[0] = 1
    d[1] = 1
    d[2] = 2
    for i in range(3,n+1):
        d[i] = d[i-1] + d[i-2]
    d.append(0)
    ans = 1
    if a[0] == 1:
        ans = 1
    else:
        ans = ans*d[a[0]-1]%mod
    for i in range(m-1):
        ans = ans*d[a[i+1]-a[i]-2]%mod
    ans = ans*d[n-a[m-1]-1]%mod
else:
    ans = d[n]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = []
mod = 10**9+7
d = [0 for i in range(n+1)]
d[0] = 1
d[1] = 1
if n >1 :
    d[2] = 2
for i in range(3,n+1):
    d[i] = d[i-1] + d[i-2]
if m != 0:
    d.append(0)
    for i in range(m):
        b = int(input())
        a.append(b)
    ans = 1
    if a[0] == 1:
        ans = 1
    else:
        ans = ans*d[a[0]-1]%mod
    for i in range(m-1):
        ans = ans*d[a[i+1]-a[i]-2]%mod
    ans = ans*d[n-a[m-1]-1]%mod
else:
    ans = d[n]%mod
print(ans)
k,t=map(int,input().split())
l=[int(i) for i in input().split()]
x=[int(i) for i in l]
nin=min(x)
nen=t

while 1:
    w=[]
    for i in x:
        if i-nin!=0:
            w.append(i-nin)
    x=[i for i in w]
    nin=min(x)
    if len(x)==1:
        print(x[0]-nin)
        exit()
    elif len(x)==0:
        print(0)
        exit()
    nen=len(x)


### FIXED CODE ###

k,t=map(int,input().split())
l=[int(i) for i in input().split()]
if t==1:
    print(l[0]-1)
    exit()
while 1:
    l.sort(reverse=True)
    if l[1]==0: break
    l[0]-=l[1]
    l[1]=0

print(max(0,l[0]-1))
X,N = map(int,input().split())
if N > 0:
    A = list(map(int,input()))
    for i in range(100):
        x = X - i
        y = X - i
    if x not in A:
        print(x)
        quit()
    if y not in A:
        print(y)
        quit()
else:
    print(N)


### FIXED CODE ###

X,N = map(int,input().split())
if N > 0:
    A = list(map(int,input().split()))
    d = {}
    for i in range(102):
        d[i] = 0
    for a in A:
        d[a] = 1
    for i in range(0,100):
        x = X - i
        y = X + i
        if d[x] == 0:
            print(x)
            quit()
        if d[y] == 0:
            print(y)
            quit()
else:
    print(X)
x = input().split()
fn = 0
sn = 0

for i in range(len(x)):
  if int(x[i]) == 5:
    fn += 1
  elif int(x[i]) == 7:
    sn += 1

if fn = 2:
  if sn = 5:
    print("YES")
  else:
    print("NO")
else:
  print("NO")

### FIXED CODE ###

x = input().split()
fn = 0
sn = 0
 
for i in range(len(x)):
  if int(x[i]) == 5:
    fn += 1
  elif int(x[i]) == 7:
    sn += 1
 
if fn == 2:
  if sn == 1:
    print("YES")
  else:
    print("NO")
else:
  print("NO")
N = int(input())
arr = []
evod0 = []
even = [0]
odds = [0]
g0 = []
for i in range(N):
    tmp = int(input())
    arr.append(tmp)
    if tmp%2:
        evod0.append(1)
        even.append(even[-1]+1)
        odds.append(odds[-1])
    elif tmp>0:
        evod0.append(2)
        even.append(even[-1])
        odds.append(odds[-1]+1)
    else:
        evod0.append(0)
        g0.append(i)
        even.append(even[-1]+1)
        odds.append(odds[-1]+2)
ans = sum(arr)
#0を消す
for i in range(N-1):
    tmp = min(even[i+1]+odds[N] - odds[i+1],odds[i+1] + even[N] - even[i+1])
    ans = min(ans,tmp)
tmp = min(even[N],odds[N])
ans = min(ans,tmp)
#0を消さない
ans0 = 0
#左を全部0にする
ans0 += sum(arr[:g0[0]])
a0min = sum(arr[g0[-1]+1:])
for i in range(g0[-1]+1,N-1):
    tmp = min(even[i+1] - even[g0[-1]+1] + odds[N] - odds[i+1],odds[i+1] - odds[g0[-1]+1] + even[N] - even[i+1])
    a0min = min(a0min,tmp)
tmp = min(even[N]-even[g0[-1]+1],odds[N]-odds[g0[-1]+1])
a0min = min(a0min,tmp)
ans0 += a0min
#右を全部0に
right = sum(arr[g0[-1]:])
rmin = sum(arr[:g0[0]])
for i in range(0,g0[0]):
    tmp = min(even[i+1]+odds[g0[0]] - odds[i+1],odds[i+1] + even[g0[0]] - even[i+1])
    rmin = min(rmin,tmp)
tmp = min(even[g0[0]],odds[g0[0]])
rmin = min(tmp,rmin)
right += rmin
print(min(ans,ans0,right))

    

### FIXED CODE ###

n = int(input())
arr = [int(input()) for _ in range(n)]
def ear(n,t):
    if n:
        if t == 1 or t == 3:
            return n%2
        elif t == 2:
            return (n-1)%2
        else:
            return n
    else:
        if t == 1 or t == 3:
            return 2
        elif t == 2:
            return 1
        else:
            return 0
dp = [[0]*5 for _ in range(n)]
for i in range(n):
    for t in range(5):
        if i == 0:
            dp[i][t] = ear(arr[i],t)
        else:
            if t == 0:
                mind = dp[i-1][t]
                dp[i][t] = ear(arr[i],t) + mind
            else:
                if mind > dp[i-1][t]:
                    mind = dp[i-1][t]
                dp[i][t] = ear(arr[i],t) + mind
            dp[i][t] = ear(arr[i],t) + mind
print(min(dp[n-1]))
a,b = map(input().split())

y = b - a - 1
w_hight = 0

for i in range(1, y):
    w_hight += i

print(w_hight - a)

### FIXED CODE ###

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

y = b - a - 1
w_hight = 0

for i in range(1, y + 1):
    w_hight += i

print(w_hight - a)
a, b, c = map(int, input())
if a<c<b:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a, b, c = map(int, input().split())
if a<c<b or b<c<a:
  print("Yes")
else:
  print("No")
import copy
N = int(input())

A = [0]*N

for r in range(N):
  A[r] = int(input())
Elias_A = copy.copy(A)
A.sort()
Sorted_A = copy.copy(A)
  
for r in range(N):
  if N >= 3:
    if A[r] == Sorted_A[N-1]: print(A[r])
    elif A[r] == Sorted_A[N-2]: print(A[r])
    elif A[r] == sorted_A[N-3]: print(A[r])
    else:
      A.remove(Elias_A[r])
      print(A[N-2])
      A = copy.copy(Sorted_A)
  else:
    A.remove(Elias_A[r])
    print(A[N-2])
    A = copy.copy(Sorted_A)

### FIXED CODE ###

N = int(input())
A = [0]*N

for r in range(N): A[r] = int(input())
A_max = max(A)
A_sec = sorted(A)[-2]

for r in range(N):
  if A[r] == A_max: print(A_sec)
  elif A[r] == A_sec: print(A_max)
  else: print(A_max)
import numpy as np
r = float(input())
print("{0:.8f} {1:.6f}".format(np.pi*r*r , 2*np.pi*r))


### FIXED CODE ###

pi = 3.141592653589793
r = float(input())
print("{0:.6f} {1:.6f}".format(pi*r**2 , 2*pi*r))
n=int(input())
l=list(map(int,input().split())
c=0
for i in range(0,n):
      for j in range(i,n):
       		for k in range(j,n):
       				if l[i]!=l[j] and l[j]!=l[k] and l[k]!=l[i]:
       						if l[i]+l[j]>l[k] and l[k]+l[j]>l[i] and l[i]+l[k]>l[j]:
       										c=c+1
print(c)


### FIXED CODE ###

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

ans=0

for i in range(N):
	for j in range(i, N):
		for k in range(j, N):
			if L_list[i]!= L_list[j] and L_list[j] != L_list[k] and L_list[k] != L_list[i]:
				if L_list[i]+L_list[j]> L_list[k] and L_list[j]+L_list[k]>L_list[i] and L_list[k]+L_list[i]>L_list[j]:
					ans+=1
print(ans)
a,b = map(int,input().split())
if int(a/(0.08)) == int(b/(0.1)):
    cost = int(a/(0.08))
else:
    inter = abs(int(a/(0.08)) - int(b/(0.1)))
    mn = min(int(a/(0.08)) , int(b/(0.1)))
             
    for i in range(inter*2):
        if int(cost*(0.08))==a:
            if int(cost*(0.1))==b:
                break
        mn += 1
        if i ==inter:
            cost = -1
print(cost)

### FIXED CODE ###

a,b = map(int,input().split())
if int(a/(0.08)) == int(b/(0.1)):
    mn = int(a/(0.08))
else:
    inter = abs(int(a/(0.08)) - int(b/(0.1)))
    mn = min(int(a/(0.08)) , int(b/(0.1)))
             
    for i in range(inter*2):
        if int(mn*(0.08))==a:
            if int(mn*(0.1))==b:
                break
        mn += 1
        if i ==inter*2-1:
            mn = -1
print(mn)
import copy
import math
import time
import statistics
import math
import itertools
import bisect
from decimal import *

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    start = time.time()

    n, q = get_int_multi()

    a = []
    a.append([-1,1,0])
    for _ in range(n-1):
        wk = get_int_list()
        wk.append(0)
        a.append(wk)

    b = []
    for _ in range(q):
        p, x = get_int_multi()
        tasu(a, p, x)

    a.sort(key=lambda x: x[1])

    ans = ""
    for itm in a:
        ans = ans + str(itm[2]) + " "

    print(ans[:-1])

def tasu(a, p, x):
    for itm in a:
        if itm[1] == p:
            itm[2] += x
            break
    for itm in a:
        if itm[0] == p:
            tasu(a, itm[1], x)




if __name__ == '__main__':
    main()




### FIXED CODE ###

import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():

    start = time.time()

    n, q = get_int_multi()

    a = [[] for _ in range(n+1)]
    for _ in range(n-1):
        s, e = get_int_multi()
        a[s].append(e)
        a[e].append(s)

    point = [0] * (n+1)
    for _ in range(q):
        p, x = get_int_multi()
        point[p] += x

    def tasu(now, prev):
        for next in a[now]:
            if next == prev:
                continue
            point[next] += point[now]
            tasu(next, now)

    sys.setrecursionlimit(10 ** 6)
    tasu(1, -1)
    point = point[1:] #１つ目は0なので除去（inputは1始まりなので、0は使わない）
    print(*point) # * は引数展開　listの中身を引数にする。例えばprint(*[1,2,3])はprint(1,2,3)になり 1 2 3 が出力される


if __name__ == '__main__':
    main()
n=int(input())
A=list(map(int,input().split()))
from collections import deque
ans=deque([])
d=deque(A)
for i in range(0,n):
    if i%2==0:
        ans.append(d[i])
    if i%2==1:
        ans.insert(0,d[i])
ans=list(ans)
if n%2==1:
    ans=ans[::-1]
print(" ".join(map(str, ans)))

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
from collections import deque
ans=deque([])
d=deque(A)
for i in range(0,n):
    if i%2==0:
        ans.append(d[i])
    if i%2==1:
        ans.appendleft(d[i])
a=list(ans)
if n%2==1:
    c=a[::-1]
else:
    c=a
print(" ".join(map(str, c)))
def read():
    H, W = map(int, input().split(' '))
    Ss = []
    for _ in range(H):
        Ss.append(input())
    return H, W, Ss

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def add(p1, p2):
    return (p1[0] + p2[0], p1[1] + p2[1])

def ans(H, W, Ss):
    if Ss[0][0] == '#':
        print('0,0 #')
        return -1
    ds =[ [-1 for _ in range(W)] for _ in range(H)]
    ds[0][0] = 1
    q = [(0, 0)]
    while q:
        p = q.pop()
        d = ds[p[1]][p[0]]
        for dr in DIRS:
            x, y = add(p, dr)
            if x < 0 or x >= W or y < 0 or y >= H:
                continue # 範囲外へは移動できない
            if Ss[y][x] == '#':
                continue # 行き止まりへは移動できない
            if ds[y][x] >= 0 and ds[y][x] < d + 1: # すでに訪れていて短縮にもなっていない
                continue
            ds[y][x] = d + 1
            q.append((x, y))
    if ds[H-1][W-1] < 0:
        return -1
    # 白マスを数える
    ws = sum([l.count('.') for l in Ss])
    return ws - ds[H-1][W-1]

if __name__ == '__main__':
	H, W, Ss = read()
    print(ans(H, W, Ss))

### FIXED CODE ###

# https://atcoder.jp/contests/abc088/tasks/abc088_d

from collections import deque

def solve(R, C, sy, sx, gy, gx, mz):
  queue = deque()
  checked = set( )
  queue.append((sx, sy, 0))
  while queue:
    x, y, n = queue.popleft()
    if x == gx and y == gy:
      return n
    if x < 1 or x > C or y < 1 or y > R or mz[y-1][x-1] == '#':
      continue
    if (x, y) in checked:
      continue
    checked.add((x, y))
    queue.append((x+1, y, n+1))
    queue.append((x-1, y, n+1))
    queue.append((x, y+1, n+1))
    queue.append((x, y-1, n+1))
  return -1


if __name__ == '__main__':
  R, C = map(int, input().split(' '))
  sy, sx = 1, 1
  gy, gx = R, C
  mz = []
  whites = 0
  for r in range(R):
    tmp = input()
    mz.append(tmp)
    whites += tmp.count('.')
  n = solve(R, C, sy, sx, gy, gx, mz)
  if n < 0:
    print(-1)
  else:
    print(whites - n - 1)
# import sys
# import math
# import itertools
# from collections import deque
# from collections import defaultdict
# import heapq
# import copy
# import bisect
# import numpy as np
# from scipy.special import comb

# def my_input(): return sys.stdin.readline().rstrip()
# sys.setrecursionlimit(100000)
# INF = 1001001001001
# MOD = 1000000007

def main():

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

    keta = [-1] * N

    flag = True
    for _ in range(M):
        s, c = map(int, input().split())
        s = s - 1

        if s == 0 and c == 0:
            flag = False

        if keta[s] == -1:
            keta[s] = c
        else:
            if not keta[s] == c:
                flag = False

    if keta[0] == -1:
        keta[0] = 1

    for i in range(1, M):
        if keta[i] == -1:
            keta[i] = 0

    if flag:
        print(int(''.join(map(str, keta))))
    else:
        print("-1")


if __name__ == '__main__':
    main()


### FIXED CODE ###

# import sys
# import math
# import itertools
# from collections import deque
# from collections import defaultdict
# import heapq
# import copy
# import bisect
# import numpy as np
# from scipy.special import comb

# def my_input(): return sys.stdin.readline().rstrip()
# sys.setrecursionlimit(100000)
# INF = 1001001001001
# MOD = 1000000007

def main():

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

    keta = [-1] * N

    flag = True
    for _ in range(M):
        s, c = map(int, input().split())
        s = s - 1

        if s == 0 and c == 0 and N > 1:
            flag = False

        if keta[s] == -1:
            keta[s] = c
        else:
            if not keta[s] == c:
                flag = False

    if keta[0] == -1:
        if N > 1:
            keta[0] = 1
        elif N == 1:
            keta[0] = 0

    for i in range(1, N):
        if keta[i] == -1:
            keta[i] = 0

    if flag:
        print(int(''.join(map(str, keta))))
    else:
        print("-1")


if __name__ == '__main__':
    main()
mod=10**9+7
N=int(input())
M=1
y=[1 for k in range(N)]
for k in range(2,N+1):
    for j in range(2,k+1):
        if k=1:
            break
        if k%j ==0:
            count=0
            while k%j==0:
                k=k//j
                count+=1
            y[j-1]+=count
ans=1
for k in range(len(y)):
    ans=ans*y[k]%mod
print(ans)

### FIXED CODE ###

mod=10**9+7
N=int(input())
M=1
y=[1 for k in range(N)]
for k in range(2,N+1):
    for j in range(2,k+1):
        if k%j ==0:
            count=0
            while k%j==0:
                k=k//j
                count+=1
            y[j-1]+=count
ans=1
for k in range(len(y)):
    ans=ans*y[k]%mod
print(ans)