Harryxun/stf_run huggingface dataset:
import math

MOD = math.pow(10, 9) + 7


def check(h, w, a, b):
    c, d = h - a, w - b
    start2p = math.factorial(a + b) // (math.factorial(a) // math.factorial(b))
    p2end = math.factorial(c + b) // (math.factorial(c) // math.factorial(d))
    return (start2p * p2end) % MOD


def main():
    h, w, a, b = map(int, input.split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 1000000007


def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装

    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def mod_inverse(a, mod):
    """
    フェルマーの小定理による a^-1 ≡ 1 (mod m)の実装
    aの逆元を計算する

    a^-1 ≡ 1 (mod m)
    a * a^-2 ≡ 1 (mod m)
    a^-2 ≡ a^-1 (mod m)

    :param a: 逆元を計算したい数
    :param mod: 法
    :return: a^-1 ≡ 1 (mod m)
    """

    return mod_pow(a=a, n=mod - 2, mod=mod)


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく

        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            # self.inverses.append(mod_inverse(i, self.mod))
            self.inverses.append(self.mod - self.inverses[self.mod % i] * (
                        self.mod // i) % self.mod)
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する

        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if not 0 < k < n:
            raise ValueError

        denominator = \
            self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


def calc_routes(combination, dx, dy):
    if dx == 0 or dy == 0:
        return 1
    else:
        return combination.mod_combination(dx + dy, dx)


def check(h, w, a, b):
    combination = ModCombination(mod=MOD, n_max=h + w)
    p = (b + 1, h - a)
    all_routes = 0
    while p[0] <= w and p[1] > 0:
        d1 = (p[0] - 1, p[1] - 1)
        d2 = (w - p[0], h - p[1])
        r1 = calc_routes(combination, *d1)
        r2 = calc_routes(combination, *d2)
        routes = r1 * r2 % MOD
        all_routes += routes
        all_routes %= MOD
        p = (p[0] + 1, p[1] - 1)
    return all_routes


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()
import math

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

b = a[0]
for i in range(n - 1):
    b = math.gcd(a[i + 1], b)

print(b)

### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a

    if b == 0:
        return a

    c = a % b
    return gcd(b, c)

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

b = a[0]
for i in range(n - 1):
    b = gcd(a[i + 1], b)

print(b)
#include <stdio.h>
#include <math.h>
int main(void){
    long int n;
    scanf("%ld", &n);

    long int ans = 1;
    long int tmp = pow(10, 9);
    for (long int i = 1; i <= n; i++){
        ans = ans * i;
    }
    printf("%ld\n", ans % (tmp + 7));

    return 0;
}


### FIXED CODE ###

n = int(input())

ans = 1
#34ms
for i in range(1, n + 1):
    ans = (ans * i) % (10 ** 9 + 7)
print(ans)
A,B = input().split(" ")
if A <= 9 and B <= 9:
  print(A*B)
else:
  print(-1)

### FIXED CODE ###

A,B = map(int, input().split(" "))
if A <= 9 and B <= 9:
  print(A*B)
else:
  print(-1)
n, k = map(int, input().split())
aa = list(map(int, input().split()))
import numpy as np
aa = np.array(aa)
mod = 10**9+7

def mul(dd):
    ret = 1
    for d in dd:
        ret = (ret*d)%mod
    return ret

def sol(aa, n, k):
    aap = aa[aa>0]
    aam = aa[aa<0]
    if n == k:
        return mul(aa)
    if len(aam) == n and k%2==1:
        aam.sort()
        aam = aam[::-1]
        return mul(aam[:k])

    aap.sort()
    aap = aap[::-1]
    aam.sort()

    ret=1
    if k%2 >0:
        k = k-1
        ret *= aap[0]
        aap = aap[1:]

    aap2 = [aap[2*i]*aap[2*i+1] for i in range(len(aap)//2)]
    aam2 = [aam[2*i]*aam[2*i+1] for i in range(len(aam)//2)]
    ip=0
    im=0
    for i in range(k//2):
        if ip < len(aap2) and aap2[ip] >= aam2[im]:
            ret = (ret * aap2[ip])%mod
            ip += 1
        else:
            ret = (ret * aam2[im])%mod
            im += 1
    return ret%mod

print(sol(aa, n, k))

### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
aa = list(map(np.int64, input().split()))
aa = np.array(aa)

def mul(dd):
    mod = 10**9+7
    ret = 1
    for d in dd:
        ret = (ret*d)%mod
    return ret

def sol(aa, n, k):
    mod = 10**9+7
    aap = aa[aa>0]
    aam = aa[aa<0]
    if n == k:
        return mul(aa)
    if len(aap) + 2*(len(aam)//2) < k:
        return 0

    # マイナスのみ
    if len(aam) == n:
        aam.sort()
        if k%2==1:
            return mul(aam[-k:])
        else:
            return mul(aam[:k])

    aap = aa[aa>=0]
    aap.sort()
    aap = aap[::-1]
    aam.sort()

    ret=1
    if k%2 >0:
        k = k-1
        ret *= aap[0]
        aap = aap[1:]

    aap2 = [aap[2*i]*aap[2*i+1] for i in range(len(aap)//2)]
    aam2 = [aam[2*i]*aam[2*i+1] for i in range(len(aam)//2)]
    aap2.extend(aam2)
    aap2.sort(reverse=True)
    aap2 = [i%mod for i in aap2]
    return (ret*mul(aap2[:k//2]))%mod
print(sol(aa, n, k))
N = int(input())
S = [list(input()) for _ in range(N)]

ans = 0
cntM = 0
cntA = 0
cntR = 0
cntC = 0
cntH = 0
for i in range(N):
    cntM += (1 if S[i][0] == 'M' else 0)
    cntA += (1 if S[i][0] == 'A' else 0)
    cntR += (1 if S[i][0] == 'R' else 0)
    cntC += (1 if S[i][0] == 'C' else 0)
    cntH += (1 if S[i][0] == 'H' else 0)
cntlst = [cntM, cntA, cntR, cntC, cntH]

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        for k in range(j + 1, N):
            ans += cntlst[i] * cntlst[j] * cntlst[k]
print(ans)

### FIXED CODE ###

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

ans = 0
cntM = 0
cntA = 0
cntR = 0
cntC = 0
cntH = 0
for i in range(N):
    cntM += (1 if S[i][0] == 'M' else 0)
    cntA += (1 if S[i][0] == 'A' else 0)
    cntR += (1 if S[i][0] == 'R' else 0)
    cntC += (1 if S[i][0] == 'C' else 0)
    cntH += (1 if S[i][0] == 'H' else 0)
cntlst = [cntM, cntA, cntR, cntC, cntH]

for i in range(3):
    for j in range(i + 1, 4):
        for k in range(j + 1, 5):
            ans += cntlst[i] * cntlst[j] * cntlst[k]
print(ans)
N = int(input())
lis = list(map(int, input().split()))

dic = {}
for num in lis:
    if num in dic:
        dic[num] = dic[num] + 1
    else:
        dic[num] = 1

answer_memo_dic = {}
for key, val in dic.items():
    ans_1 = int(val * (val -1) / 2)
    ans_2 = int((val - 1) * (val - 2) / 2)
    answer_memo_dic[key] = {"ans_1": ans_1, "ans_2": ans_2}

answer_list = []
answer_dic = {}
def answer():
    for n in lis:
        if n in answer_dic:
            answer_list.append(answer_dic[n])
        else:
            answer = 0
            for key, val in answer_memo_dic.items():
                if n == key:
                    answer += val["ans_2"]
                else:
                    answer += val["ans_1"]
            answer_list.append(answer)
            answer_dic[n] = answer

answer()
for a in answer_list:
    print(a)


### FIXED CODE ###

L = int(input())

hen_nagasa = L / 3
print(hen_nagasa ** 3)
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# 素因数分解、リストで返す
#############################################################


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

max_cnt = max(primes.values())
min_cnt = min(primes.values())
if max_cnt == N:
    print("not coprime")
elif min_cnt >= 2:
    print("setwise coprime")
else:
    print("pairwise coprime")


### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))

# 素因数分解、リストで返す
#############################################################


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a.sort()
    return a
#############################################################


primes = defaultdict(int)

for i in range(N):
    p = prime_factorize(A[i])
    p_set = set(p)
    for pi in p_set:
        primes[pi] += 1

# print(primes)

if len(primes) == 0:
    print("pairwise coprime")
    exit()

max_cnt = max(primes.values())
min_cnt = min(primes.values())

if max_cnt == 1:
    print("pairwise coprime")
elif max_cnt != N:
    print("setwise coprime")
else:
    print("not coprime")
n=int(input())
l=sorted([int(i) for i in input().split()],reverse=True)

#print(l)
co=0
for i in range(n-2):
    c=l[i]
    x=0
    for j in range(i+1,n-1):
        b=l[j]
        for k in range(j+1,n):
            a=l[k]
            if c<(a+b):
                co+=1
            else:
                x=1
                break
        if x==1:
            break

print(co)

### FIXED CODE ###

a, b = map(int ,input().split())
print(0 if a-2*b<0 else a-2*b)
P, Q, R = map(int, input().split())
time = [P+Q, P+R, Q+R]
print(min(time))

### FIXED CODE ###

A, P = map(int, input().split())
print(int((A*3 + P)/2))
N = int(input())
A = [int(i) for i in input().split()]

i=2
b=[1]#a=0
c=[1]
d=[]
while True:
    a = 0
    for j in range(N):
        if A[j] % i != 0:
            a += 1
        if a > 1:
            d.append(i) #black list
            break

    print(i,A,a)

    if a == 0:
        b.append(i) #white list
        for j in range(len(A)):
            A[j] = int(A[j] / i)
        i = 2
    if a == 1:
        c.append(i) #gray list
    if a > 0:
        i += 1
    
    k=0
    while True:
        if k >= len(d):
            break
        if i % d[k] == 0:
            i += 1
            k = -1
        k += 1


    if i > min(A):
        break

bs = 1
for i in range(len(b)):
    bs *= b[i]
print(bs * max(c))

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
arr1 = [0 for _ in range(n)]
arr2 = [0 for _ in range(n)]
arr1[0] = a[0]
arr2[-1] = a[-1]
for i in range(1, n):
    arr1[i] = gcd(arr1[i - 1], a[i])
for i in reversed(range(n - 1)):
    arr2[i] = gcd(arr2[i + 1], a[i])
ans = arr1[-1]
for i in range(n): #delete a[i]
    if 0 < i < n - 1:
        ans = max(ans, gcd(arr1[i - 1], arr2[i + 1]))
    elif i == 0:
        ans = max(ans, arr2[1])
    elif i == n - 1:
        ans = max(ans, arr1[n - 2])
print(ans)
import numpy as np

N,M = map(int,input().split())
vector = np.zeros((N,N), dtype='int8')


### FIXED CODE ###

n,m = map(int,input().split())
visited = [-1 for _ in range(n+1)]
visited[1] = 0
will = []
root = [[] for _ in range(n+1)] 
for i in range(m):
    a,b = map(int,input().split())
    root[a].append(b)
    root[b].append(a)

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])
H,N = map(int,input().split())
magic = list(list(map(int,input().split()))for i in range(N))

DP = [10**9]*(H+1)
DP[0] = 0
for a,b in magic:
    for i in range(a):
        DP[i] = min(DP[i],b)
    for i in range(a,H+1):
        DP[i] = min(DP[i],DP[i-a]+b)
print(DP[-1])
 

### FIXED CODE ###

H,N = map(int,input().split())
magic = list(list(map(int,input().split()))for i in range(N))

DP = [10**9]*(H+1)
DP[0] = 0
for a,b in magic:
    for i in range(min(a,H+1)):
        DP[i] = min(DP[i],b)
    for i in range(a,H+1):
        DP[i] = min(DP[i],DP[i-a]+b)
print(DP[-1])
a=[list(map(int,input().split()))for _ in range(3)]
n=int(input())
b=[int(input())for _ in range(n)]
ans='No'
for i in range(3):
  for j in range(3):
    for k in range(n):
      if a[i][j]==b[k]:
         a[i][j]=[0,0]
      
for i in range(3):
    if a[i][0] + a[i][1] + a[i][2] == 0:
        ans = "Yes"
    if a[0][i] + a[1][i] + a[2][i] == 0:
        ans = "Yes"
if a[0][0] + a[1][1] + a[2][2] == 0:
    ans = "Yes"
if a[0][2] + a[1][1] + a[2][0] == 0:
    ans = "Yes"
print(ans)


### FIXED CODE ###

a=[list(map(int,input().split()))for _ in range(3)]
n=int(input())
b=[int(input())for _ in range(n)]
ans='No'
for i in range(3):
  for j in range(3):
    for k in range(n):
      if a[i][j]==b[k]:
         a[i][j]=0
      
for i in range(3):
    if a[i][0] + a[i][1] + a[i][2] == 0:
        ans = "Yes"
    if a[0][i] + a[1][i] + a[2][i] == 0:
        ans = "Yes"
if a[0][0] + a[1][1] + a[2][2] == 0:
    ans = "Yes"
if a[0][2] + a[1][1] + a[2][0] == 0:
    ans = "Yes"
print(ans)
k,s=map(int,input().split())
ans=0
z=[i for i in range(k+1)]
for x in range(k+1):
    for y in range(k+1):
        a=s-x-y
        a=min(s-x-y,k)
        if z[bisect.bisect_left(z,a)]==a:
            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<=k:
            ans+=1
print(ans)
n,a,b = map(int, input().split())
if n/2 < a: a=n-a
if n/2 < b: b=n-b
total, combination = 0,1

for i in range(1,(n-1)//2+1):
    combination = combination*(n-i+1)/i
    total += combination
    if a == i: a_cnt = combination
    if b == i: b_cnt = combination
        
    total = total%(10**9+7)

if n%2==0:
    print(total*2+combination*(n-i)/(i+1)-a_cnt-b_cnt+1)
else:
    print(total*2-a_cnt-b_cnt+1)

### FIXED CODE ###

def pow_self(x,n):
    ans = 1
    while n>0:
        if n&1 == 1:
            ans = (ans*x)%(10**9+7)
            
        x = (x*x)%(10**9+7)
        n >>= 1
    return ans

  
n,a,b = map(int, input().split())        
X,Y = 1,1
for i in range(b):
    X *= n-i
    X %= 10**9+7
    Y *= i+1
    Y %= 10**9+7

    if a-1 == i:
        Xa,Ya = X,Y

comb_a = (Xa*pow_self(Ya,10**9+5))%(10**9+7)
comb_b = (X*pow_self(Y,10**9+5))%(10**9+7)

result = pow_self(2,n)-1-comb_a-comb_b
while result <0:
    result += 10**9+7
print(result)
import collections


def solve():

    S = list(input())
    K = int(input())

    passed = 5000000000000000

    if K < passed:
        if S[0] != "1":
            print(S[0])
        else:
            print(S[1])
        exit()

    for s in S:
        if K < int(s) * passed:
            print(s)
            break
        K = K - (int(s) * passed)


if __name__ == "__main__":
    solve()


### FIXED CODE ###



import collections


def solve():

    S = list(input())
    K = int(input())

    for i in range(K):
        if S[i] != "1":
            print(S[i])
            break
    else:
        print(1)


if __name__ == "__main__":
    solve()
import sys

Num = int(sys.stdin.readline().rstrip())
#Num_str = str(Num)
list_stu_Num = list(sys.stdin.readline().rstrip().split())
list_stu_Num_int = [int(s) for s in list_stu_Num]
list_attend_stu = None
for i in range(1, Num + 1):
    for l in range(0, Num):
        if list_stu_Num_int[l] == i:
            if not list_attend_stu:
                list_attend_stu = list(str(l + 1))
            else:
                list_attend_stu.append(l + 1)
print(*list_attend_stu)


### FIXED CODE ###

import sys

a = sys.stdin.readline().rstrip()
a_int = int(a)

if a_int%2==0:
    print("0.5")
elif a_int == 1:
    print("1.0000000000")
else:
    b = ((a_int - 1)/2 + 1) / a_int
    print('{:.10f}'.format(b))
n,m=map(int,input().split())
a=[(0,0) for _ in range(n+1)]
x=[]
for i in range(m):
    x.append(list(input().split()))
    x[i][0]=int(x[i][0])
for i in range(m):
    if x[i][1]=="AC":
        a[x[i][0]][1]=1
    else:
        if a[x[i][0]][1]==1:
            continue
        else:
            a[x[i][0]][0]+=1
c=0
d=0
for i in range(n+1):
    c+=a[i][1]
    if a[i][1]:
        d+=a[i][0]
print(c,d)

### FIXED CODE ###

n,m=map(int,input().split())
a=[[0,0] for _ in range(n+1)]
x=[]
for i in range(m):
    x.append(list(input().split()))
    x[i][0]=int(x[i][0])
for i in range(m):
    if x[i][1]=="AC":
        a[x[i][0]][1]=1
    else:
        if a[x[i][0]][1]==1:
            continue
        else:
            a[x[i][0]][0]+=1
c=0
d=0
for i in range(n+1):
    c+=a[i][1]
    if a[i][1]:
        d+=a[i][0]
print(c,d)
#coding:utf-8

n = list(input())

if s[0] == s[1] and s[1] == s[2]:
  print('Yes')
elif s[1] == s[2] and s[2] == s[3]:
  print('Yes')
elif s[0] == s[1] and s[1] == s[2] and s[2] == s[3]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

#coding:utf-8

n = list(input())

if n[0] == n[1] and n[1] == n[2]:
  print('Yes')
elif n[1] == n[2] and n[2] == n[3]:
  print('Yes')
elif n[0] == n[1] and n[1] == n[2] and n[2] == n[3]:
  print('Yes')
else:
  print('No')
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if k < a[0] and k < b[0]:
    print(0)
    exit()

if k < a[0] and k >= b[0]:
    for i in range(len(b)):
        k -= b[i]
        if k < 0:
            print(i)
            exit()
        if i == len(b)-1:
            print(m)
            exit()

if k >= a[0] and k < b[0]:
    for i in range(len(a)):
        k -= a[i]
        if k < 0:
            print(i)
            exit()
        if i == len(a)-1:
            print(n)
            exit()

i = 0
j = 0
c = []

while True:
    if a[i] <= b[j]:
        c.append(a[i])
        i += 1
        if i == n -1:
            if j == m -1:
                break
            else:
                for l in range(j, m):
                    c.append(b[l])
                break
    else:
        c.append(b[j])
        j += 1
        if j == m -1:
            if i == n -1:
                break
            else:
                for l in range(i, m):
                    c.append(a[l])
                break

for i in range(len(c)):
    k -= c[i]
    if k < 0:
        print(i)
        exit()
    if i == len(c)-1:
        print(n+m)
        exit()

### FIXED CODE ###

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

best = 0

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for j in range(M):
    b.append(b[j] + B[j])

ans , j = 0, M

for i in range(N +1):
    if a[i] > K:
        break
    while b[j] > K -a[i]:
        j -= 1
    ans = max(ans, i +j)
print(ans)
N,K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
for a in A:
  if(a >= K):ans+=1
print(ans)

### FIXED CODE ###


def myAnswer(N:int,A:list) -> int:
   dic ={}
   for i in range(1,N+1):
      dic[i]=A[i - 1]
   ans = sorted(dic.items(), key=lambda x:x[1])
   for a in ans:
      print(a[0],end=" ")
   print()
def modelAnswer():
   tmp=1
def main():
   N = int(input())
   A = list(map(int,input().split()))

   myAnswer(N,A[:])

if __name__ == '__main__':
   main()
N = int(input())
num = list(map(str, input().split()))
num.sort(reverse=True)
print(sum(num[0::2])-sum(num[1::2]))


### FIXED CODE ###

N = int(input())
num = list(map(int, input().split()))
num.sort(reverse=True)
print(sum(num[0::2])-sum(num[1::2]))
N = int(input())
A = map(int, input().split())

S = sum(A)
Y = [0]*N
Y[0] = S - 2* sum(A[1::2])
for i in range(1,N):
  Y[i] = 2*A[i-1] - Y[i-1] 

print(*Y)

  
  
  


### FIXED CODE ###

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

S = sum(A)
Y = [0]*N
Y[0] = S - 2*sum(A[1::2])
for i in range(1,N):
  Y[i] = 2*A[i-1] - Y[i-1]

print(*Y)
a,b = map(int,raw_input().split())
sum=1
if((a<0 and b>0) or a==0 or b==0):
    print("Zero")
elif(a>0):
    print("Positive")
else:
    for i in range(a,b+1):
        sum*=i
    if(sum>0):
        print("Positive")
    else:
        print("Negative")


### FIXED CODE ###

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

if((a<0 and b>0) or a==0 or b==0):
    print("Zero")
elif(a>0):
    print("Positive")
else:
    if((((a-b)*-1)+1)%2==1):
        print("Negative")
    else:
        print("Positive")
r,g,b=map(int,input().split())
if ((g+b)%4) == 0 :print('YES')
  else:print('NO')

### FIXED CODE ###

r,g,b=input().split()
gb=g+b #str
if int(gb)%4 ==0:print('YES')
else:print('NO')
H,W = input().split()
H,W=int(H),int(W)
sw=[[0]*W]*H

for i in range(W):
    sw[i] = input()

count=0
if sw[0][0]=='#':
    sw[0]='.'+sw[0][1:]
    count+=1
if sw[H-1][W-1]=='#':
    sw[H-1]=sw[H-1][:W-1]+'.'
    count+=1

def search(h,v):
    global H,W
    global sw
    if h>=H-1 and v>=W-1:
        return -2,-2
    elif v>=H-1:
        if sw[h+1][W-1]=='.':
            return h+1,v
        else:
            return -1,-1
    elif h>=W-1:
        if sw[H-1][v+1]=='.':
            return h,v+1
        else:
            return -1,-1
    else:
        if sw[h+1][v]=='.':
            return h+1,v
        elif sw[h][v+1]=='.':
            return h,v+1
        else:
            return -1,-1

h=0
v=0
i=0
while(1):
    flag=True
    for j in range(i+1):
        result = search(h+i-j,v+j)
        if result == (-2,-2):
            print(count)
            exit()
        if result!=(-1,-1):
            flag = False
            h,v=result
            break
    if flag:
        count+=1
        i+=1
    else:
        i=1

### FIXED CODE ###

import numpy as np

H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

dp=np.zeros((H,W),dtype='u8')
if P[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

def DP(y,x):
    global dp
    if 0<=x<=W-1 and 0<=y<=H-1:
        return dp[y][x]
    else:
        return 9999999

for l in range(1,H+W):
    for i in range(l+1):
        if i<H and l-i<W:
            if P[i][l-i]=='#':
                a=DP(i-1,l-i)
                b=DP(i,l-i-1)
                if a < 9999999:
                    if P[i-1][l-i]=='.':
                        a+=1
                if b <  9999999:
                    if P[i][l-i-1]=='.':
                        b+=1
                dp[i][l-i]=min(a,b)
            else:
                #print(i,l-i,DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))
print(dp[H-1][W-1])