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

def read_nums():
    return map(int, raw_input().split(' '))


def is_in_the_map(x, y):
    return x < H-1 and x > 0 and y < W-1 and y > 0


def solve():
    res = [0 for _ in range(10)]
    for i in range(N):
        a = As[i]
        b = Bs[i]
        for j in [-1, 0, 1]:
            for k in [-1, 0, 1]:
                x_mid = a + j
                y_mid = b + k
                if not is_in_the_map(x_mid, y_mid) or memo[x_mid][y_mid] == 1:
                    continue
                memo[x_mid][y_mid] = 1
                count = 0
                for x_pad in [-1, 0, 1]:
                    for y_pad in [-1, 0, 1]:
                        x = x_mid + x_pad
                        y = y_mid + y_pad
                        if Map[x][y] == 1:
                            count += 1
                res[count] += 1
    res[0] = (H-2) * (W-2) - sum(res)
    return res


H, W, N = read_nums()
As = [0 for _ in range(N)]
Bs = [0 for _ in range(N)]
Map = [[0 for _ in range(W)] for _ in range(H)]
for i in range(N):
    a, b = read_nums()
    As[i] = a - 1
    Bs[i] = b - 1
    Map[a - 1][b - 1] = 1
memo = [[0 for _ in range(W)] for _ in range(H)]
res = solve()
for i in res:
    print i

### FIXED CODE ###

import collections


def read_nums():
    return map(int, raw_input().split(' '))


H, W, N = read_nums()

vs = []
for i in range(-1, 2):
    for j in range(-1, 2):
        vs.append((i, j))

cnt = []
for i in range(N):
    a, b = read_nums()
    for v in vs:
        i, j = v
        x = a + i
        y = b + j
        if x >= 2 and x <= H-1 and y >= 2 and y <= W-1:
            cnt.append(x * W + y)

cnt = collections.Counter(cnt)
cnt2 = [0] * 10
cnt2[0] = (H - 2) * (W - 2)

for k in cnt:
    cnt2[cnt[k]] += 1
    cnt2[0] -= 1

