Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque

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

move = ((1, 0), (-1, 0), (0, 1), (0, -1))
visited = [[-1] * W for _ in range(H)]

ans = 0
que = deque([])
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            visited[i][j] = 0
            for di, dj in move:
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W \
                   and S[ni][nj] != '#' and visited[ni][nj] == -1:
                    que.append((ni, nj, 1))
                    visited[ni][nj] = 1
                    ans = 1

while que:
    i, j, d = que.popleft()
    for di, dj in move:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == -1:
            que.append((ni, nj, d+1))
            visited[ni][nj] = d+1
            ans = d+1

print(ans)


### FIXED CODE ###

import numpy as np
import sys
# 距離K以内にxが居ない
# xからの距離を測る

buf = sys.stdin.buffer
R,C = map(int,buf.readline().split())
black = np.zeros((R+2,C+2),dtype=np.bool)
black[1:-1,1:] = (np.frombuffer(buf.read(R*(C+1)),dtype='S1') == b'#').reshape(R,C+1)

INF = 10 ** 9
dist = np.zeros((R,C),dtype=np.int32)
dist[~black[1:-1,1:-1]] = INF

for n in range(1,R):
  np.minimum(dist[n-1]+1,dist[n],out=dist[n])
for n in range(R-2,-1,-1):
  np.minimum(dist[n+1]+1,dist[n],out=dist[n])

for n in range(1,C):
  np.minimum(dist[:,n-1]+1,dist[:,n],out=dist[:,n])
for n in range(C-2,-1,-1):
  np.minimum(dist[:,n+1]+1,dist[:,n],out=dist[:,n])

answer = dist.max()
print(answer)
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(0,n):
    a=input()
    if a not in s:
        s.append(a)
print(len(s))


### FIXED CODE ###

n=int(input())
s=[]
for i in range(0,n):
  s.append(input())
a=set(s)
print(len(a))
### BUGGY CODE ###

S = input()
MOD = 10**9 + 7
M = 13

dp = [0] * M
dp[0] = 1

for s in S:
    newDp = [0] * M
    if s == '?':
        for s in range(10):
            for i in range(M):
                newDp[(i * 10 + s) % M] += dp[i]
    else:
        s = int(s)
        for i in range(M):
            newDp[(i * 10 + s) % M] = dp[i]
    for i in range(M):
        dp[i] = newDp[i] % MOD

print(dp[5])


### FIXED CODE ###

S = input()
MOD = 10**9 + 7
lenS = len(S)

dp = [[0 for _ in range(13)] for _ in range(lenS + 1)]  # dp[digit][d] = digit桁までの mod=d の数
dp[0][0] = 1

digitMask = 1

for digit in range(1, lenS + 1) :
    if(S[-digit] == '?') :
        for d in range(13) :
            for k in range(10) :
                dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - k * digitMask) % 13]) % MOD
    else :
        a = int(S[-digit])
        for d in range(13) :
            dp[digit][d] = (dp[digit][d] + dp[digit - 1][(d - a * digitMask) % 13]) % MOD
    digitMask *= 10
    digitMask %= 13

ans = (dp[len(S)][5]) % MOD
print(ans)
### BUGGY CODE ###

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [int(i) for i in bin(A[i])[2:]]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=now.count(1)
    ans+= ((pow(2,59-i,mod)* (q*(q-1)))%mod *pow(2,mod-2,mod))%mod
    ans%=mod
ans*=2
ans%=mod


last=0
for i in A:
    last+=i%mod
    last%=mod
last*=(n-1)
last%=mod
print((last-ans)%mod)
    
     


### FIXED CODE ###

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

B=[[] for i in range(n)]
for i in range(n):
    B[i]= [((A[i]>>(59-j))) & 1 for j in range(60)]
    B[i] = [0]*(60-len(B[i]))+B[i]

TB=[[0]*n for i in range(60)]
for i in range(60):
    TB[i] = [B[j][i] for j in range(n)]
        
# import numpy as np
#print(TB)
ans=0
for i in range(60):
    now=TB[i]
    q=sum(now)
    
    ans+= ((pow(2,59-i,mod)* (q*(n-q)))%mod)%mod
    ans%=mod


print((ans)%mod)
### BUGGY CODE ###

N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

