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

nums = list(map(int, input().split()))

ok = False
count = min(nums)
while not ok:    
    if  (count % nums[0] == 0) and (count % nums[1] == 0):
        ok = True
        break
    count += 1
print(count)

### FIXED CODE ###

from fractions import gcd

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

print(A * B // gcd(A, B))
### BUGGY CODE ###

from functools import reduce
from math import gcd

K = int(input())

count = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            a = [i, j, k]
            if 1 in a:
                count += 1
                continue
            else:
                count += reduce(gcd, a)
print(count)


### FIXED CODE ###

from math import gcd

K = int(input())

count = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        a = gcd(i, j)
        for k in range(1, K+1):
            count += gcd(a, k)
print(count)
### BUGGY CODE ###

N, K = map(int, input().split())
P = tuple(map(int, input().split()))

max_sum = 0
for i in range(N-K+1):
  max_sum = max(max_sum, sum(P[i:i+K]))
          
res = (max_sum + K)/ 2
print(res)

### FIXED CODE ###

N, K = map(int, input().split())
P = tuple(map(int, input().split()))
P2 = P[K:]

max_sum = 0
sum_ = sum(P[:K])

for p, q in zip(P, P2):
  max_sum = max(max_sum, sum_)
  sum_ += q - p
  
max_sum = max(max_sum, sum_)
          
res = (max_sum + K)/ 2
print(res)
### BUGGY CODE ###

#D
N = int(input())
S = list(str(input()))
count = 0
for i in range(1000):
    si = str(i)
    while len(si) < 3:
        si = "0"+si
        
    flag = 0
    for j in range(N):
        if S[j] == si[flag]:
            flag+=1
            if flag == 3:
                break
            
    if flag == 3:
        count+=1
    
print(count)

### FIXED CODE ###

#D
N = int(input())
S = list(str(input()))
count = 0
for i in range(1000):
    si = str(i)
    while len(si) < 3:
        si = "0"+si
        
    flag = 0
    for s in S:
        if s == si[flag]:
            flag+=1
            if flag == 3:
                break
            
    if flag == 3:
        count+=1
    
print(count)
### BUGGY CODE ###

import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
cs = [[0] * 61 for _ in range(N + 1)]
mod = 10 ** 9 + 7
for i in range(N):
  for j in range(61):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    cs[i + 1][j] = (cs[i][j] + (a[i] & t)) % mod
res = 0
#print(cs[-1])
#print(cs[2])
for i in range(N):
  t = 0
  for j in range(61):
    if a[i] & (1 << j) != 0:
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += (1 << j) * (N - i - 1) - (cs[-1][j] - cs[i + 1][j])
    else:
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += (cs[-1][j] - cs[i + 1][j])
    #if i == 1: print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
mxbit = 0
for i in range(N):
  mxbit = max(mxbit, a[i].bit_length())
cs = [0] * mxbit
for i in range(N):
  for j in range(mxbit):
    t = 1 << j
    #print(a[i], t, a[i] & t)
    x = (a[i] & t) > 0
    cs[j] += x
res = 0
#print(cs[-1])
#print(cs)
for i in range(N):
  t = 0
  for j in range(mxbit):
    x = 1 << j
    if a[i] & x != 0:
      x %= mod
      #if i == 1: print((1 << j) * (N - i - 1), (cs[-1][j] - cs[i + 1][j]))
      t += x * (N - (cs[j]))
    else:
      x %= mod
      #if i == 1: print(a[i] & (1 << j), (cs[-1][j] - cs[i + 1][j]))
      t += x * cs[j]
    #print(t)
    t %= mod
  res += t
  res %= mod
print(res % mod * pow(2, mod - 2, mod) % mod)
### BUGGY CODE ###

k,s = map(int, input().split(" "))
sum = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l == s:
                sum += 1
print(sum)

### FIXED CODE ###

k, s = list(map(lambda x: int(x), input().split()))

count = 0
for x in range(k+1):
    for y in range(k+1):
        if x+y+k >= s and x+y <= s:
            count += 1

print(count)
### BUGGY CODE ###

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

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

a,b,n = LI()
import math

ans = 0
for i in range(n+1):
    ans = max(ans, math.floor(a*i/b)-a*math.floor(i/b))
print(ans)

### FIXED CODE ###

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

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

a,b,n = LI()

m = min(b-1, n)
print(int(a*m/b)-a*int(m/b))
### BUGGY CODE ###

n = int(input())
l = []

for i in range(n):
    line = input().split()
    if line[0] == "insert":
        l.append(line[1])
    elif line[0] == "find":
        if line[1] in l:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

n = int(input())
d = {}

for i in range(n):
    line = input().split()
    if line[0] == "insert":
        d[line[1]] = 1
    elif line[0] == "find":
        if line[1] in d:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

#D-Knapsack 1
def main():
    N,W=map(int,input().split())
    DP=[[0 for j in range(W+1)]for i in range(N+1)]
    for i in range(N):
        w,v=map(int,input().split())
        for j in range(1,W+1):
            if j>=w:
                DP[i+1][j]=max(DP[i][j-w]+v,DP[i][j])
            else:
                DP[i+1][j]=DP[i][j]
    print(DP[N][W])
    
main()

### FIXED CODE ###

N,W=map(int,input().split())
DP=[[0 for j in range(W+1)]for i in range(N+1)]
for i in range(N):
    w,v=map(int,input().split())
    for j in range(1,W+1):
        if j>=w:
            DP[i+1][j]=max(DP[i][j-w]+v,DP[i][j])
        else:
            DP[i+1][j]=DP[i][j]
print(DP[N][W])
### BUGGY CODE ###

import sys
import numpy as np


read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def c(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1

    B = np.cumsum(B)
    return B


def main():
    N, K = map(int, readline().split())
    A = np.array(list(map(int, readline().split())))


    K = min(K, 50)
    for _ in range(K):
        A = c(A)

    print(' '.join(A.astype(str)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import numpy as np
from numba import njit


read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i8[::1],)', cache=True)
def c(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N - 1, i + a)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1

    B = np.cumsum(B)
    return B


def main():
    N, K = map(int, readline().split())
    A = np.array(readline().split(), np.int64)


    K = min(K, 50)
    for _ in range(K):
        A = c(A)

    print(' '.join(A.astype(str)))


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

from copy import deepcopy


def main():
    h, w = map(int, input().split())
    s = ["#" * (w + 2)]
    for _ in range(h):
        s.append("#" + input() + "#")
    s.append("#" * (w + 2))

    b = [[0] * (w + 2) for _ in range(h + 2)]
    for hi in range(h + 2):
        for wi in range(w + 2):
            if s[hi][wi] == ".":
                b[hi][wi] = 1

    u = deepcopy(b)
    d = deepcopy(b)
    l = deepcopy(b)
    r = deepcopy(b)
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            if s[hi][wi] == ".":
                u[hi][wi] += u[hi-1][wi]
                l[hi][wi] += l[hi][wi-1]

    for hi in range(h, 0, -1):
        for wi in range(w, 0, -1):
            if s[hi][wi] == ".":
                d[hi][wi] += d[hi+1][wi]
                r[hi][wi] += r[hi][wi+1]

    ans = 0
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            cnt = u[hi][wi] + d[hi][wi] + l[hi][wi] + r[hi][wi] - 3
            ans = max(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]

    m = [[0] + [0 if e == "#" else 1 for e in s[i]] + [0] for i in range(h)]
    m.append([0] * (w + 2))
    m.insert(0, [0] * (w + 2))

    m_t = [[m[i][j] for i in range(h+2)] for j in range(w+2)]

    lr = []
    for i in range(h + 2):
        sm = 0
        row = []
        for j in range(w + 2):
            if m[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        lr.append(row)

    ud = []
    for i in range(w + 2):
        sm = 0
        row = []
        for j in range(h + 2):
            if m_t[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        ud.append(row)

    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            sm = lr[i][j] + ud[j][i] - 1
            ans = max(ans, sm)

    print(ans)


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

a,b,c,K=list(map(int,input().split()))
if a==b and b==c:
  print("0")
  exit()
for i in range(K):
  an=a
  bn=b
  cn=c
  a=bn+cn
  b=an+cn
  c=an+bn
S=a-b
if a-b>=10**18:
  print("Unfair")
  exit()
print(a-b)

### FIXED CODE ###

a,b,c,K=list(map(int,input().split()))
print((a-b)*((-1)**K))
### BUGGY CODE ###

import numpy as np

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

def xor_(x, y):
    p, q = tuple(sorted([x, y]))
    p = np.array(list(bin(p)))
    q = np.array(list(bin(q)))

    i = -1
    r = str()
    while p[i] != 'b':
        if p[i] == q[i]:
            r = '0' + r
        else:
            r = '1' + r
        i -= 1

    while q[i] != 'b':
        r = q[i] + r
        i -= 1
    
    r = '0b' + r

    return(int(r, 0))

sum = 0
for i in range(n-1):
    for j in range(i+1, n):
        sum += xor_(a[i], a[j])
        sum = sum % (10**9 + 7)

print(sum)
    



### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    ret = 0
    magni = 1
    for j in range(60):
        bin_cnt = [0, 0]
        for i in range(n):
            a[i], b = divmod(a[i], 2)
            bin_cnt[b] += 1
        x, y = bin_cnt
        ret += x * y * magni % mod
        magni = magni * 2 % mod

    ret %= mod

    print(ret)


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

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

bitruiseki = [[0]*21 for i in range(n+1)]

for i in range(n):
    ref = a[i]
    for j in range(20,-1,-1):
        if ref >= (1 << j):
            bitruiseki[i+1][j] = bitruiseki[i][j] + 1
            ref %= (1 << j)
        else:
            bitruiseki[i+1][j] = bitruiseki[i][j]

def check(l,r):
    for i in range(21):
        if bitruiseki[r][i] - bitruiseki[l][i] <= 1:
            pass
        else:
            return False
    return True

# 尺取り
ans = 0
right = 1
for i in range(n+1):
    right = max(right,i)
    if right < n:
        while (check(i,right+1) and right < n):
            right += 1
            if right == n:break
    ans += right - i
print(ans)

### FIXED CODE ###

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

bitruiseki = [[0]*21 for i in range(n+1)]

for i in range(n):
    ref = a[i]
    for j in range(20,-1,-1):
        if ref >= (1 << j):
            bitruiseki[i+1][j] = bitruiseki[i][j] + 1
            ref %= (1 << j)
        else:
            bitruiseki[i+1][j] = bitruiseki[i][j]

def check(l,r):
    for i in range(21):
        if bitruiseki[r][i] - bitruiseki[l][i] <= 1:
            pass
        else:
            return False
    return True

# 尺取り
ans = 0
right = 1
for i in range(n+1):
    right = max(right,i)
    if right < n:
        while (check(i,right+1) and right < n):
            right += 1
            if right == n:break
    ans += right - i
print(ans)
### BUGGY CODE ###

n, k = input().split()
p = list(map(int, input().split()))

n, k = int(n), int(k)

ans = 0

for i in range(n - k + 1):
    c = 0
    for j in range(k):
        c += p[i + j]
    c += k
    if c >= ans:
        ans = c


print(ans / 2)


### FIXED CODE ###

N,K = map(int,input().split())
Data  = map(int,input().split())
Data2 = [0]*N
for idx,data in enumerate(Data):
    e = data * (data+1) / 2 / data
    Data2[idx] = e
#print(Data2)
sum1 = 0
for i in range(K):
    sum1 += Data2[i]
ans = sum1
for i in range(0,N-K):
    sum1 -= Data2[i]
    sum1 += Data2[i+K]
    if ans < sum1:
        ans = sum1
print(ans)
### BUGGY CODE ###

S = input()
n = len(S)
S = int(S, 2)

A = 0
for i in range(0, n, 2):
    A += 2**i

B = 0
for i in range(1, n, 2):
    B += 2**i

ans = min(bin(S^A).count('1'), bin(S^B).count('1'))
print(ans)

### FIXED CODE ###

S = input()
n = len(S)
S = int(S, 2)

A = '0b'
B = '0b'
for i in range(n):
    if i % 2 == 0:
        A += '0'
        B += '1'
    else:
        A += '1'
        B += '0'

ans = min(bin(S ^ int(A, 0)).count('1'), bin(S ^ int(B, 0)).count('1'))
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = []
for i in range(N):
    ans.append(str(A.index(i + 1) + 1))
print(" ".join(ans))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [None for _ in range(N)]
for i, j in enumerate(A):
    ans[j-1] = str(i + 1)
print(" ".join(ans))
### BUGGY CODE ###

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

count = set([])

for i in range(len(S)-2):
    for j in range(i+1, len(S)-1):
        for k in range(j+1, len(S)):
            count.add(S[i]+S[j]+S[k])
    
print(len(count))

### FIXED CODE ###

N = input()
S = input()
ans = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            a = S.find(str(i))
            if a == -1:
                continue
            b = S.find(str(j), a+1)
            if b == -1:
                continue
            c = S.find(str(k), b+1)
            if c == -1:
                continue
            ans+=1

print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
ab_list = sorted([list(map(int, input().split())) for _ in range(M)])

ans = "IMPOSSIBLE"
second_island = []

for a, b in ab_list:
  if a == 1:
    second_island.append(b)

  if b == N:
    if a in second_island:
      ans = "POSSIBLE"
      break

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
sa = set()
sb = set()
for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        sb.add(b)
    if b == n:
        sa.add(a)

print('POSSIBLE' if len(sa&sb) != 0 else 'IMPOSSIBLE')
### BUGGY CODE ###

N = int(input())

sList = [0 for _ in range(N)]

for i in range(N) :
    s = list(input())
    s.sort()
    sList[i] = s

confilm = [False for _ in range(N)]

ans = 0
for i in range(N) :
    if confilm[i] :
        continue
    confilm[i] = True
    count = 1
    for j in range(i + 1, N) :
        if sList[i] == sList[j] :
            confilm[j] = True
            count += 1
    ans += count * (count - 1) // 2

print(ans)

### FIXED CODE ###

N = int(input())

sList = {}

for i in range(N) :
    s = list(input())
    s.sort()
    s = ''.join(s)

    if s in sList :
        sList[s] += 1
    else :
        sList[s] = 1

ans = 0
for _, num in sList.items() :
    ans += num * (num - 1) // 2

print(ans)
### BUGGY CODE ###

sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx,sy,0)]
for i in range(n):
    data.append(tuple(map(int,input().split())))
data.append((gx,gy,0))
for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=((data[i][0]-data[j][0])**2+(data[i][1]-data[j][1])**2)**0.5-data[i][2]-data[j][2]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

from heapq import heappush, heappop, heapify
dist=[10000000000 for i in range(len(g))]
dist[0]=0
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    if dist[v]<c:
        continue
    for i in range(len(g[v])):
        tmp=max(g[v][i][0],0)+c
        if tmp<dist[g[v][i][1]]:
            dist[g[v][i][1]]=tmp
            heappush(que,(tmp,g[v][i][1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

from collections import Counter

n = int(input())
a = Counter(map(int, input().split()))
q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  a[c] += a[b]
  del a[b]
  s = sum(x * y for x, y in a.items())
  print(s)


### FIXED CODE ###

from collections import Counter

n = int(input())
a = Counter(map(int, input().split()))
q = int(input())
s = sum(x * y for x, y in a.items())
for _ in range(q):
  b, c = map(int, input().split())
  s = s + (c - b) * a[b]
  a[c] += a[b]
  a[b] = 0
  print(s)
### BUGGY CODE ###

H, W, D = map(int, input().split())
mass = [0]*(H*W+1)
for y in range(1,H+1):
    for x,i in enumerate(input().split()):
        mass[int(i)]= (y,x+1)

Q = int(input())
for _ in range(Q):
    ans = 0
    L, R = map(int, input().split())
    while L < R:
        ans += abs(mass[L + D][0] - mass[L][0]) + abs(mass[L + D][1] - mass[L][1])
        L += D
    print(ans)

### FIXED CODE ###

H, W, D = map(int, input().split())
mass = [0]*(H*W+1)
for y in range(1,H+1):
    for x,i in enumerate(input().split()):
        mass[int(i)]= (y,x+1)

Q = int(input())
dp = [H*W+2]*(H*W+1)

for i in range(1,H*W+1):
    if i > D:
        dp[i] = dp[i-D] + abs(mass[i][0] - mass[i-D][0]) + abs(mass[i][1] - mass[i-D][1])
    else:
        dp[i] = mass[i][0] + mass[i][1]

for _ in range(Q):
    L, R = map(int, input().split())
    print(dp[R] - dp[L])
### BUGGY CODE ###

def f_c():
    n = int(input())
    s = input()

    stack, c = 1, 1
    for si in s[1:]:
        if si=="B":
            if stack%2==0:
                stack += 1
            else:
                c *= stack
                stack -= 1
        else:
            if stack%2==0:
                c *= stack
                stack -= 1
            else:
                stack += 1
    if stack!=0 or c==0:
        print(0)
    else:
        c %= (10**9+7)
        for i in range(1, n+1):
            c*=i
        print(c%(10**9+7))

if __name__ == "__main__":
    f_c()


### FIXED CODE ###

# import sys
# input = sys.stdin.readline
Q = 10**9+7
def main():
    N = int( input())
    S = input()
    left = 0
    ans = 1
    # for i in range(N*2):
    #     s = S[i]
    for s in S:
        if s == "B":
            if left%2 == 0:
                left += 1
            else:
                ans *= left
                left -= 1
        else:
            if left%2 == 1:
                left += 1
            else:
                ans *= left
                left -= 1
        ans %= Q
    if left > 0 or ans == 0:
        print(0)
        return
    for i in range(1,N+1):
        ans *= i
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

a, b, k = map(int, input().split())
l = [i for i in range(a, b + 1)]
ans = l[:k] + l[-k:]
ans = list(set(ans))
ans.sort()
for e in ans:
  print(e)

### FIXED CODE ###

a, b, k = map(int, input().split())
ans = []
for i in range(k):
  if a + i <= b:
    ans.append(a + i)
  if b - i >= a:
    ans.append(b - i) 
for i in sorted(set(ans)):
    print(i)
### BUGGY CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**5)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)
### BUGGY CODE ###

modout = lambda x: x%1000000007
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
N2 = N**2
M2 = M**2
Xpattern = [x * (N-x) for x in range(N)]
Ypattern = [y * (M-y) for y in range(M)]
coef = 1
num = min(K-2, N*M-K)
for i in range(N*M-2, N*M-2-num, -1):
    coef *= i
for j in range(1, num+1):
    coef //= j


print(modout((sum(Xpattern)*M2+sum(Ypattern)*N2)*coef))

### FIXED CODE ###

mod = 1000000007
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())


def cmb(n, r):
    if n<0 or r<0 or r>n:
        return None
    r = min(r, n-r)
    if r == 0:
        return 1
    if r == 1:
        return n
    numerator = [0]*r
    denominator = [0]*r
    for k in range(r):
        numerator[k] = n-r+k+1
        denominator[k] = k+1
    for p in range(2, r+1):
        pivot = denominator[p-1]
        if pivot > 1:
            offset = (n-r) % p
            for k in range(p-1, r, p):
                numerator[k-offset] //= pivot
                denominator[k] //= pivot
    res = 1
    for n in numerator:
        if n > 1:
            res *= n
    return res

N2 = N**2
M2 = M**2
Xpattern = [(x * (N-x)) % mod for x in range(N)]
Ypattern = [(y * (M-y)) % mod for y in range(M)]
coef = cmb(N*M-2, K-2)

print(((sum(Xpattern)*M2+sum(Ypattern)*N2)*coef)%mod)
### BUGGY CODE ###


N = int(input())
inlis = list(map(int,input().split()))
donelis =[]
numlis=[]

for i in inlis:
    donelis.append(i+1)
    donelis.append(i)
    donelis.append(i-1)
    if not i in numlis:
        numlis.append(i)
    if not i+1 in numlis:
        numlis.append(i+1)
    if not i-1 in numlis:
        numlis.append(i-1)
estc =0
for i in numlis:
    a =donelis.count(i)
    if estc < a:
        estc = a
print(estc)

### FIXED CODE ###

n = int(input())
inlis = list(map(int,input().split()))
donelis =[]
numlis=[]

for i in inlis:
    donelis.append(i+1)
    donelis.append(i)
    donelis.append(i-1)

estc =0
donelis.sort()
a = -2
count=0
for i in donelis:
    if a != i:
        if count > estc:
            estc = count
        count = 1
        a = i
    else:
        count +=1
if count >estc:
    estc =count
print(estc)