Problem:
 Score : 800 points    Problem Statement Given is a positive even number N .  Find the number of strings s of length N consisting of A , B , and C that satisfy the following condition:   s can be converted to the empty string by repeating the following operation:  Choose two consecutive characters in s and erase them. However, choosing AB or BA is not allowed.     For example, ABBC satisfies the condition for N=4 , because we can convert it as follows: ABBC → (erase BB ) → AC → (erase AC ) → (empty) .  The answer can be enormous, so compute the count modulo 998244353 .      Constraints  2 \leq N \leq 10^7  N is an even number.         Input Input is given from Standard Input in the following format:  N       Output Print the number of strings that satisfy the conditions, modulo 998244353 .        Sample Input 1 2      Sample Output 1 7  Except AB and BA , all possible strings satisfy the conditions.       Sample Input 2 10      Sample Output 2 50007       Sample Input 3 1000000      Sample Output 3 210055358

Solution (Python):
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-p//i)%p]
for i in range(n,n//2,-1):a+=b*c;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Solution (Python):
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-p//i)%p]
for i in range(n,n//2,-1):a+=b*c;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Solution (Python):
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-p//i)%p]
for i in range(n,n//2,-1):a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Solution (Python):
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Solution (Python):
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):
 l+=[l[p%i]*(p-int(p/i))%p]
for i in range(n,n//2,-1):
 a+=b*c%p;b+=b%p;c=c*i*l[n+1-i]%p
print((pow(3,n,p)-2*a)%p)

Solution (Python):
N = int(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)

Solution (Python):
N = int(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)

Solution (Python):
n=int(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)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

N = int(read())

import numpy as np

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**7 + 10
fact, fact_inv = make_fact(U,MOD)

x = np.full(U,2,dtype=np.int64); x[0] = 1
pow2 = cumprod(x,MOD)

n = N//2
comb = fact_inv[:n] * fact_inv[N:N-n:-1] % MOD * fact[N] % MOD

x = (comb * pow2[:n] % MOD).sum()
answer = pow(3,N,MOD) - x - x
answer %= MOD
print(answer)

Solution (Python):
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):
 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)

Solution (Python):
n=int(input());l=[0,1];a=0;b=c=1;p=998244353
for i in range(2,n):
 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)

Solution (Python):
n=int(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)

Solution (Python):
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(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)

Solution (Python):
def calc(n, mod):
	f = 1
	fac = [1]
	for i in range(1, n + 1):
		f *= i
		f %= mod
		fac.append(f)
	inv = pow(f, mod - 2, mod)
	invs = [1] * (n + 1)
	invs[n] = inv
	for i in range(n, 1, -1):
		inv *= i
		inv %= mod
		invs[i - 1] = inv
	return fac, invs

def cnk(n, r, mod, fac, inv):
	return fac[n] * inv[n - r] * inv[r] % mod


n = int(input())

mod = 998244353

f, inv = calc(n + 10, mod)
ans = pow(3, n, mod)
p = [1]