B = [0]*N
possible = True
tot = 0
for i in range(N):
    if A[-(i+1)] > N-i-1:
        possible = False
        break
    elif B[-(i+1)] > A[-(i+1)]:
        possible = False
        break
    elif B[-(i+1)] == A[-(i+1)]:
        continue
    else:
        if i == 0:
            B[-(i+1+A[-(i+1)]):] = range(A[-(i+1)]+1)
            tot += A[-(i+1)]
        else:
            B[-(i+1+A[-(i+1)]):-i] = range(A[-(i+1)]+1)
            tot += A[-(i+1)]
if not possible:
    print(-1)
else:
    print(tot)

### FIXED CODE ###

N = int(input())
A = [0]*N
for i in range(N):
    A[i] = int(input())

B = [0]*N
possible = True
tot = 0
if A[0] == 0:
    for i in range(N-1):
        if A[-(i+1)] > N-i-1:
            possible = False
            break
        elif B[-(i+1)] > A[-(i+1)]:
            possible = False
            break
        elif B[-(i+1)] == A[-(i+1)]:
            B[-(i+2)] = A[-(i+1)]-1
            continue
        else:
            B[-(i+2)] = A[-(i+1)]-1
            tot += A[-(i+1)]
    if not possible:
        print(-1)
    else:
        print(tot)
else:
    print(-1)
### BUGGY CODE ###

def main():
    n = int(input())
    A = []
    for _ in range(n):
        a = int(input())
        if a in A:
            A.remove(a)
        else:
            A.append(a)
    print(len(A))
            

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    B = set()
    for _ in range(n):
        b = int(input())
        if b in B:
            B.remove(b)
        else:
            B.add(b)
    print(len(B))
            

if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import Counter,deque
from scipy import special
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = (K * x)
        x = (x * x)
        n //= 2
    return (K * x)
S = input()
l = [int(n) for n in list(S)]
a = [0]
init = 0
i = 0
d = deque(l)
while d:
    temp = d.pop()
    init += temp*pow_k(10,i)
    a.append(init%2019)
    i += 1
b = [special.comb(kv,2,exact=True) for kv in Counter(a).values() if kv > 1]
print(sum(b))

### FIXED CODE ###

from collections import Counter,deque
from scipy import special
S = input()
l = [int(n) for n in S]
a = [0]
t = 0
m = 1
d = deque(l)
mod = 2019
while d:
    temp = d.pop()
    t = (t + (temp * m)) % mod
    m = (m * 10) % mod
    a.append(t%mod)
b = [special.comb(kv,2,exact=True) for kv in Counter(a).values() if kv > 1]
print(sum(b))
### BUGGY CODE ###

s = list(input())
q = int(input())
for _ in range(q):
    try:
        t,f,c = input().split()
        if f == "1":
            s.insert(0,c)
        else:
            s.append(c)
    except ValueError:
        s = s[::-1]
print(''.join(s))

### FIXED CODE ###

from collections import deque
s = deque(list(input()))
q = int(input())
flg = True
for _ in range(q):
    try:
        t,f,c = input().split()
        if flg:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)
    except ValueError:
        if flg:
            flg = False
        else:
            flg = True
if flg:
    print(''.join(s))
else:
    s = list(reversed(s))
    print(''.join(s))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
kl = list(range(1,k+1))
res = 0

for i in kl:
    for j in kl:
        for k in kl:
            res += gcd(i,j,k)

print(res)



### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
kl = list(range(1,k+1))
res = 0

for i in kl:
    for j in kl:
        for k in kl:
            res += gcd(i,j,k)

print(res)
### BUGGY CODE ###

n = int(input())
ans = 0
for a in range(1,n+1):
    y = n//a
    ans+=int((y*(y+1)*a)/2)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1,n+1):
    y = n//a
    ans+=(y*(y+1)*a)//2
print(ans)
### BUGGY CODE ###

from collections import Counter


def split_RL_block(S):
    N = len(S)
    ret = []

    RL = "R"
    c = "R"
    for i in range(1, N):
        now = S[i]
        if RL == "R" and now == "R":
            c += "R"
        elif RL == "R" and now == "L":
            RL = "L"
            c += "L"
        elif RL == "L" and now == "R":
            ret.append(c)
            RL = "R"
            c = "R"
        else:
            c += "L"
    else:
        ret.append(c)
    return ret


def count_children_RL_border(RL):
    N = len(RL)
    ret = [0] * N
    
    cnt_RL = Counter(RL)
    idx_r = cnt_RL["R"] - 1
    idx_l = idx_r + 1

    r = 0
    l = 0
    for i in range(N):
        if abs(i - idx_r) % 2 == 0:
            r += 1
        else:
            l += 1
    ret[idx_r] = r
    ret[idx_l] = l

    return ret