for c in cnt2:
    print c
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
ans = 0
for r in range(R * N//R+1):
  for g in range(G * N//G+1):
    if R*r + G*g > N: break
    if (N - R*r - G*g) % B == 0:
      ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())
ans = 0

a = max(R, G, B)
if a == R:
  b = max(G, B)
elif a == G:
  b = max(B, R)
else:
  b = max(R, G)
c = min(R, G, B)
for i in range(N//a+1):
  for j in range((N-a*i)//b+1):
    if ((N-a*i)-b*j)%c == 0:
      ans += 1
print(ans)
### BUGGY CODE ###

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = [(si, sj)]
    while queue:
        i, j = queue.pop()
        for di, dj in D:
            for s in range(1, k + 1):
                ni, nj = i + s * di, j + s * dj
                if not (0 <= ni < m and 0 <= nj < n):
                    break
                if grid[ni][nj] == '@':
                    break
                if dist[ni][nj] <= dist[i][j]:
                    break
                dist[ni][nj] = dist[i][j] + 1
                queue.append((ni, nj))

    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()

### FIXED CODE ###

import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    m, n, k = map(int, input().split())
    si, sj, ti, tj = map(lambda x : int(x) - 1, input().split())
    grid = [input() for _ in range(m)]

    dist = [[INF] * n for _ in range(m)]
    dist[si][sj] = 0
    D = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(si, sj)])
    while queue:
        i, j = queue.popleft()
        for di, dj in D:
            for s in range(1, k + 1):
                ni, nj = i + s * di, j + s * dj
                if not (0 <= ni < m and 0 <= nj < n):
                    break
                if grid[ni][nj] == '@':
                    break
                if dist[ni][nj] <= dist[i][j]:
                    break
                if dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    queue.append((ni, nj))

    ans = dist[ti][tj]
    if ans == INF:
        ans = -1
    print(ans)
resolve()
### BUGGY CODE ###

import sys

def parent(i):
    return (i + 1) / 2 - 1

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def sibling(i):
    if i % 2 == 0:
        return i - 1
    else:
        return i + 1

def insert(S, k):
    S.append(k)
    idx = len(S) - 1
    while True:
        p = parent(idx)
        if p < 0 or S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p

def extract(S):
    print S[0]
    S[0] = S[-1]
    S.pop()

    idx = 0
    while True:
        l, r = left(idx), right(idx)
        if r < len(S):
            if S[idx] < S[l] and S[r] <= S[l]:
                S[idx], S[l] = S[l], S[idx]
                idx = l
            elif S[idx] < S[r] and S[l] <= S[r]:
                S[idx], S[r] = S[r], S[idx]
                idx = r
            else:
                break
        elif l < len(S):
            if S[idx] < S[l]:
                S[idx], S[l] = S[l], S[idx]
                idx = l
            else:
                break
        else:
            break

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    lines.pop()

    S = []
    for line in lines:
        if line[0] == "i":
            insert(S, int(line[7:]))
        else:
            extract(S)

### FIXED CODE ###

import sys

def insert(k):
    global S, last
    S[last] = k
    idx = last
    while True:
        p = (idx + 1) / 2 - 1
        if S[idx] <= S[p]:
            break
        else:
            S[idx], S[p] = S[p], S[idx]
            idx = p
    last += 1

def maxHeapify(i):
    global S, last
    l = 2 * i + 1
    r = 2 * i + 2

    if l < last and S[l] > S[i]:
        largest = l
    else:
        largest = i

    if r < last and S[r] > S[largest]:
        largest = r

    if largest != i:
        S[i], S[largest] = S[largest], S[i]
        maxHeapify(largest)

def extract():
    global S, last
    print S[0]
    last -= 1
    S[0], S[last] = S[last], 0
    maxHeapify(0)

lines = sys.stdin.readlines()
lines.pop()

S = [0] * 2000001
S[2000000] = 2000000000
last = 0
for line in lines:
    if line[0] == "i":
        insert(int(line[7:]))
    else:
        extract()
### BUGGY CODE ###

N = int(input())
A = [int(zz) for zz in input().split()]
B = set(A)

ans = 0
for i in B:
    p = A.count(i)
    if i > p:
        ans += p
    elif i < p:
        ans += p - i

print(ans)


### FIXED CODE ###

import bisect

N = int(input())
A = [int(zz) for zz in input().split()]
B = set(A)
A.sort()
ans = 0
for i in B:
    p = bisect.bisect_right(A, i) - bisect.bisect_left(A, i)
    if i > p:
        ans += p
    elif i < p:
        ans += p - i

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

def solve():
  s = input()
  t = input()
  ans = 0
  alp = [[] for _ in range(27)]
  length_s = len(s)
  for i in range(length_s):
    char = ord(s[i]) - ord('a')
    alp[char].append(i + 1)
  length_t = len(t)
  import bisect
  for i in range(length_t):
    char = ord(t[i]) - ord('a')
    if alp[char]:
      if ans % length_s >= max(alp[char]):
        ans = (ans // length_s + 1) * length_s
      index = bisect.bisect_right(alp[char], ans % length_s)
      ans += alp[char][index] - ans % length_s
    else:
      return -1
  return ans
print(solve())

### FIXED CODE ###

def solve():
  s = input()
  t = input()
  ans = 0
  alp = [[] for _ in range(27)]
  length_s = len(s)
  for i in range(length_s):
    char = ord(s[i]) - ord('a')
    alp[char].append(i + 1)
  length_t = len(t)
  import bisect
  for i in range(length_t):
    char = ord(t[i]) - ord('a')
    if alp[char]:
      if ans % length_s >= alp[char][-1]:
        ans = (ans // length_s + 1) * length_s
      index = bisect.bisect_right(alp[char], ans % length_s)
      ans += alp[char][index] - ans % length_s
    else:
      return -1
  return ans
print(solve())
### BUGGY CODE ###

import bisect
import math
def binomial(n, k):
    m = min(k,n-k)
    a = 1
    for i in range(m):
        a *= n
        n -=1
    return a//math.factorial(m)

n =  int(input().strip())
nums  = list(map(int, input().strip().split(' ')))
sortedNums = sorted(nums)
candidates = []
for i in nums:
    insert_index  = bisect.bisect_left(sortedNums,int(i/2))
    if(insert_index == n-1):
        candidates.append((i,sortedNums[insert_index-1]))
    elif(i/2 - sortedNums[insert_index] <= sortedNums[insert_index+1] - i/2):
        candidates.append((i,sortedNums[insert_index]))
    else:
        candidates.append((i,sortedNums[insert_index+1]))

minIndex, tmpMax = 0, 0
for index, value in enumerate(candidates):
    b = binomial(value[0],value[1])
    if(tmpMax < b):
        minIndex = index
        tmpMax = b

print(candidates[minIndex][0], candidates[minIndex][1])


### FIXED CODE ###

import bisect
import math
n =  int(input().strip())
nums  = list(map(int, input().strip().split(' ')))
sortedNums = sorted(nums)
x = sortedNums[-1]
insert_index  = bisect.bisect_left(sortedNums,int(x/2))
if insert_index == 0: y = sortedNums[0]
else:
    if x/2 - sortedNums[insert_index-1] > sortedNums[insert_index]-x/2: y = sortedNums[insert_index]
    else: y = sortedNums[insert_index - 1]
if n==2: y=sortedNums[0]
print(x,y)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    n = II()
    a_s = LI()
    kaizyo = [1]
    kaizyo_append = kaizyo.append
    keta = [0 for i in range(60)]
    ans = 0
    for i in range(60):
        kaizyo_append(kaizyo[i] * 2 % MOD)
    for i in a_s:
        for i, v in enumerate(format(i, 'b')[::-1]):
            keta[i] += int(v)
    for i, v in enumerate(keta):
        c = v * (n-v) % MOD
        ans += c * kaizyo[i]
        ans = ans % MOD
        # print(ans, c, kaizyo[i])

    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())

def main():
    n = II()
    a_s = LI()
    kaizyo = [1]
    kaizyo_append = kaizyo.append
    keta = [0 for i in range(60)]
    ans = 0
    for i in range(60):
        kaizyo_append(kaizyo[i] * 2 % MOD)
    for i in a_s:
        for j in range(60):
            v, i = i % 2, i // 2
            keta[j] += v
    for i, v in enumerate(keta):
        c = v * (n-v) % MOD
        ans += c * kaizyo[i] % MOD
        ans = ans % MOD

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

import math

from fractions import Fraction
n=int(input())
x=list(map(int,input().split()))
l=[1]
for i in range(1,n-1):
    l.append(l[-1]+Fraction(1,i+1))
#print(l)

for i in range(n-1):
    l[i]=l[i]*(x[i+1]-x[i])%(10**9+7)

ans=sum(l)
ans=ans*math.factorial(n-1)%(10**9+7)
print(ans)


### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
ans=math.factorial(n-1)%(10**9+7)

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

c=0
for i in range(1,n):
    c+=(a[-1]-a[i-1])*modinv(i, mod=10**9+7)
print(ans*c%(10**9+7))
### BUGGY CODE ###

n = int(input())
a = [0] * n
b = [0]*n
for i in range(n):
    a[i],b[i] = list(map(int,input().split()))
amax = max(a)
bmin = min(b)
ans = 0

for i in range(bmin):
    amax += 1

print(amax)


### FIXED CODE ###

n = int(input())
a = [0] * n
b = [0] * n
amax = 1
bmin = 9999999990
for i in range(n):
    a[i],b[i] = list(map(int,input().split()))
amax = max(a)
bmin = min(b)
ans = amax +bmin

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

n = int(input())
l = [int(i) for i in input().split()]


ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if l[j] == l[i]:
            ans += 1

for i in range(n):
    ans_i = 0
    for j in range(n):
        if j != i:
            if l[i] == l[j]:
                ans_i += 1
    print(ans - ans_i)

### FIXED CODE ###

from collections import Counter

n = int(input())
l = [int(i) for i in input().split()]

S = Counter(l)

ans = 0
for i in S.values():
    ans += int(i * (i - 1) / 2)

for i in range(n):
    val = S[l[i]]
    print(ans - val + 1)
### BUGGY CODE ###

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

sum = 0
mod = 10**9 + 7
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i] * A[j] % mod
print(sum % mod)
        

### FIXED CODE ###

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

c_sum = sum(A)
mod = 10**9 + 7
ans = 0

for i in range(N-1):
    c_sum -= A[i]
    ans += A[i] * c_sum % mod
ans %= mod
print(ans)
### BUGGY CODE ###

h,n=map(int,input().split())

lists=[]
for i in range(n):
    a,b=map(int,input().split())
    lists.append([a,b])
    
    
#dic[x]=y モンスターの体力をｘ減らすために必要な魔力
minimum=[10**9 for i in range(20001)]
#minimum[k]=ダメージｋを与えるために最小の魔力
minimum[0]=0
for i in range(1,20001):
    for j in range(n):
        if i>=lists[j][0]:
            minimum[i]=min(minimum[i-lists[j][0]]+lists[j][1],minimum[i])
        else:
            minimum[i]=minimum[i]
ans=10**8
for k in range(h,20001):
    ans=min(ans,minimum[k])
print(ans)


### FIXED CODE ###

h,n=map(int,input().split())

lists=[]
for i in range(n):
    a,b=map(int,input().split())
    lists.append([a,b])
    
    
#dic[x]=y モンスターの体力をｘ減らすために必要な魔力
minimum=[10**9 for i in range(20001)]
#minimum[k]=ダメージｋを与えるために最小の魔力
minimum[0]=0
for i in range(1,20001):
    for j in range(n):
        if i>=lists[j][0]:
            minimum[i]=min(minimum[i-lists[j][0]]+lists[j][1],minimum[i])
        else:
            minimum[i]=minimum[i]
ans=10**8
for k in range(h,20001):
    ans=min(ans,minimum[k])
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, X, Y = map(int,input().split())

    ans = [0] * N

    for i in range(N):
        approched = [False] * N

        que = deque([[i,0]])
        approched[i] = True

        while que:
            pos,distance = que.popleft()

            if pos + 1 < N and not approched[pos + 1]:
                que.append([pos + 1, distance + 1])
                approched[pos + 1] = True
                ans[distance + 1] += 1

            if pos - 1 >= 0 and not approched[pos - 1]:
                que.append([pos - 1, distance + 1])
                approched[pos - 1] = True
                ans[distance + 1] += 1

            if (pos == X - 1) and not approched[Y -1]:
                que.append([Y -1, distance + 1])
                approched[Y -1] = True
                ans[distance + 1] += 1

            if (pos == Y - 1) and not approched[X -1]:
                que.append([X -1, distance + 1])
                approched[X -1] = True
                ans[distance + 1] += 1

    for x in map(lambda x: x//2, ans[1:]):
        print(x)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def main():
    N, X, Y = map(int,input().split())
    X, Y = X - 1, Y - 1

    # iからjまでの距離
    # 到達の仕方は以下の３パターンなので、このうち最小が最短の距離になる
    # 直線のパターン
    # |j - i|
    # まずiからXまでいって、その後XからYまでジャンプ、Yからjまでのパターン
    # |X - i| + 1 + |j - Y|
    # まずiからYまでいって、その後YからXまでジャンプ、Xからjまでのパターン
    # |Y - i| + 1 + |j - X|

    ans = [0] * N

    for i in range(N - 1):
        for j in range(i + 1, N):
            ij = abs(j - i)
            ixyj = abs(X - i) + 1 + abs(j - Y)
            iyxj = abs(Y - i) + 1 + abs(j - X)

            dist = min(ij, ixyj, iyxj)

            ans[dist] += 1

    for a in ans[1:]:
        print(a)


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

from math import gcd

def solve():
    n, m = map(int, input().split())
    d = m // n
    p = m % n
    res = max(1, gcd(d, d + p))
    while d > 1:
        d -= 1
        q = m - n * d
        res = max(res, gcd(d, d + q))
    print(res)


solve()

### FIXED CODE ###

from math import gcd

def solve():
    n, m = map(int, input().split())
    d = m // n
    p = m % n
    res = max(1, gcd(d, d + p))
    if p == 0:
        print(res)
        exit()
    while d > res:
        d -= 1
        p += n
        if p % d == 0:
            res = max(res, d)
    print(res)


solve()
### BUGGY CODE ###

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

ans = 0
for i in range(1,N+1):
  for j in range(1,N+1):
      for k in range(1,N+1):
        if ((i + j) % K == 0 and (j + k) % K == 0 and (k + i) % K == 0):
          ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
if (K % 2 != 0):
  ans = (N // K) ** 3
else:
  for i in range(1,N+1):
    if (i % K == int(K / 2)):
      ans += 1
  ans = ans ** 3 + (N // K) ** 3
print(ans)
### BUGGY CODE ###

from itertools import combinations
import math
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)


N,M,K = map(int,input().split())
ans = 0
mod = 10**9 +7
by = cmb(N*M-2,K-2,mod)

#まずは、X軸の総和を求める。
X = []
for i in range(1,N+1):
    for j in range(M):
        X.append(i)

for a,b in list(combinations(X,2)):
    ans = (ans + abs(a-b)*by%mod)%mod


Y = []
for i in range(1,M+1):
    for j in range(N):
        Y.append(i)

for a,b in list(combinations(Y,2)):
    ans = (ans + abs(a-b)*by%mod)%mod

print(ans)

### FIXED CODE ###

import math
def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
mod = 10**9 +7
N,M,K = map(int,input().split())
ans = 0
memo = choose(N*M-2,K-2)
memo %= mod
#まずはX軸について、総和を考える
d = 1
while d < M:
    ans += d*memo*(M-d)*N*N
    d += 1
    ans %= mod

#Y軸について、総和を考える
d = 1
while d < N:
    ans += d*memo*(N-d)*M*M
    d += 1
    ans %= mod

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

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
ct = 0
for i in range(N-1):
    for j in range(i+1, N):
        x = A[i] * A[j]
        ct += x
print((ct % mod))


### FIXED CODE ###

# C　Sum of product of pairs
N = int(input())
A = list(map(int, input().split()))
t = sum(A)
x = t - A[0]
mod = 10 ** 9 + 7
ct = 0
for i in range(N-1):
    ct += A[i] * x
    x = x - A[i+1]

print((ct % mod))
int((ct % mod))
### BUGGY CODE ###

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

m=li[0]
for i in range(1,N):
  a=m*li[i]
  m=a
 
if m>10**18:
  print(-1)
else:
  print(m)

### FIXED CODE ###

N=int(input())
li=list(map(int,input().split()))
 
m=li[0]
if 0 in li:
  m=0
else:
  for i in range(1,N):
    m=m*li[i]
    if m>10**18:
      m=-1
      break
print(m)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))

for i in range(N):
    if i == 0:
        print(max(A[1:]))
    elif i == N - 1:
        print(max(A[:N-1]))
    else:
        print(max(A[:i]+A[i+1:]))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
sortA = sorted(A, reverse=True)
maxA = sortA[0]
secondA = sortA[1]
for i in range(N):
    if A[i] != maxA:
        print(maxA)
    else:
        print(secondA)
### BUGGY CODE ###

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

p=1
for i in range(k):
    p*=a[i]

p1=0
p2=k

last=p
for i in range(k,n):
    p = p//a[p1]
    p*=a[p2]
    p1+=1
    p2+=1
    if p>last:
        print('Yes')
    else:
        print('No')
    last=p



    


### FIXED CODE ###

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


p1=0
p2=k

for i in range(k,n):
    if a[p2]>a[p1]:
        print('Yes')
    else:
        print('No')
    p1+=1
    p2+=1
### BUGGY CODE ###

input_line=int(input())
ARC = [int(i)for i in input().split()]
count=0
for i in range(10**5):
  AARC = ARC
  for s in ARC:
    if s<i:
      while s in AARC:
        AARC.remove(s)
  if (input_line//2)== len(AARC):
    count+=1

print(count)

### FIXED CODE ###

input_line=int(input())
ARC = [int(i)for i in input().split()]
ARC.sort()
middle = input_line //2
s = ARC[middle]-ARC[middle-1]

print(s)
### BUGGY CODE ###

def pow(x,n,mod):
    ans = 1
    while n>0:
        if n&1==1:
            ans *= x
            ans%=mod
        x*=x
        x%=mod
        n = n>>1
    return ans

MOD=998244353
N,M,K=map(int,input().split())

ans=M*pow(M-1,N-1,MOD)%MOD
a=1
b=1
for i in range(1,K+1):
    a*=N-i
    b*=i
    ans+=M*pow(M-1,N-i-1,MOD)*int(a//b)
    ans%=MOD
print(ans)

### FIXED CODE ###

mod=998244353

class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod
 
    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod

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

C=Combination(N)
ans=0
c=[1]*(N)
for i in range(1,N):
    c[i]=c[i-1]*(M-1)%mod
for i in range(K+1):
    tmp=M*c[N-i-1]*C.calc(N-1,N-i-1)%mod
    ans=(ans+tmp)%mod
print(ans)
### BUGGY CODE ###

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

if min(A)==1:
  print(1)
  exit()

while len(A)>1:
  monster_min = A.pop(A.index(min(A)))
  for i in range(len(A)):
    A[i] %= monster_min
  A.sort()
  for i in A[:]:  
    if i == 0: A.remove(i)
    else: continue
  A.append(monster_min)

print(A[0])


### FIXED CODE ###

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

if min(A)==1:
  print(1)
  exit()

while len(A)>1:
  monster_min = A.pop(A.index(min(A)))
  for i in range(len(A)):
    A[i] %= monster_min
  A.sort()
  for i in A[:]:  
    if i == 0: A.remove(i)
    else: continue
  A.append(monster_min)

print(A[0])
### BUGGY CODE ###

s = input()

count = 0

oi1000 = "0"*1000 + "1"*1000
io1000 = "1"*1000 + "0"*1000

while oi1000 in s or io1000 in s:
    while oi1000 in s:
        s = s.replace(oi1000, "", 1)
        count += 1000
    while io1000 in s:
        s = s.replace(io1000, "", 1)
        count += 1000

oi100 = "0"*100 + "1"*100
io100 = "1"*100 + "0"*100

while oi100 in s or io100 in s:
    while oi100 in s:
        s = s.replace(oi100, "", 1)
        count += 100
    while io100 in s:
        s = s.replace(io100, "", 1)
        count += 100

while "01" in s or "10" in s:
    while "01" in s:
        num = s.count("01")
        s = s.replace("01", "")
        count += num
    while "10" in s:
        num = s.count("10")
        s = s.replace("10", "")
        count += num

print(count * 2)


### FIXED CODE ###

s = input().rstrip()
a = s.count("0")
b = s.count("1")
print(min(a,b)*2)