Harryxun/stf_run huggingface dataset:
class Combination:

    """
    n_max = 10**6のとき前処理は約950ms(PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


N, M, K = map(int, input().split())
mod = 998244353
comb = Combination(N-1, mod)

ans = 0
for k in range(K+1):
    t1 = M % mod
    t2 = pow(M-1, N-1-k, mod)
    t3 = comb(N-1, k)
    ans = (ans + t1 * t2 * t3) % mod

print(ans)


### FIXED CODE ###

class Combination:

    """
    (使用例)
    comb = Combination(n_max, mod)
    comb(n, r)

    (注意)
    n_max != 0
    """

    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * \
                modinv[self.mod % i] % self.mod
        return modinv


N, M, K = map(int, input().split())
mod = 998244353
comb = Combination(N, mod)

ans = 0
for k in range(K+1):
    t1 = M % mod
    t2 = pow(M-1, N-1-k, mod)
    t3 = comb(N-1, k)
    ans = (ans + t1 * t2 * t3) % mod

print(ans)
import math

A, B = list(input().split())
A = int(A)
B = '{:.2f}'.format(B).replace('.', '')
B = int(B)

# A *= 100
# B = int(B * 100)


AB = A * B / 100
floored = int(math.floor(AB))
print(floored)

# AB = A * B
# AB = str(AB)
# AB = AB[0:-2]
# AB = 0 if AB == '' else AB
# print(AB)


### FIXED CODE ###

import math

A, B = list(input().split())
A = int(A)

# A *= 100
# B = float(B)
# B = math.floor(B * 100)
B = B.replace('.', '').ljust(3, '0')
B = int(B)

# AB = A * B / 100
# floored = int(math.floor(AB))
# print(floored)

AB = A * B
AB = str(AB)
AB = AB[0:-2]
AB = 0 if AB == '' else AB
print(AB)
day = list(int(input()))
ans = list(int(input()))
num = 0
for i in range(0, len(ans)):
    num += ans[i]

target = day[0] - num

if target >= 0:
    print(target)
else:
    print("-1")

### FIXED CODE ###

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

num = 0
for i in range(0, len(a)):
    num += int(a[i])

target = n - num

if target >= 0:
    print(target)
else:
    print("-1")
def actual(n, a, b):
    n_op_least = n // (a + b)

    n_blue_least = a * n_op_least
    adjustment = min(n % (a + b), a)

    return n_blue_least + adjustment

n, a, b = map(int, input().split())
print(actual(n, a, b))


### FIXED CODE ###

s = input()

if 'A' in s and 'B' in s:
  	print('Yes')
else:
  	print('No')
n,m,x=map(int,input().split())
a=list(map(int,input().split()))

keep=0
hidari=1
while keep<x:
  keep=a[hidari]
  hidari+=1

keep=10*100
migi=-1
while keep>x:
  keep=a[migi]
  migi-=1
  
print(min([hidari-1,-migi-2]))

### FIXED CODE ###

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

keep=0
hidari=a[0]
while hidari<x and keep<=m:
  keep+=1
  hidari=a[keep]
  
print(min(keep,m-keep))
n=int(input())
if n==0:
  print('0')
else:
  ls=[]
  while(n!=0):
    ls.append(n%2)
    n=-1*(n-n%2)//2
ls.sort(reverse:True)
print(ls)
    
  
    

### FIXED CODE ###

n=int(input())
if n==0:
  print('0')
else:
  ls=[]
  while(n!=0):
    ls.append(str(n%2))
    n=-1*(n-n%2)//2
  ls.reverse()
  oneLinerString="".join(ls)
  print(oneLinerString)
n = int(input())
a = list(map(int, input().split()))
q = int(input())
m = list(map(int, input().split()))

def main():
    for number in m:
        if solve(0, number):
            print('yes')
        else :
            print('no')

def solve(i, m):
    if m == 0:
        return 1

    if i >= n:
        return 0

    res = solve(i + 1, m) or solve(i + 1, m - a[i])
    return res

if __name__ == '__main__':
    main()



### FIXED CODE ###

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

def main():
    for number in m:
        if solve(0, number):
            print('yes')
        else :
            print('no')

def memolize(f):
    cache = {}

    def helper(x, y):
        if (x, y) not in cache:
            cache[(x, y)] = f(x, y)
        return cache[(x, y)]
    return helper

@memolize
def solve(i, m):
    if m == 0:
        return True

    if i >= n:
        return False

    res = solve(i + 1, m) or solve(i + 1, m - a[i])
    return res

if __name__ == '__main__':
    main()
while True:
    n = int(input())
    if n == 0:
        break
    a = [int(input()) for _ in range(n)]
    d = [a[0]]
    for i in range(n):
        if d[0] == 0:
            d[0] += a[i]
        elif a[i] / d[-1] >= 0:
            d[-1] += a[i]
        else:
            d.append(a[i])
    if d[0] < 0:
        d.pop(0)
    print(d)
    if len(d) <= 2:
        print(max(d))
    else:
        maxd = max(d)
        for i in range(0, len(d), 2):
            for j in range(i + 1, len(d) + 1, 2):
                print("{} {} {}".format(i, j, sum(d[i:j])))
                maxd = max(maxd, sum(d[i:j]))
        print(maxd)



### FIXED CODE ###

from collections import deque
while True:
    n = int(input())
    if n == 0:break
    a = [int(input()) for _ in range(n)]
    b = deque([0] * n)
    j = 0
    for i in range(n):
        if a[i] * b[j] >= 0:b[j] += a[i]
        else:j += 1;b[j] += a[i]
    if b[0] < 0 and len(b) > 1:b.popleft()
    while b[-1] <= 0 and len(b) > 1:b.pop()
    if len(b) == 1 and b[0] <= 0:print(max(a))
    else:
        m = len(b) // 2 + 1
        v = [[0] * m for _ in range(m)]
        v[0][0] = b[0]
        for i in range(1, m):
            v[0][i] = v[0][i - 1] + b[2 * i] + b[2 * i - 1]
        for i in range(1, m):
            for j in range(i, m):
                v[i][j] = v[i - 1][j] - b[2 * i - 2] - b[2 * i - 1]
        print(max([max(i) for i in v]))
n, m = map(int, input().split())
c = [input().split() for i in range(m)]
for i in range(m):
    c[i][0] = int(c[i][0])
AC, WA = 0, 0
aclist = [0 for i in range(n)]
for i in range(n):
    if aclist[c[i][0]] == 0:
        if c[i][1] == 'AC':
            aclist[c[i][0]] += 1
            AC += 1
        else:
            WA += 1
print(AC, WA)

### FIXED CODE ###

n, m = map(int, input().split())
c = [input().split() for i in range(m)]
for i in range(m):
    c[i][0] = int(c[i][0])
AC, WA = 0, 0
acwa = [[0, 0] for i in range(n)]
for i in range(m):
    if acwa[c[i][0] - 1][0] == 0:
        if c[i][1] == 'AC':
            acwa[c[i][0] - 1][0] += 1
            AC += 1
            WA += acwa[c[i][0] - 1][1]
        else:
            acwa[c[i][0] - 1][1] += 1

print(AC, WA)
from collections import deque
n, m = map(int, input().split())
route =[[] for i in range(m+1)]
for i in range(m):
    a, b = map(int, input().split())
    route[a].append(b)
    route[b].append(a)
visited = [0 for i in range(n+1)]
visited[1] = 1
ans = [0 for i in range(n+1)]
D = deque()
D.append(1)
while D:
    visit = D.popleft()
    for i in route[visit]:
        if visited[i] == 0:
            D.append(i)
            visited[i] = 1
            ans[i] = visit
print('Yes')
for i in range(2, n+1):
    print(ans[i])

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
way = [[] for i in range(n + 1)]
ans = [-1 for i in range(n + 1)]
reached = [0 for i in range(n + 1)]
for i in range(m):
    a, b = map(int, input().split())
    way[a].append(b)
    way[b].append(a)
D = deque([1])
while D:
    go = D.popleft()
    for i in way[go]:
        if reached[i] == 0:
            D.append(i)
            reached[i] = 1
            ans[i] = go
print('Yes')
for i in range(2, n + 1):
    print(ans[i])
for i in range(1,10):
for j in range(1,10):
print(i, x, j, =, i*j)


### FIXED CODE ###

print ("1x1=1")
print ("1x2=2")
print ("1x3=3")
print ("1x4=4")
print ("1x5=5")
print ("1x6=6")
print ("1x7=7")
print ("1x8=8")
print ("1x9=9")
print ("2x1=2")
print ("2x2=4")
print ("2x3=6")
print ("2x4=8")
print ("2x5=10")
print ("2x6=12")
print ("2x7=14")
print ("2x8=16")
print ("2x9=18")
print ("3x1=3")
print ("3x2=6")
print ("3x3=9")
print ("3x4=12")
print ("3x5=15")
print ("3x6=18")
print ("3x7=21")
print ("3x8=24")
print ("3x9=27")
print ("4x1=4")
print ("4x2=8")
print ("4x3=12")
print ("4x4=16")
print ("4x5=20")
print ("4x6=24")
print ("4x7=28")
print ("4x8=32")
print ("4x9=36")
print ("5x1=5")
print ("5x2=10")
print ("5x3=15")
print ("5x4=20")
print ("5x5=25")
print ("5x6=30")
print ("5x7=35")
print ("5x8=40")
print ("5x9=45")
print ("6x1=6")
print ("6x2=12")
print ("6x3=18")
print ("6x4=24")
print ("6x5=30")
print ("6x6=36")
print ("6x7=42")
print ("6x8=48")
print ("6x9=54")
print ("7x1=7")
print ("7x2=14")
print ("7x3=21")
print ("7x4=28")
print ("7x5=35")
print ("7x6=42")
print ("7x7=49")
print ("7x8=56")
print ("7x9=63")
print ("8x1=8")
print ("8x2=16")
print ("8x3=24")
print ("8x4=32")
print ("8x5=40")
print ("8x6=48")
print ("8x7=56")
print ("8x8=64")
print ("8x9=72")
print ("9x1=9")
print ("9x2=18")
print ("9x3=27")
print ("9x4=36")
print ("9x5=45")
print ("9x6=54")
print ("9x7=63")
print ("9x8=72")
print ("9x9=81")
n, p = map(int, input().split())
if n==1:
  print(p)
  exit()
if p==1:
  print(1)
  exit()
for i in range(round(p**(1/n)))[0::-1]:
  if p%(i**n)==0:
    print(i)
    exit()


### FIXED CODE ###

n, p = map(int, input().split())
if n==1:
  print(p)
  exit()
elif p==1 or n>=60:
  print(1)
  exit()
for i in range(int(p**(1/n))+1, 0, -1):
  if p%(i**n)==0:
    print(i)
    exit()
a,b,x=map(int,input().split())
def an():
    if x>a*1e+9+b*10:
        print(int(1e+9))
        return
    i=int(1e+9)
    j=i
    max=int(1e+9)
    min=1
    while max-min>1:
        d=len(str(i))
        if a*i+b*d>x:
            max=i
        else:
            min=(i+j)//2
        i=(max+min)/2
    print(min)
an()

### FIXED CODE ###

s = input()
if s=='SUN':
  print(7)
elif s=='MON':
  print(6)
elif s=='TUE':
  print(5)
elif s=='WED':
  print(4)
elif s=='THU':
  print(3)
elif s=='FRI':
  print(2)
elif s=='SAT':
  print(1)
N = int(input())
N_List = list(map(int,input().split()))
maxct = 0
for i in range(N-1):
    if N_List[i] >= N_List[i+1]:
        ct += 1
        if (i == N - 2) & (ct > maxct):
            maxct  = ct
    else:
        if maxct < ct:
            maxct = ct
            ct = 0

print(maxct)


### FIXED CODE ###

N = int(input())
N_List = list(map(int,input().split()))
ans = 0
cans = 0
for i in range(1,N):
    if N_List[i] <= N_List[i-1]:
        cans += 1
    if cans > ans:
        ans = cans
    if N_List[i] > N_List[i-1]:
        cans = 0
    
print(ans)
N,R=map(int,input())
if N>=10:
    print(R)
else:
    print(R+100*(10-N))

### FIXED CODE ###

N,R=map(int,input().split())
if N>=10:
    print(R)
else:
    print(R+100*(10-N))
def resolve():
    n,k = map(int, input().split())
    listA = list(map(int,input().split()))
    listA.sort()
    c = sum(listA[:k])
    print(c)
resolve()

### FIXED CODE ###

def resolve():
    a = input()
    if a.isupper() == True:
        print("A")
    else:
        print("a")
        
resolve()
n, k = map(int,(input().split()))
h = []
for i in range(n):
    h.append(int(input()))
h.sort()
min=h[-1]-h[0]
for i in range(n-k+1):
    if h[i+k-1]-h[i] < min:
        min = h[i+k-1]-h[i]
print(min)

### FIXED CODE ###

s=int(input())
if s==25:
    print("Christmas")
elif s==24:
    print("Christmas Eve")
elif s==23:
    print("Christmas Eve Eve")
elif s==22:
    print("Christmas Eve Eve Eve")
N, M = map(int, input.split())
print('Yes' if N == M else 'No)

### FIXED CODE ###

N, M = map(int, input().split())
print('Yes' if N == M else 'No')
import math

def main():
    s = input()
    k = int(input())
    cnt = 0
    if (len(s) == 1):
        cnt = math.floor(k/2)
    elif (len(s) == 2):
        if (s[0] == s[1]):
            cnt = k
        elif (s[0] != s[1]):
            cnt = 0
    else:
        l = list()
        prev = ''
        for c in s:
            if(c == prev):
                l[-1][1] += 1
            else:
                l.append([c, 1])
                prev = c
        for e in l:
            cnt += math.floor(e[1]/2)
        if (l[0][0] == l[-1][0]):
            p = l.pop()
            l[0][1] += p[1]
            if (p[1] == 6):
                cnt -= 1
        cnt *= k
    print(cnt, end='')


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math

def main():
    s = input()
    k = int(input())
    cnt = 0
    if (len(s) == 0):
        cnt = 0
    elif (len(s) == 1):
        cnt = math.floor(k/2)
    elif (len(s) == 2):
        if (s[0] == s[1]):
            cnt = k
        elif (s[0] != s[1]):
            cnt = 0
    else:
        l = list()
        prev = ''
        for c in s:
            if(c == prev):
                l[-1][1] += 1
            else:
                l.append([c, 1])
                prev = c
        if (len(l) == 1):
            cnt += l[0][-1] * k // 2
        elif (len(l) == 2):
            cnt += l[0][-1] // 2
            cnt += l[1][-1] // 2
            cnt *= k
        else:
            edge1 = l[0]
            edge2 = l[-1]
            mid = l[1:-1]
            for e in mid:
                cnt += e[1] // 2 * k
            if (edge1[0] == edge2[0]):
                cnt += (edge1[1] + edge2[1]) // 2 * (k-1)
            else:
                cnt += (edge1[1]) // 2 * (k-1)
                cnt += (edge2[1]) // 2 * (k-1)
            cnt += edge1[1] // 2
            cnt += edge2[1] // 2

    print(cnt, end='')


if __name__ == '__main__':
    main()
n = int(input())
G = [[] for _ in range(n)]
for i in range(n-1):
  uvw = list(map(int, input().split()))
  u = uvw[0]-1
  v = uvw[1]-1
  w = uvw[2]
  G[u].append([v, w])
  G[v].append([u, w])
  
color = [-1]*n
def dfs(G, v, cur = 0):
  if color[v] == -1:
    
    color[v] = cur
    for next_v, w in G[v]:
     
      if color[next_v]==-1:
        if (w % 2 != 0):
          dfs(G, next_v, 1-cur)
        if (w% 2 == 0):
          dfs(G, next_v, cur)
        continue
      


        

for v in range(n):
  if color[v] != -1:
    continue
  else:
    dfs(G, v)


print(*color, sep='\n')
          
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n = int(input())
G = [[] for _ in range(n)]
for i in range(n-1):
  uvw = list(map(int, input().split()))
  u = uvw[0]-1
  v = uvw[1]-1
  w = uvw[2]
  G[u].append([v, w])
  G[v].append([u, w])
  
color = [-1]*n
def dfs(G, v, cur = 0):
  if color[v] == -1:
    
    color[v] = cur
    for next_v, w in G[v]:
     
      if color[next_v]==-1:
        if (w % 2 != 0):
          dfs(G, next_v, 1-cur)
        if (w% 2 == 0):
          dfs(G, next_v, cur)
        continue
      


        

for v in range(n):
  if color[v] != -1:
    continue
  else:
    dfs(G, v)


print(*color, sep='\n')
H, W = map(int, input().split())
inputs = [input() for _ in range(H)]

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

ans = 'Impossible'
counts = 0
for item in inputs:
    counts += item.count('#')

if counts != (H + W - 1):
    ans = 'Impossible'
else:
    for i in range(H + W - 2):
        if 0 <= x <= W - 1 and inputs[y][x + 1] == '#':
            x = x + 1
        elif 0 <= y <= H - 1 and inputs[y + 1][x] == '#':
            y = y + 1
        else:
            ans = 'Impossible'
            break
    ans = 'Possible' if y == goal_y and x == goal_x else 'Impossible'

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
inputs = [input() for _ in range(H)]

y = 0
x = 0

goal_y = H - 1
goal_x = W - 1

counts = 0
for item in inputs:
    counts += item.count('#')

if counts != (H + W - 1):
    print('Impossible')
else:
    for _ in range(H + W - 2):
        if x + 1 < W and inputs[y][x + 1] == '#':
            x += 1
        elif y + 1 < H and inputs[y + 1][x] == '#':
            y += 1
    print('Possible' if y == goal_y and x == goal_x else 'Impossible')
A = map(int, input().split())
if len(set(A) == 2):
  print("yes")
else:
  print("No")

### FIXED CODE ###

A = map(int,input().split())
if len(set(A) ) == 2:
    print("Yes")
else:
    print("No")
#include<iostream>

using namespace std;


main()
{
    int n;
    cin>>n;
    int l=n/3;
    n-=l;
    int w=n/2;
    int h = n-w;
    cout<<l*w*h;
}



### FIXED CODE ###

#HIManshu
H = int(input())
E = H / 3
print(E ** 3)
import math
a,b,x = map(int,input().split())
if a**2*b>x>= (a**2)*b/2:
  tan=2*((a**2)*b-x)/(a**3)
elif a**2*b>x:
  tan=a*(b**2)/x
print(math.degrees(math.atan(tan)))

### FIXED CODE ###

import math
a,b,x = map(int,input().split())
if a**2*b>x> (a**2)*b/2:
  tan=2*((a**2)*b-x)/(a**3)
elif x<=a*a*b/2:
  tan=a*b*b/(2*x)
elif x==a*a*b:
  tan=0
  

print(math.degrees(math.atan(tan)))
S = input()
S[3] = 8
print(S)

### FIXED CODE ###

S = input()
S = "2018/01/" + S.split("2017/01/")[-1]
print(S)
import numpy as np

MOD = 10**9+7

D,T,E = input().split()
n= int(D)

arr = np.zeros((n+1,n+1),dtype=np.int16)
for i in range(3,n+1):
    arr[0,i] = 1

for i in range(1,n+1):
    sum_ = 0
    for j in range(3*i,n+1):
        sum_ += arr[i-1,j]

### FIXED CODE ###

D,T,S = [int(i) for i in input().split()]
out = 'Yes' if D <= T * S else 'No'
print(out)
import sys

read = sys.stdin.read
readline = sys.stdin.readline

N, *a = map(int, read().split())

memo = [[0] * N for _ in range(N)]
r = N % 2


def f(i, j):
    n = j - i + 1
    if i == j:
        if n % 2 == r:
            s = a[i]
            memo[i][j] = s
            return s
        else:
            s = -a[i]
            memo[i][j] = s
            return s
    if n % 2 == r:
        s = max(f(i, j - 1) + a[j], f(i + 1, j) + a[i])
    else:
        s = min(f(i, j - 1) - a[j], f(i + 1, j) - a[i])
    memo[i][j] = s
    return s


f(0, N - 1)
print(memo[0][N - 1])


### FIXED CODE ###

import sys

read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)


def solve():
    n, *a = map(int, read().split())
    a = tuple(a)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            if L > R:
                dp[i][j] = L
            else:
                dp[i][j] = R
    return dp[0][n - 1]


print(solve())
print(input()[{
  "SAT": 1
  "FRI": 2,
  "THU": 3,
  "WED": 4,
  "TUE": 5,
  "MON": 6,
  "SUN": 7
}])

### FIXED CODE ###

print({
  "SAT": 1,
  "FRI": 2,
  "THU": 3,
  "WED": 4,
  "TUE": 5,
  "MON": 6,
  "SUN": 7
}[input()])
from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])
    
    

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    print(H*W-path_area-black)
                
    
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque

def bfs(board, visited, gh, gw):
    turn = 0
    queue = deque([[0, 0, turn]])
    while queue:
        h, w, turn = queue.popleft()
        if h == gh-1 and w == gw-1:
            return turn
        for i, j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_h, new_w = h+i, w+j
            if new_h >= gh or new_h < 0 or new_w >= gw or new_w < 0:
                continue
            elif board[new_h][new_w] != "#" and visited[new_h][new_w] == "x":
                visited[new_h][new_w] = "o"
                queue.append([new_h, new_w, turn+1])
    return -1

def main():
    H, W = map(int,input().split())
    board = []
    for _ in range(H):
        board.append(list(input()))
    black = 0
    for i in range(H):
        for j in range(W):
            if board[i][j] == "#":
                black += 1
    visited = [["x"]*W for _ in range(H)]
    path_area = bfs(board, visited, H, W) + 1
    if path_area:
        print(H*W-path_area-black)
    else:
        print(-1)
                
    
    
if __name__ == "__main__":
    main()
import math
x,y = map(int,input().split())

dp = [[0]*(x*2+1) for _ in range(x+1)]
dp[2][2] = 0
start = 0
end = 0

for i in range(1,x+1):
    if i%2 == 0:
        start = i//2
        dp[i][start] = 1
    else :
        start = int(math.ceil(i/2+1))
        
    end = i*2
    dp[i][end] = 1
    
    for j in range(start,end+1,3):
        if dp[i][j] == 0:
            dp[i][j] += dp[i-1][j-2] + dp[i-2][j-1]


print(dp[x][y])
            


### FIXED CODE ###

import math
def inv(a,mod=10**9+7):
    return(pow(a,mod-2,mod))

x,y = map(int,input().split())
mod = 10**9+7
reuslt = 0
if (x+y) %3 == 0:

    n = (2*x-y)//3
    m = (2*y-x)//3
    r = min(n,m)
    result = 1
    if n < 0 or m < 0:
        print(0)
        exit()
    for i in range(r):
        result = result*(n+m-i)*inv(i+1,mod)%mod
    
else :
    result = 0

print(result)
n = int(input())
A = list(map(int, input().split()))

ans, anstmp = 0
tmp = 0
head = 0
for n1, i in enumerate(A):
    if tmp^i == tmp+i:
        anstmp += 1
        tmp ^= i
    else:
        ans += anstmp 
        for j in A[head:]:
            tmp - A[0]
            anstmp -= 1
            head += 1
            if tmp^i == tmp+i:
                anstmp += 1
                break
print(ans)


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())

result,right,asum=0,0,0
for left in range(n):
    for r in range(right,n):
        if asum&A[right]:
            break
        asum|=A[right]
        right += 1
    asum -= A[left]
    result += right-left
print(result)
a = input()
b = int(input())
c = 0
for i in range(b):
	d = input().split(" ")
	if d[0] == "1":
		c += 1
	else:
		if c % 2 == 0:
			if d[1] == "1":
				a = d[2] + a
			else:
				a = a + d[2]
		else:
			if d[1] == "2":
				a = d[2] + a
			else:
				a = a + d[2]
if c % 2 == 1:
	a = a[::-1]
print(a)

### FIXED CODE ###

a = input().split(" ")
t8 = int(a[0])
t10 = int(a[1])

for i in range(13, 1001):
	b = int(i * 0.08)
	c = int(i * 0.1)
	if b == t8 and c == t10:
		print(i)
		break
	if i == 1000:
		print(-1)
		break
# coding:utf-8
def recurcive(N,c):
    if N%2==0 and N!=0:
        c+=1
        return recurcive(int(N/2),c)
    else:
        return c
N=int(input())
maxim=-1

for i in range(1,N+1):
    if ans = recurcive(i,0) > maxim:
        maxim=ans
print(2**maxim)


### FIXED CODE ###

# coding:utf-8
def recurcive(N,c):
    if N%2==0 and N!=0:
        c+=1
        return recurcive(int(N/2),c)
    else:
        return c
#print(recurcive(8,0))

N=int(input())
maxim=0

for i in range(1,N+1):
    if recurcive(i,0) > maxim:
        maxim=recurcive(i,0)
print(2**maxim)