for i in range(n // 2 + 10):
	p.append(p[-1] * 2 % mod)
for k in range(n // 2 + 1, n + 1):
	cur = 2 * cnk(n, k, mod, f, inv) * p[n - k]
	ans -= cur
	ans %= mod
print(ans)

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc040/tasks/agc040_c

奇数文字目と偶数文字目がセットで消える
奇数文字目のABを反転すると、AB or BA or AC or BC or CC で消えていいことになる

すなわち、異なる文字の切れ目では必ず消せる
異なる切れ目は必ず存在するので、Cを適当にABに割り振った時に全て消せるかどうかが問題になる

A,Bのみの時に全て消せる条件は 両者の数が等しい事
Cを適切に割り振った時に両者の数を等しくできる必要十分条件は max(a,b) <= N//2
あとはこれを数えればよい→どうやって？

全ての並び方は 3**N　ここから補集合を引く？
Aが半数を超える(k個)の時のおき方は、 NCk * (2**(N-k))で求まる
Bの時も同様に。

"""

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(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 factorials, invs


def modnCr(n,r,mod,fac,inv):
    return fac[n] * inv[n-r] * inv[r] % mod


N = int(input())
mod = 998244353

fac,inv = modfac(N+10,mod)
ans = pow(3,N,mod)

tpow = [1]
for i in range(N//2+10):
    tpow.append(tpow[-1]*2%mod)

for k in range(N//2+1,N+1):

    now = 2 * modnCr(N,k,mod,fac,inv) * tpow[N-k]
    ans -= now
    ans %= mod

print (ans)

Solution (Python):
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

MOD = 998244353
N = int(input())

n = N // 2
ansx = 1
tmp2 = 1
tmpc = 1
for i in range(1, n):
    tmp2 = (tmp2 * 2)%MOD
    tmpc = (tmpc * (2 * n - i + 1) * modinv(i, MOD)) % MOD
    ansx = (ansx + tmp2 * tmpc)%MOD

ans = pow(3, N, MOD)
ans = (ans + 2 * MOD - ansx * 2)%MOD
print(ans)

Solution (Python):
MOD = 998244353

N = int(input())

ans = pow(3, N, MOD)

def getInvs(n, MOD):
    invs = [1] * (n+1)
    for x in range(2, n+1):
        invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
    return invs

def getCombNs(n, invs, MOD):
    combNs = [1] * (n//2+1)
    for x in range(1, n//2+1):
        combNs[x] = (combNs[x-1] * (n-x+1) * invs[x]) % MOD
    return combNs + combNs[:(n+1)//2][::-1]

invs = getInvs(N, MOD)
combNs = getCombNs(N, invs, MOD)

pow2 = 1
for i in range((N-1)//2+1):
    num = combNs[i] * pow2
    ans -= num*2 % MOD
    ans %= MOD
    pow2 *= 2
    pow2 %= MOD

print(ans)

Solution (Python):
LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    factorial_n = 1
    factorial_inv = [0] * (n + 1)
    factorial_inv[0] = 1
    for i in range(1, n + 1):
        factorial_n *= i
        factorial_n %= LARGE
    factorial_inv[-1] = pow(factorial_n, LARGE - 2, LARGE)
    for i in range(n):
        factorial_inv[n - i - 1] = (factorial_inv[n - i] * (n - i)) % LARGE
    pow_2 = 1
    for k in range(n // 2):
        r += factorial_n * factorial_inv[n - k] * factorial_inv[k] * pow_2
        r %= LARGE
        pow_2 *= 2
        pow_2 %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    


if __name__ == "__main__":
    test()
    main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

N = int(read())

import numpy as np

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**7 + 10
fact, fact_inv = make_fact(U,MOD)

x = np.full(U,2,dtype=np.int64); x[0] = 1
pow2 = cumprod(x,MOD)

n = N//2
comb = fact_inv[:n] * fact_inv[N:N-n:-1] % MOD * fact[N] % MOD

x = (comb * pow2[:n] % MOD).sum()
answer = pow(3,N,MOD) - x - x
answer %= MOD
print(answer)

Solution (Python):
import itertools
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N = int(sys.stdin.readline())


@lru_cache(maxsize=None)

def is_ok(s):
    if len(s) == 0:
        return True
    if len(s) == 2:
        return s not in ['AB', 'BA']
    for i in range(len(s) - 2):
        if s[i:i + 2] not in ['AB', 'BA'] and is_ok(s[:i] + s[i + 2:]):
            return True
    return False


def test(N):
    ret = 0
    for s in itertools.product('ABC', repeat=N):
        s = ''.join(s)
        ret += is_ok(s)
    return ret


def mod_invs(max, mod):
    """
    逆元のリスト 0 から max まで
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs








ans = pow(3, N, MOD)

invs = mod_invs(max=N, mod=MOD)
ncr = 1  
p2r = 1  
for r in range(N, N // 2, -1):
    
    ans -= ncr * p2r * 2 % MOD
    ans %= MOD
    ncr *= r * invs[N - r + 1]
    ncr %= MOD
    p2r *= 2
    p2r %= MOD
print(ans)

Solution (Python):
N=int(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)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD

fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)

Solution (Python):

n=int(input())
pre=[1]*(n//2+200)
pp=[1]*(n+1)
mod=998244353
for i in range(1,n//2+100):
    pre[i]=((pre[i-1]*2)%mod)
    
p=[1]*(n+1)
for i in range(n):
    p[i+1]=((p[i]*(i+1))%mod)
pp[-1] = pow(p[-1], mod - 2, mod)
 
for i in range(2, n + 1):
	pp[-i] = int((pp[-i + 1] * (n + 2 - i)) % mod)
tot=1
for i in range(n):
    tot*=3
    tot%=mod


cc=0
for i in range(n//2+1,n+1):
    c=(((((p[n]*pp[i])%mod)*pp[n-i])%mod)*pre[n-i])%mod
    c%=mod
    cc+=c
tot-=cc
tot-=cc
tot%=mod
print(tot)

Solution (Python):
N = int(input())
MOD = 998244353

list_size = 10000010

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)


def comb(n,r):
    if r == 0:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

ans = 0
for i in range((N//2)):
    ans += comb(N,i) * pow(2,i,MOD)
    ans %= MOD

print((pow(3,N,MOD)-ans*2)%MOD)

Solution (Python):
N = int(input())
MOD = 998244353

list_size = 10000010

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)


def conv(n,r):
    if r == 0:
        return 1
    return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

ans = 0
for i in range((N//2)):
    ans += conv(N,i) * pow(2,i,MOD)
    ans %= MOD

print((pow(3,N,MOD)-ans*2)%MOD)

Solution (Python):
MOD = 998244353
list_size = 10000010

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n = int(input())
sub = 0
for i in range(n//2+1, n+1):
	sub += comb(n, i) * pow(2, n-i, MOD)
	sub %= MOD
print((pow(3, n, MOD) - 2 * sub) % MOD)

Solution (Python):

def main():
    mod=998244353
    n=int(input())
    Fact=[1] 
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) 
    Finv[-1]=pow(Fact[-1],mod-2,mod)
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    def comb(n,r):
        if n<r:
            return 0
        return Fact[n]*Finv[r]*Finv[n-r]%mod
    
    impossible=0
    m=1
    for k in range(n//2):
        impossible+=comb(n,k)*m%mod
        impossible%=mod
        m*=2
        m%=mod
    print((pow(3,n,mod)-impossible*2)%mod)

if __name__=='__main__':
    main()

Solution (Python):
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(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)