def main():
    S = input()
    N = len(S)
    RL = split_RL_block(S)
    ans = []
    for rl in RL:
        tmp = count_children_RL_border(rl)
        ans += tmp
    
    print(*ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter


def split_RL_block(S):
    N = len(S)
    ret = []

    RL = "R"
    c = "R"
    for i in range(1, N):
        now = S[i]
        if RL == "R" and now == "R":
            c += "R"
        elif RL == "R" and now == "L":
            RL = "L"
            c += "L"
        elif RL == "L" and now == "R":
            ret.append(c)
            RL = "R"
            c = "R"
        else:
            c += "L"
    else:
        ret.append(c)
    return ret


def count_children_RL_border(RL):
    N = len(RL)
    ret = [0] * N
    
    cnt_RL = Counter(RL)
    idx_r = cnt_RL["R"] - 1
    idx_l = idx_r + 1

    r = 0
    l = 0
    for i in range(N):
        if abs(i - idx_r) % 2 == 0:
            r += 1
        else:
            l += 1
    ret[idx_r] = r
    ret[idx_l] = l

    return ret


def main():
    S = input()
    N = len(S)
    RL = split_RL_block(S)
    ans = []
    for rl in RL:
        tmp = count_children_RL_border(rl)
        ans += tmp
    
    print(*ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

for i in range(max(A,B),A*B+1):
    if i%A==0 and i%B==0:
        print(i)
        break
    i+=(min(A,B)-1)


### FIXED CODE ###

A,B=map(int,input().split())
ma,mi=0,0
ma=max(A,B)
mi=min(A,B)

if A%B==0 or B%A==0:
    print(ma)

else :
    for i in range(2,ma+1):
        if (ma*i)%mi==0:
            print(ma*i)
            break
        i+=(mi-1)
### BUGGY CODE ###

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

def floor(m):
    return int(m)

d=0
for x in range(n+1):
    c= floor(a*x/b) - a*floor(x/b)
    if d<=c:
        d=c

print(d)


### FIXED CODE ###

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

def floor(m):
    return int(m)

if n>=b:
    x=b-1
    c= floor(a*x/b) - a*floor(x/b)
else:
    x=n
    c= floor(a*x/b) - a*floor(x/b)

print(c)
### BUGGY CODE ###

input()
S = list(input())
count = 0
for mask in range(1, 2 << len(S)-1):
	temp = []
	for i, v in enumerate(S):
		if 0 != mask & (1 << i):
			temp.append(v)
	if len(temp) == len(set(temp)):
		count += 1
print(count)


### FIXED CODE ###

N = int(input())
S = input()

mod = 10**9+7
R = 1
for w in set(S):
	#print(w, S.count(w))
	R *= S.count(w) + 1
	R %= mod
print(R - 1)
### BUGGY CODE ###

from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


def update(i, x, seg):
    i = len(a) + i - 1
    seg[i] = x
    while i > 0:
        i = math.floor((i-1) / 2)  # 上のノード
        # seg[i] = min(seg[2*i + 1], seg[2*i + 2])
        seg[i] = fractions.gcd(seg[2*i + 1], seg[2*i + 2])
    # 数列の1要素を変更可能＞消去で良い＞1要素を0に置換しても良い
    # 1要素を0にした時のリスト全体の最大公約数を今回は返す
    return seg[0]


n, a = II(), LI()
# 最大公約数を求める。gcd(0, x) = 0なので各要素を0で初期化する
segtree = [0] * (2*n -1)
maxi = 0

# node n, parent floor((n-1)/2), chile 2*n + 1 2*n + 2
for i in range(n):
    update(i, a[i], segtree)

for i in range(n):
    maxi = max(maxi, update(i, 0, segtree))
    # 元に戻す...???
    update(i, a[i], segtree)

print(maxi)


### FIXED CODE ###

from collections import Counter
from functools import reduce
import bisect
import copy
import fractions
import math
# import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


n, a = II(), LI()
left = [0] * (n+1)
right = [0] * (n+1)

for i in range(1, n+1):
    left[i] = fractions.gcd(left[i-1], a[i-1])

for i in range(n-1, -1, -1):
    right[i] = fractions.gcd(right[i+1], a[i]) 

# print(left)
# print(right)

maxi = -INF

for i in range(n):
    maxi = max(maxi, fractions.gcd(left[i],right[i+1]))

print(maxi)
### BUGGY CODE ###

import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        a = bisect.bisect_left(l[j + 1 : n], l[i] + l[j])
        ans += a
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        a = bisect.bisect_left(l, l[i] + l[j]) - j - 1
        ans += a
print(ans)
### BUGGY CODE ###

import numpy as np

N=int(input())
A=np.array(list(map(int,input().split())))
'''
以下、方針
・Aから、各要素の出現回数を取得する。
・出現回数から、組み合わせを計算する。
'''
uni,cou=np.unique(A,return_counts=True)
# print(uni)
# print(cou)
com=[]
for i in range(len(cou)):
    c=(cou[i]*(cou[i]-1))//2
    com.append(c)
# com=np.array(com)
# print(com)
totalcombination=sum(com)

'''
以下方針
・Aから数字を取得
・その数字に対応する組み合わせを減らす。
・その数字の出現回数を1減らした状態の組み合わせの数を足す。
'''
for j in range (N):
    n=A[j] #nはAの数列の数字
    f=np.where(uni==n)[0][0]
    t=com[f]
    e=(cou[f]-1)*(cou[f]-2)//2
    print(totalcombination-t+e)

### FIXED CODE ###

import numpy as np

N=int(input())
A=np.array(list(map(int,input().split())))
'''
以下、方針
・Aから、各要素の出現回数を取得する。
・出現回数から、組み合わせを計算する。
'''
uni,cou=np.unique(A,return_counts=True)

# print(uni)
# print(cou)
dic0={}
dic1={}
dic={} #回答用

com=[]
for i in range(len(cou)):
    c=cou[i]*(cou[i]-1)//2
    dic0[uni[i]]=cou[i]
    dic1[uni[i]]=c
    com.append(c)
    dic.setdefault(uni[i])

# print(com)
totalcombination=sum(com)

# print(com)
# print(dic1)

'''
以下方針
・Aから数字を取得
・その数字に対応する組み合わせを減らす。
・その数字の出現回数を1減らした状態の組み合わせの数を足す。
'''

for j in range (N):
    n=A[j] #nはAの数列の数字
    if dic[n]==None:
        e=(dic0[n]-1)*(dic0[n]-2)//2
        t=totalcombination-dic1[n]+e
        dic[n]=t
        print(t)
    else:
        print(dic[n])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

_n = int(input())
_s = input()[:-1]


def chker(n, s):
    flg = [0] * 1000
    for i in range(1000):
        password = str(i).zfill(3)
        digit = 0
        for num in s:
            if password[digit] == num:
                digit += 1

            if digit == 3:
                flg[i] = 1
                break

    print(sum(flg))


chker(_n, _s)


### FIXED CODE ###

import sys
input = sys.stdin.readline

_n = int(input())
_s = input()[:-1]


def chker(n, s):
    flg = [0] * 1000
    for i in range(1000):
        password = str(i).zfill(3)
        digit = 0
        for num in s:
            if password[digit] == num:
                digit += 1

            if digit == 3:
                flg[i] = 1
                break

    print(sum(flg))


chker(_n, _s)
### BUGGY CODE ###

cnt = 0
base = 0
digits_base = 0
MOD = 2019
s = input().rstrip()

for d in s:
    digits_base += 1
    digits_tmp = digits_base
    base *= 10
    base += int(d)
    tmp = base
#     print(base)
    while tmp:
#         print(tmp)
        if tmp % MOD == 0:
            cnt += 1
        tmp %= 10 ** (digits_tmp-1)
        digits_tmp -= 1
print(cnt)

### FIXED CODE ###

s = input().rstrip()
tmp = 0
pw = 1
from collections import Counter
c = Counter()
c[0] += 1

for d in s[::-1]:
    tmp += int(d) * pw
    tmp %= 2019
    pw *= 10
    pw %= 2019
    c[tmp] += 1

print(sum([v*(v-1)//2 for v in c.values() if v > 1]))
### BUGGY CODE ###

import numpy as np
s = input()
q = int(input())
rbef = str()
aft = str()
sgn = 1
for i in range(q):
    qi = np.array(input().split(),dtype=str)
    if qi[0] == "1":
        sgn *= -1
    else:
        if (qi[1] == "1" or sgn == -1) and (qi[1] == "2" or sgn == 1):
            rbef += qi[2]
        else:
            aft += qi[2]

bef = ''.join(list(reversed(rbef)))
ans = bef+s+aft

if sgn == 1:
    print(ans)
else:
    rans = ''.join(list(reversed(ans)))
    print(rans)


### FIXED CODE ###

import numpy as np
s = input()
q = int(input())
rbef = []
aft = []
sgn = 1
for i in range(q):
    qi = np.array(input().split(),dtype=str)
    if qi[0] == "1":
        sgn *= -1
    else:
        if (qi[1] == "1" or sgn == -1) and (qi[1] == "2" or sgn == 1):
            rbef.append(qi[2])
        else:
            aft.append(qi[2])

bef = "".join(reversed(rbef))
taft = "".join(aft)
ans = bef + s + taft

if sgn == 1:
    print(ans)
else:
    rans = ''.join(list(reversed(ans)))
    print(rans)
### BUGGY CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline

N, K = map(int, readline().split())
p = np.array(list(map(int, readline().split())))
q = np.convolve(p, np.ones(K), mode='valid')

print((np.max(q) + K) / 2)


### FIXED CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def moving_average(a, n=3) :
    ret = np.cumsum(a, dtype=float)
    ret[n:] = ret[n:] - ret[:-n]
    return ret[n - 1:]

def main():
    N, K = map(int, readline().split())
    p = np.array(readline().split(), dtype=np.int32)
    q = moving_average(p, K)

    print((np.max(q) + K) / 2)


main()
### BUGGY CODE ###


"""
xi,xjのペアにおいて、このペアは何通り出てくるか
sum(全通り)sum(i)sum(j){|xi-xj|+|yi-yj|}
和なので、どんな順序でもいい

sum(i)sum(j)sum(全通り){|xi-xj|}
sum(i)sum(j)sum(全通り){|yi-yj|}

あるi,jで固定して、sum(全通り){|xi-xj|}を求めるヤツ
固定したi,jが現れる回数は、

pat = NM-2_C_K-2 こいつはどこでも一緒

pat*sum(i)sum(j){|xi-xj|}を計算する
すべてのi,j(i>j)ペアにおいて、xi,xjの和は
sum(i=1,N){i*(N-i)}
"""
from math import factorial

N,M,K = map(int,input().split())
mod = 10**9+7
fa = 1
num = N*M - 2
# 固定したときの通り数
for i in range(num,1,-1):
    if num-i == K-2:
        break
    fa *= i
pat = fa//factorial(K-2)
# xi-xj
n_x = M**2*((N-1)*N*(N+1))//6
n_y = N**2*((M-1)*M*(M+1))//6
print(pat*(n_x+n_y)%mod)

### FIXED CODE ###


"""
xi,xjのペアにおいて、このペアは何通り出てくるか
sum(全通り)sum(i)sum(j){|xi-xj|+|yi-yj|}
和なので、どんな順序でもいい

sum(i)sum(j)sum(全通り){|xi-xj|}
sum(i)sum(j)sum(全通り){|yi-yj|}

あるi,jで固定して、sum(全通り){|xi-xj|}を求めるヤツ
固定したi,jが現れる回数は、

pat = NM-2_C_K-2 こいつはどこでも一緒

pat*sum(i)sum(j){|xi-xj|}を計算する
すべてのi,j(i>j)ペアにおいて、xi,xjの和は
sum(i=1,N){i*(N-i)}
"""
from math import factorial

N,M,K = map(int,input().split())
mod = 10**9+7
fa = 1
num = N*M - 2
# 固定したときの通り数
# フェルマーの小定理をつかって、mod(M)でのcombinationが高速で求まる
# http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
def mod_combination(n,r,mod):
    if n<0 or r<0 or n<r:
        return 0
    if n==0 or r == 0:
        return 1
    a = factorial(n) % mod
    b = factorial(r) % mod
    c = factorial(n-r) % mod
    return (a*pow(b,mod-2,mod)*pow(c,mod-2,mod)) % mod 

pat = mod_combination(N*M-2,K-2,mod)

n_x = M**2*((N-1)*N*(N+1))//6
n_y = N**2*((M-1)*M*(M+1))//6
print(pat*(n_x+n_y)%mod)
### BUGGY CODE ###

import bisect
n = int(input())
a = [- int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  if a[i] >= max(tmp):
    tmp.append(a[i])
  else:
    index=bisect.bisect_right(tmp,a[i])
    tmp[index] =a[i]
print(len(tmp))

### FIXED CODE ###

import bisect
n = int(input())
a = [- int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  idx=bisect.bisect_right(tmp,a[i])
  if idx==len(tmp):
    tmp.append(a[i])
  else:
    tmp[idx] =a[i]
print(len(tmp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
mod = int(1e9+7)
n=int(input())
L=list(map(int,input().split()))
total = 0
for i in range(n):
    for j in range(i+1,n):
        total+=((L[i]%mod)*(L[j]%mod))
print(total%mod)





### FIXED CODE ###

import sys
input = sys.stdin.readline
mod = int(1e9+7)
n=int(input())
L=list(map(int,input().split()))
total = 0
hb = sum(L)
val = 0
for i in range(n-1):
    val +=L[i]
    total += L[i]*(hb-val)
print(total%mod)
### BUGGY CODE ###

MOD = 10**9+7

def modpow(base, pow, mod):
  res = 1
  while pow > 0:
    if pow & 1:
      res = res * base % mod
    base = base**2 % mod
    pow >>= 1
  return res

def modmul(a, b, mod):
  return a*b % mod

def solve(h,w,a,b):
  fact = [1]
  fact_inv = [1]
  for i in range(1, h+w):
    fact.append(fact[-1]*i % MOD)
    fact_inv.append(modpow(fact[-1], MOD-2, MOD))

  ans = 0
  for col_idx in range(b, w):
    before_checkpoint = modmul(modmul(fact[h-a-1+col_idx], fact_inv[h-a-1], MOD), fact_inv[col_idx], MOD)
    from_checkpoint = modmul(modmul(fact[(a-1) + (w-col_idx-1)], fact_inv[w-col_idx-1], MOD), fact_inv[a-1], MOD)
    ans = (ans + modmul(before_checkpoint, from_checkpoint, MOD)) % MOD

  return ans

if __name__ == "__main__":
  h,w,a,b = map(int, input().split())
  print(solve(h,w,a,b))


### FIXED CODE ###

MOD = 10**9+7

def modpow(base, pow, mod):
  res = 1
  while pow > 0:
    if pow & 1:
      res = res * base % mod
    base = base**2 % mod
    pow >>= 1
  return res

def modmul(a, b, mod):
  return a*b % mod

def solve(h,w,a,b):
  fact = [0]*(h+w+1)
  fact[0] = 1
  fact_inv = [0]*(h+w+1)
  fact_inv[0] = 1
  for i in range(1, h+w):
    fact[i] = fact[i-1]*i % MOD
    fact_inv[i] = modpow(fact[i], MOD-2, MOD)

  ans = 0
  for col_idx in range(b, w):
    before_checkpoint = modmul(modmul(fact[h-a-1+col_idx], fact_inv[h-a-1], MOD), fact_inv[col_idx], MOD)
    from_checkpoint = modmul(modmul(fact[(a-1) + (w-col_idx-1)], fact_inv[w-col_idx-1], MOD), fact_inv[a-1], MOD)
    ans = (ans + modmul(before_checkpoint, from_checkpoint, MOD)) % MOD

  return ans

if __name__ == "__main__":
  h,w,a,b = map(int, input().split())
  print(solve(h,w,a,b))
### BUGGY CODE ###

a,b,x=map(int, input().split())
n=x*((a+x-1)//x)
cnt=0
while n<=b:
  cnt+=1
  n+=x
print(cnt)

### FIXED CODE ###

a,b,x=map(int, input().split())
max=b//x
min=(a+x-1)//x
print(max-min+1)
### BUGGY CODE ###


N , M = [int(n) for n in input().split(' ')]

list_AC = []
count_WA = {}
sum_WA = 0
for i in range(M):
    p , S = input().split(' ')
    
    if (p in list_AC):
        # 既にAC済みの場合は何もしない
        continue 
    else:
        if S == 'AC':
            list_AC.append(p)
            if p in count_WA:
                sum_WA += count_WA[p]
        else:
            if p in count_WA:
                count_WA[p] += 1
            else:
                count_WA[p] = 1

print("{} {}".format(len(list_AC),sum_WA))

### FIXED CODE ###


N , M = [int(n) for n in input().split(' ')]

list_AC = [0] * N
list_WAcount = [0] * N
sumAC = 0
sumWA = 0

for i in range(M):
    sp , S = input().split(' ')
    p = int(sp)
    
    if (list_AC[p-1] != 0):
        # 既にAC済みの場合は何もしない
        continue 
    else:
        # 最初に正解したときにそれまでのWA回数を加算
        if S == 'AC':
            sumAC += 1
            list_AC[p-1] = 1
            sumWA += list_WAcount[p-1]
        else:
            list_WAcount[p-1] += 1

print("{} {}".format(sumAC,sumWA))