CodeEff/ECCO huggingface dataset:
# Original solution
import math

N, A, B = list(map(int, input().split()))
h = [int(eval(input())) for _ in range(N)]


def check(t):
    cnt = 0
    ab = A - B
    bt = B * t
    for i in range(N):
        r = (h[i] - bt)
        if r <= 0:
            continue
        cnt += r // ab
        if r % ab:
            cnt += 1
    return cnt <= t


left = 1
right = max(h)
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)


# Optimized solution
N, A, B = list(map(int, input().split()))
h = [int(eval(input())) for _ in range(N)]

ab = A - B


def check(t):
    cnt = 0
    bt = B * t
    for hi in h:
        r = hi - bt
        if r <= 0:
            continue
        cnt += r // ab
        if r % ab:
            cnt += 1
    return cnt <= t


left = 1
right = max(h)
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)
# Original solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    h = [int(input().rstrip('\n')) for _ in range(n)]

    cor_v = 10 ** 20
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for v in h:
            if v > bin_v * b:
                cost += (v - bin_v * b + (a - b) - 1) // (a - b)
        #costが制約を満たすか
        if cost <= bin_v:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()


# Optimized solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    h = [int(input().rstrip('\n')) for _ in range(n)]
    cor_v = 10 ** 16
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        for i in range(n):
            hp = h[i] - bin_v * b
            if hp > 0:
                cost += (hp + (a - b) - 1) // (a - b)
        #costが制約を満たすか
        if cost <= bin_v:
            cor_v = bin_v
        else:
            inc_v = bin_v
    print(cor_v)


if __name__ == '__main__':
    solve()
# Original solution
import copy
import math
n, a, b = list(map(int, input().split()))
h = [int(eval(input())) for _ in range(n)]

def is_ok(x):
    t = copy.deepcopy(h)
    y = x
    for i in range(n):
        t[i] -= b * x
        if t[i] > 0:
            y -= math.ceil(t[i] / (a - b))
    return y >= 0

ng = 0
ok = 10 ** 9
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

print(ok)


# Optimized solution
import math

n, a, b = list(map(int, input().split()))
h = [int(eval(input())) for _ in range(n)]

def is_ok(x):
    c = 0
    for i in range(n):
        t = h[i] - b * x
        if t <= 0:
            continue
        c += math.ceil(t / (a - b))
    return c <= x

ng = 0
ok = 10 ** 9
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

print(ok)
# Original solution
# int(input()) # 入力が1つ
from math import ceil
n, a, b = list(map(int, input().split())) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字

monster = []
for i in range(n):
    monster.append(int(eval(input())))

def check(monster, t):
    temp = []
    for i in range(n):
        temp.append(monster[i] - b * t) 
    ans = 0
    for i in range(n):
        if temp[i] > 0:
            ans += ceil(temp[i] / (a - b))
    if ans <= t:
        return True
    return False

l = 0
r = 10 ** 10
ans = 10 ** 10
while l <= r:
    mid = (l + r) // 2
    if check(monster, mid):
        ans = min(ans, mid)
        r = mid - 1
    else:
        l = mid + 1
print(ans)

# Optimized solution
# https://atcoder.jp/contests/abc063/tasks/arc075_b
n, a, b = list(map(int, input().split()))

monster = []
for i in range(n):
    monster.append(int(eval(input())))

def damage(monster, t):
    temp = []
    for hp in monster:
        s = hp - t * b
        if s > 0:
            temp.append(s)
    ans = 0
    for hp in temp:
        if hp % (a - b) != 0:
            ans += 1
        ans += hp // (a - b)
    return True if ans <= t else False

ans = float('inf')
l = 0
r = 10 ** 9
while l <= r:
    mid = (l + r) // 2
    if damage(monster, mid):
        ans = min(ans, mid)
        r = mid - 1
    else:
        l = mid + 1
print(ans)
# Original solution
import math
N, A, B = list(map(int, input().split()))
H = [int(eval(input())) for i in range(N)]
    
def f(x):
    s = sum([math.ceil(max(0, h - x * B) / (A - B)) for h in H])
    if s <= x:
        return True
    else:
        return False
    
l = 0
r = 10 ** 9 + 7
while r - l > 1:
    m = (l + r) // 2
    if f(m):
        r = m
    else:
        l = m
    # print(r, l, m)
        
print(r)

# Optimized solution
N, A, B = list(map(int, input().split()))
H = [int(eval(input())) for i in range(N)]
    
def f(x):
    s = sum([- (- max(0, h - x * B) // (A - B)) for h in H])
    if s <= x:
        return True
    else:
        return False
    
l = 0
r = 10 ** 9 + 7
while r - l > 1:
    m = (l + r) // 2
    if f(m):
        r = m
    else:
        l = m
    # print(r, l, m)
        
print(r)
# Original solution
"""
AtCoder Grand Contest 041  B - Voting Judges


N個の問題があり、M人がそれぞれV問に１点足していく。同じ人が同じ問題に点は入れられない。
全員が点を入れた後、得点の大きいものからP個選ばれる。
選ばれうる可能性のある問題の個数を考える。

例えば1,2,3,4,5,6,7,8,9,10として、３人が４問に加点するのを考える。その後４問が選ばれるとする
５がえらばれうるか考えてみる。
５に３点入れて、残りは５未満に足しておけば８に並ぶので選ばれうる。
上位一位にいくより上位４位にはいる方が縛りが緩そう。１～４のどこにいてもいいので。

なので、とりあえず４位になることを目標とする。
４位になるには上位３位の10,9,8には負けててもいいが、少なくとも７に並ぶ必要がある。
また、投票者が３人なので、多くても＋３しかされない。

とりあえず５にとって最善の＋３した場合を考える。
このときに７に＋２とか６に＋３とかされて８を上回られると選ばれない。
なので、５的には、自分に最大に点を割り振って、残りは順位に影響ないところで使いつぶすのが嬉しい。

１～４について、＋３しても順位に影響ないから、これらには割り振る。
８～１０についても、５的には４位に入ることができたら問題ないので、これらについても＋３して問題ない。
ついで、６，７であるが、これが９になると５は勝てないので、こいつらには＋した結果でも８にとどまってほしい。

こんな感じで、P位になるためにある数字に最大に割り振って、残りを使いつぶす。
で、全体でM*V点持っていて、使いつぶしたときにこれを使い切っていなければ、今回でいうところの６とか７に振るしかなくなる。
そのときは選ばれる可能性がない。
みたいな？

"""
import bisect


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

A.sort(reverse=True)

l = P - 1
r = N
while r - l > 1:
    mid = (l + r) // 2

    curr_max = A[mid] + M
    if curr_max < A[P-1]:
        r = mid
        continue

    cnt = 0
    # P位になれればよいので、P位以降に対して見る
    for i in range(P-1, N):
        if i == mid:
            continue
        # A[mid]以下の値は＋MしてOK、それ以外はcurr_maxと同じ値までは＋してよい
        cnt += min(M, max(0, curr_max - A[i]))

    # 上位P-1とA[mid]に振った分をのぞいて、都合いい感じに振ったものが、余りを上回れば、選ばれうる
    if cnt >= M * (V - P):
        l = mid
    else:
        r = mid

# lがギリギリ選ばれるもののインデックス（下限）なので、+1して要素数というか個数にする
print((l + 1))

# Optimized solution


N,M,V,P = list(map(int, input().split()))

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


A.sort(reverse=True)
ok = P-1
ng = N 
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    curr_max = A[mid] + M

    if curr_max < A[P-1]:
        ng = mid
        continue

    cnt = 0
    # midと上位P-1位に＋Mした分
    cnt += M + (P-1) * M
    for i in range(P-1, N):
        if i == mid: continue

        cnt += min(M, max(0, curr_max - A[i]))

    if cnt >= M*V:
        ok = mid
    else:
        ng = mid

print((ok + 1))
# Original solution
import sys
from bisect import bisect_right as bi_r
from heapq import heapify, heappop, heappush

n, m, v, p, *a = list(map(int, sys.stdin.read().split()))

def main():
    a.sort()
    # return a

    for i in range(n):
        l = bi_r(a, a[i]) - 1
        r = max(0, v - l - 1)
        if r >= p:
            cand = a[l+1:n-p+1]
            ma = cand[-1]
            heapify(cand)
            remain = m * (r - (p - 1))
            while True:
                x = heappop(cand)
                if x == ma:
                    heappush(cand, x)
                    break
                d = ma - x
                if remain < d:
                    remain = 0
                    break
                remain -= d
                heappush(cand, ma)

            if not remain:
                if a[i] + m >= ma:
                    return n - i
            le = len(cand)
            ma += (remain + le - 1) // le
            if a[i] + m >= ma:
                return n - i
        else:
            if a[i] + m >= a[n-p]:
                return n - i

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

# Optimized solution
import sys

n, m, v, p, *a = list(map(int, sys.stdin.read().split()))
a.sort(reverse=True)

def possible(i):
    score = a[i] + m
    if i < p:
        return True
    else:
        every_ok = p - 1 + n - i 
        if every_ok >= v:
            if score >= a[p-1]:
                return True
            else:
                return False
        else:
            s = m * (v - every_ok)
            limit = 0
            for j in range(p-1, i):
                if a[j] > score:
                    return False
                limit += score - a[j]
            if s > limit:
                return False
            return True

def main():
    lo = -1
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if possible(i):
            lo = i
        else:
            hi = i
        
    return lo + 1

if __name__ == '__main__':
    ans = main()
    print(ans)
# Original solution
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in list(currentframe().f_back.f_locals.items())}
    print((', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args)))

def main():
    N, M, V, P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(list(dic_A.items()), key=lambda x: x[1], reverse=True)
    # chkprint(sorted_dic_A)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    # chkprint(B)
    C = sorted_dic_A[P:]
    # chkprint(C)

    ans = set()

    num_vote = M * V
    # chkprint(num_vote)
    for i, v in C:
        if P_min_val > v + M:
            break
        margin = num_vote
        margin -= M * (P-1)
        margin_list = [v+M-w for (j,w) in C if j!=i]
        mod_margin_list = list([x if x < M else M for x in margin_list])
        # chkprint(margin_list)
        # chkprint(mod_margin_list)
        margin -= M
        margin -= sum(mod_margin_list)
        # chkprint(margin)
        if margin <= 0:
            ans.add(i)

    for i, _ in B:
        ans.add(i)

    print((len(ans)))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N, M, V, P = list(map(int, input().split()))
    A = list(map(int, input().split()))
    sorted_A = sorted(A, reverse=True)

    def is_possible(i):
        # Aは降順 -> sorted_A、
        # i+1番目以降の問題のスコアをi番目の問題のスコア以下になるように投票すれば
        # i番目の問題に採用される可能性が生まれるという考え方

        # 投票前の上位P問は採用される可能性がある
        if i < P:
            return True

        # 残り投票数
        num_votes = V * M

        # i番目の問題を採用させようとする場合は、M人のジャッジ全員がi番目の問題に投票すればよい
        score_i = sorted_A[i] + M
        num_votes -= M

        # M人のジャッジ全員がi番目の問題に投票しても、上位P問にスコアが上がらない場合は採用される可能性がない
        if sorted_A[P - 1] > score_i:
            return False

        # 上の操作からi+1番目以降のの問題のスコアを、i番目の問題のスコアを超えることがないため、
        # M人のジャッジ全員がi+1番目以降の問題に投票してもよい
        num_votes -= (N - i - 1) * M

        # i番目の問題が上位P問に入ればよいので、P-1位の問題にもM人のジャッジ全員が投票してもよい
        num_votes -= (P - 1) * M

        # P番目からi番目
        # print('margin: {}, num_votes: {}'.format(sum(score_i - j for j in sorted_A[P-1 : i]), num_votes))
        return sum(score_i - j for j in sorted_A[P-1 : i]) >= num_votes

    # 1番目は必ず採用される
    # N番目は採用されるか
    if is_possible(N-1):
        print(N)

    # 1番目:採用、N番目:採用されない
    # -> [1:N-1]のどこに採用の境界があるかを二分探索する
    else:
        low = 0
        hight = N - 1

        while hight - low > 1:
            middle = (hight + low) // 2
            # print('PRE - low:{}, middle:{}, hight:{}'.format(low, middle, hight))
            if is_possible(middle):
                low = middle
            else:
                hight = middle
            # print('AFT - low:{}, middle:{}, hight:{}'.format(low, middle, hight))

        print((low + 1))


if __name__ == '__main__':
    main()
# Original solution
from collections import deque

N, M, V, P = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    D = deque([d for d in D if d > 0])
    cnt = 0

    while D:
        cnt += 1
        E = []
        for _ in range(min(W, len(D))):
            E.append(D.pop())
        for e in E:
            e -= 1
            if e > 0:
                D.append(e)

    return cnt <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)

# Optimized solution
N, M, V, P = list(map(int, input().split()))
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = -(-(sum(D) - W) // W) + 1

    return max(max(D), cnt) <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)
# Original solution
def check(n):

    if n <= P-1:
        return True
    
    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = 0

if check(right):
    print(N)
    exit()

while abs(right-left) > 1 and check(left) and not check(right):

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print((left+1))

# Optimized solution
def check(n):

    if n <= P-1:
        return True
    
    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = 0

if check(right):
    print(N)
    exit()

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print((left+1))
# Original solution
n, m, v, p = list(map(int, input().split()))
a = sorted(list(map(int, input().split())), reverse=True)
ans = p
c = [0]
cnt = 0
for i in range(n):
  # 累積和
  cnt += a[i]
  c.append(cnt)
  
from bisect import bisect_right
for i in range(p,n):
  h = a[i]+m
  free = v - (p-1) - (n-i)
  if free >= 0 and h >= a[p-1]:
    d = h * (i-p+1) - (c[i]-c[p-1]) # 余裕
    if d >= free*m:
      ans += 1
  else:
    if h >= a[p-1]:
      ans += 1
print(ans)


# Optimized solution
N, M, V, P = list(map(int, input().strip().split()))
A = sorted(list(map(int, input().strip().split())),reverse=True)
ans=P

sum_=[0]*N
sum_[0]=A[0]
for i in range(1,N):
    sum_[i]=(sum_[i-1]+A[i])
# sum_=[0]
# cnt=0
# for i in range(N):
#   # 累積和
#   cnt += A[i]
#   sum_.append(cnt)

for i in range(P,N):
    thre=A[i]+M
    if thre < A[P-1]:
        continue

    remain=V-(P-1)-(N-i)
    if remain <=0:
        ans+=1
    else:
        if P!=1:
            if sum_[i-1]-sum_[P-2]+M*remain <= thre*(i-P+1):
                ans+=1
        else:
            if sum_[i-1]+M*remain <= thre*(i-P+1):
                ans+=1
print(ans)
# Original solution
from math import floor

def main(N, rate=1.08):
    ans = -1
    for x in range(1, N+1):
        if floor(x * 1.08) == N:
            ans = x
    return ans


if __name__ == "__main__":
    N = int(eval(input()))
    ans = main(N)
    print((ans if ans > 0 else ':('))


# Optimized solution
def main(N, rate=1.08):
    X = int(-(-N // 1.08))
    return X if int(X * rate) == N else -1


if __name__ == "__main__":
    N = int(eval(input()))
    ans = main(N)
    print((ans if ans > 0 else ':('))
# Original solution
n=int(eval(input()))
for i in range(1,n+1):
    if int(i*1.08) == n:
        print(i)
        exit()

print(':(')

# Optimized solution
n=int(eval(input()))
for i in range(n+1):
    if int(i*1.08) == n:
        print(i)
        exit()
print(':(')
# Original solution
def main():
    from math import floor
    N = int(input())
    for i in range(50000):
        if floor(i*1.08) == N:
            return print(i)
    else:
        print(":(")


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    from math import ceil, floor
    N = int(eval(input()))
    X = ceil(N/1.08)
    if floor(X*1.08) == N:
        print(X)
    else:
        print(":(")


if __name__ == '__main__':
    main()
# Original solution
def main():
    n = int(eval(input()))

    for i in range(1, 50000):
        if i * 108 // 100 == n:
            print(i)
            break
    else:
        print(":(")


if __name__ == "__main__":
    main()


# Optimized solution
from math import ceil


def main():
    n = int(eval(input()))

    min_value = n * 100 / 108
    max_value = (n + 1) * 100 / 108

    candidate = ceil(min_value)

    if candidate < max_value:
        print(candidate)
    else:
        print(":(")


if __name__ == "__main__":
    main()
# Original solution
N=int(eval(input()))
ans = -1

for i in range(50000+10):
 x1 = int(i*1.08)
 x2 = i*1.08
 #print(i,x1,x2)
 if(x1 == N): ans = i
 elif(x2 == N): ans = i
  
  
if(ans == -1):
 print(':(')
else:
 print(ans)

# Optimized solution
N = int(eval(input()))

ans = -1
for x in range(N+1):
  if(int(x*1.08) == N):
    ans = x
    break
    
if(ans == -1): print(':(')
else: print(ans)
# Original solution
# sumitb2019_b_bacha.py
N = int(eval(input()))
for i in range(10000000):
    if int(i*1.08) == N:
        print(i)
        exit()
print(":(")




# Optimized solution
# sumitb2019_b_bacha.py
N = int(eval(input()))
for i in range(50000):
    if int(i*1.08) == N:
        print(i)
        exit()
print(":(")
# Original solution
import math

n=int(eval(input()))

for i in range(1,50001):
    if math.floor(i*1.08)==n:
        print(i)
        exit()
print(":(")



# Optimized solution
n=int(eval(input()))

if int(n//1.08) !=int((n+1)//1.08):
      print((int((n+1)//1.08)))
else:
      print(':(')
# Original solution
n=int(eval(input()));print((([m for m in range(n+1)if int(m*1.08)==n]+[':('])[0]))

# Optimized solution
n=int(eval(input()))+1;print((n%27%14and int(n/1.08)or':('))
# Original solution
import math

n = int(eval(input()))

for i in range(1, 50001):
    if i * 1.08 == n or math.floor(i*1.08) == n:
        print(i)
        exit()

print(":(")

# Optimized solution
import math

n = int(eval(input()))

for price in range(1, 50001):
    if math.floor(price*1.08) == n:
        print(price)
        exit()
print(":(")
# Original solution
N = int(eval(input()))
import math

for x in range(900000 + 1):
    if math.floor(x * 1.08) == N:
        print(x)
        break
else:
    print(':(')

# Optimized solution
N = int(eval(input()))
import math

x = math.ceil(N / 1.08)
print((str(x) if math.floor(x * 1.08) == N else ':('))
# Original solution
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod
 
n=int(eval(input()))
mod=998244353

g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

a=0
b=1
for i in range(n,n//2,-1):
  a+=cmb(n,i,mod)*b
  a%=mod
  b*=2
  b%=mod
ans=(pow(3,n,mod)-2*a)%mod
print(((ans+mod)%mod))

# Optimized solution
n=int(eval(input()));l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n//2+1):
 l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):
 a+=b*c%p;b=2*b%p;c=c*i*l[n+1-i]%p
print(((pow(3,n,p)-2*a+p)%p))
# Original solution
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(eval(input()))
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * pow(2, i, MOD)
    impossible = (impossible + 2 * tmp) % MOD
print(((ans - impossible) % MOD))


# Optimized solution
def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


n = int(eval(input()))
MOD = 998244353
fn, invs = prepare(n, MOD)
ans = pow(3, n, MOD)
impossible = 0
mul = 2
for i in range(n // 2):
    tmp = fn * invs[i] * invs[n - i] % MOD * mul
    impossible = (impossible + tmp) % MOD
    mul = mul * 2 % MOD
print(((ans - impossible) % MOD))
# Original solution
#解説参照
#言い換えが困難

n=int(eval(input()))
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

def ch(a,b):
    return f[a]*finv[a-b]*finv[b]
k=n//2
if k*2<=n:
    k+=1

for i in range(k,n+1):
    ans -= ch(n,i)*pow(2,n-i+1,mod)
print((ans%mod))
    



# Optimized solution
n=int(eval(input()))
mod=998244353

ans=pow(3,n,mod)
rmv=0
f = [1, 1]  
inv = [1, 1]  
finv=[1,1]
for i in range(2, n+1):
    f.append((f[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    finv.append(finv[-1]*inv[-1]%mod)

k=n//2
if k*2<=n:
    k+=1
tmp=pow(2,n-k+1,mod)
inv2=pow(2,mod-2,mod)
for i in range(k,n+1):
    ans -= f[n]*finv[n-i]*finv[i]*tmp
    tmp*=inv2
    tmp%=mod
print((ans%mod))
# Original solution
N=int(eval(input()))
mod=998244353
Combi=1
SC=0
for i in range(N,N//2,-1):
    SC=(SC+Combi*pow(2,N-i,mod))%mod
    Combi=Combi*(i)*pow(N-i+1,mod-2,mod)%mod
print(((pow(3,N,mod)-SC*2)%mod))

# Optimized solution
N=int(eval(input()))
mod=998244353

FACT=[1]
for i in range(1,N+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(N,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

POW=[1]
for i in range(N):
    POW.append(POW[-1]*2%mod)

def Combi(a,b):
    return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod

SC=0
for i in range(N//2+1,N+1):
    SC+=Combi(N,i)*POW[N-i]

print(((pow(3,N,mod)-SC*2)%mod))
# Original solution
N = int(eval(input()))

nn = N + 10
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0

ans = pow(3, N, P)
for i in range(N//2 + 1, N + 1):
    ans = (ans - 2 * C(N, i) * pow(2, N - i, P)) % P

print(ans)

# Optimized solution
N = int(eval(input()))

nn = N + 10
P = 998244353

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
C = lambda a, b: fa[a] * fainv[b] % P * fainv[a-b] % P if 0 <= b <= a else 0

ans = pow(3, N, P)
p2 = 2
for i in range(N, N // 2, -1):
    ans = (ans - C(N, i) * p2) % P
    p2 = p2 * 2 % P

print(ans)