Kuro and Shiro are playing with a board composed of n squares lining up in a row.
The squares are numbered 1 to n from left to right, and Square s has a mark on it.
First, for each square, Kuro paints it black or white with equal probability, independently from other squares. Then, he puts on Square s a stone of the same color as the square.
Kuro and Shiro will play a game using this board and infinitely many black stones and white stones. In this game, Kuro and Shiro alternately put a stone as follows, with Kuro going first:
 - Choose an empty square adjacent to a square with a stone on it. Let us say Square i is chosen.
 - Put on Square i a stone of the same color as the square.
 - If there are squares other than Square i that contain a stone of the same color as the stone just placed, among such squares, let Square j be the one nearest to Square i. Change the color of every stone between Square i and Square j to the color of Square i.
The game ends when the board has no empty square.
Kuro plays optimally to maximize the number of black stones at the end of the game, while Shiro plays optimally to maximize the number of white stones at the end of the game.
For each of the cases s=1,\dots,n, find the expected value, modulo 998244353, of the number of black stones at the end of the game.

-----Notes-----
When the expected value in question is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq=p ~(\text{mod } 998244353) and 0 \leq r \lt 998244353, which we ask you to find.

-----Constraints-----
 - 1 \leq n \leq 2\times 10^5

-----Input-----
Input is given from Standard Input in the following format:
n

-----Output-----
Print n values.
The i-th value should be the expected value, modulo 998244353, of the number of black stones at the end of the game for the case s=i.

-----Sample Input-----
3

-----Sample Output-----
499122178
499122178
499122178

Let us use b to represent a black square and w to represent a white square.
There are eight possible boards: www, wwb, wbw, wbb, bww, bwb, bbw, and bbb, which are chosen with equal probability.
For each of these boards, there will be 0, 1, 0, 2, 1, 3, 2, and 3 black stones at the end of the game, respectively, regardless of the value of s.
Thus, the expected number of stones is (0+1+0+2+1+3+2+3)/8 = 3/2, and the answer is r = 499122178, which satisfies 2r = 3 ~(\text{mod } 998244353) and 0 \leq r \lt 998244353.

Difficulty: competition

Starter code:

Solutions:
N=int(input())
mod=998244353
inv4=249561088
A=[inv4,0,3]
for i in range(N):
    A.append(9*A[-1]-24*A[-2]+16*A[-3])
    A[-1]%=mod
A[0]-=inv4
B=[0 for i in range(N)]
for i in range(N):
    x=i
    y=N-i-1
    if x<=y:
        B[x]=A[i]
        B[y]=A[i]

P=N*pow(2,N-2+mod-1,mod)
for i in range(N):
    B[i]+=P
    B[i]%=mod
Q=pow(2,N-1,mod)
Qinv=pow(Q,mod-2,mod)
for i in range(N):
    B[i]*=Qinv
    B[i]%=mod
for i in range(N):
    print((B[i]))


A=[1,6]
N=int(input())
mod=998244353
for i in range(N+2):
  A.append((4*A[-1]+pow(4,i+2,mod))%mod)
B=[N*pow(2,N-1,mod)%mod]
A[0]=0
for i in range((N-1)//2):
  B.append(B[i]+A[i])
if N&1:
  for i in range((N-1)//2):
    B.append(B[-i*2-2])
else:
  for i in range((N-1)//2+1):
    B.append(B[-i*2-1])
for i in range(N):
  B[i]=B[i]*pow(2,(mod-2)*N,mod)%mod
print(*B,sep='\n')

M=998244353
a=range(N:=int(input()))
C=M+1>>1
p=[N*C]*N*3
for i in a:p[i+2]=p[i+1]+pow(2,2*i+1-N,M)*(2*i+3);print(p[min(i,N-1-i)]%M)

Q=998244353
N=int(input())
a=range(N)
C=(Q+1)//2
p=[N*C]*N*3
q=[1]*N*2
for i in a:q[i+1]=(q[i]*C)%Q
for i in a:p[i+2]=p[i+1]+q[N-2*i-1]*(2*i+3);print(p[min(i,N-1-i)]%Q)

MOD = 998244353
N = int(input())
if N == 1:
  print((1 * pow(2, MOD - 2, MOD)))
  return
if N == 2:
  print((1))
  print((1))
  return

ans = pow(2, N - 2, MOD) * N % MOD
q = pow(pow(2, N, MOD), MOD - 2, MOD)
for i in range(1, N):
  if i == 1:
    ans += 1
  else:
    ans = (ans + i * pow(2, i - 2, MOD) % MOD) % MOD 
for i in range(1, N):
  if i == N - 1:
    ans += N - 1
  else:
    ans = (ans + i * pow(2, N - 2 - i, MOD) % MOD) % MOD

t = ans * q % MOD
L = [t, t]
for i in range(2, (N + 1) // 2):
  ans = (ans + (i * 2 - 1) * pow(2, (i - 1) * 2 - 1, MOD) % MOD) % MOD
  L.append(ans * q % MOD)

for i in L:
  print(i)
L.reverse()
if N % 2 == 0:
  t = 0
else:
  t = 1
for i in L[t:]:
  print(i)


N = int(input())
MOD = 998244353

arr = [(pow(2,N-1,MOD) * N) % MOD] * 2
b,a = 2,3
while len(arr) <= N//2:
    arr.append((arr[-1] + b*a)%MOD)
    b *= 4
    b %= MOD
    a += 2

inv = pow(2,-N,MOD)
if N <= 2:
    for a in arr[:N]:
        print((a * inv) % MOD)
    return

if N%2==0: arr.pop()

for a in arr:
    print((a * inv) % MOD)

if N%2: arr.pop()
for a in arr[::-1]:
    print((a * inv) % MOD)

mod = 998244353

n = int(input())
half = 499122177 * n % mod
d = pow(2, mod - n, mod)
h = (n + 1) // 2
ans = [half] * h
for i in range(h - 2):
    ans[i + 2] = ans[i + 1] + (2 * i + 3) * d
    ans[i + 2] %= mod
    d *= 4
    d %= mod
for i in range(h):
    print((ans[i]))
if n % 2 == 0:
    print((ans[-1]))
for i in range(2, h + 1):
    print((ans[-i]))


M=998244353
a=range(N:=int(input()))
p=[-~M//2*N]*N*3
for i in a:p[i+2]=p[i+1]+pow(2,2*i+1-N,M)*(2*i+3);print(p[min(i,N-1-i)]%M)

n = int(input())
MOD = 998244353
tmp = n * 2 ** (n - 2) % MOD
if n == 1:
    print(pow(2, MOD - 2, MOD))
    return
elif n == 2:
    print(1)
    print(1)
    return
ans = [tmp, tmp]
bi = 1

for i in range(2, (n + 1) // 2):
    tmp = ans[-1] + (2 * i - 1) * bi
    bi *= 4
    ans.append(tmp % MOD)
    bi %= MOD
inv = pow(2 ** (n - 1), MOD - 2, MOD)
for a in ans:
    print(a * inv % MOD)
if n % 2 == 1:
    for n in ans[:-1][::-1]:
        print(n * inv % MOD)
else:
    for n in ans[::-1]:
        print(n * inv % MOD)

n = int(input())
MOD = 998244353

if n == 1:
    print((pow(2, MOD - 2, MOD)))
    return

if n == 2:
    print((1))
    print((1))
    return

div = pow(pow(2, n - 1, MOD), MOD - 2, MOD)
num = n * pow(2, n - 2, MOD) % MOD
a = 1
b = 3
buf = [div * num % MOD] * 2
for i in range((n + 1) // 2 - 2):
    num = (num + a * b) % MOD
    buf.append(div * num % MOD)
    a = a * 4 % MOD
    b = (b + 2) % MOD
if n % 2 == 0:
    buf.extend(list(reversed(buf)))
else:
    buf.extend(list(reversed(buf[:-1])))

print(('\n'.join(map(str, buf))))


M=998244353
N=int(input())
p=[-~M//2*N]*N*3
for i in range(N):p[i+2]=p[i+1]+pow(2,2*i+1-N,M)*(2*i+3);print(p[min(i,N-1-i)]%M)

P = 998244353
N = int(input())
i2 = pow(2, P - 2, P)
iv = pow(i2, N - 1, P)
s = 0
t = 1
ANS = [i2 * N % P] * (1 if N <= 2 else 2)
for i in range(2, (N + 1) // 2):
    a = (i * 2 - 1) * t % P
    s = (s + a) % P
    ANS.append((i2 * N + s * iv) % P)
    t = t * 4 % P
for i in range(N // 2):
    ANS.append(ANS[N//2-i-1])
print("\n".join(map(str, ANS)))

mo = 998244353

n = int(input())

if n == 1:
    print(pow(2, mo - 2, mo))
    return

def calc(n, s):
    nonlocal bans, qa
    return (bans + qa(2, min(n - 2, 2 * n - 1 - 2 * s, 2 * s - 2))) % mo

a = [0] * n

for k in range(3, n - 1, 2):
    a[k] = k * pow(2, k - 2, mo) % mo

for k in range(1, n):
    a[k] += a[k - 1]

def qa(l, r):
    if l > r:
        return 0
    return a[r] - a[l - 1]

bans = 0
bans = (bans + pow(2, n - 2, mo) * n) % mo
for i in range(1, n):
    bans = (bans + 2 * i) % mo
tmp = 0
for k in range(2, n - 1):
    tmp = (tmp + pow(2, n - k - 2, mo) * (k - 1)) % mo
bans = (bans + tmp * n) % mo

dom = pow(2, -n + mo - 1, mo)

for s in range(1, n + 1):
    print(calc(n, s) * dom % mo)

N=int(input())
mod=998244353
inv4=249561088
A=[inv4,0,3]
for i in range(N):
    A.append(9*A[-1]-24*A[-2]+16*A[-3])
    A[-1]%=mod
A[0]-=inv4
B=[0 for i in range(N)]
for i in range(N):
    x=i
    y=N-i-1
    if x<=y:
        B[x]=A[i]
        B[y]=A[i]
P=N*pow(2,N-2,mod)
for i in range(N):
    B[i]+=P
    B[i]%=mod
Q=pow(2,N-1,mod)
Qinv=pow(Q,mod-2,mod)
for i in range(N):
    B[i]*=Qinv
    B[i]%=mod
for i in range(N):
    print((B[i]))


mod=998244353
n=int(input())
a=[0,6,40]
if n==1:
  print(pow(2,-1,mod))
  return
if n==3:
  print(499122178)
  print(499122178)
  print(499122178)
  return
for i in range((n//2)+1):
  a.append((a[-1]*8-a[-2]*16)%mod)
if n%2==0:
  s=pow(2,n,mod)
  p=pow(s,-1,mod)
  c=n//2
  k=(c)%mod
  print(k)
  L=[k]
  k=(s*k)%mod
  q=n//2
  for i in range((n//2)-1):
    k+=a[i]
    po=(k*p)%mod
    L.append(po)
    print(po)
  for i in range(q):
    print(L[q-i-1])
else:
  s=pow(2,n,mod)
  p=pow(s,-1,mod)
  
  k=(n*pow(2,-1,mod))%mod
  print(k)
  L=[k]
  k=(s*k)%mod
  q=n//2
  for i in range((n//2)-1):
    k+=a[i]
    po=(k*p)%mod
    L.append(po)
    print(po)
  k+=a[i+1]
  po=(k*p)%mod
  print(po)
  for i in range(q):
    print(L[q-i-1])

Q=998244353
N=int(input())
a=range(N)
C=-~Q//2
p=[N*C]*N*3
q=[1]*N*2
for i in a:q[i+1]=(q[i]*C)%Q
for i in a:p[i+2]=p[i+1]+q[N-2*i-1]*(2*i+3);print(p[min(i,N-1-i)]%Q)

Q=998244353
N=int(input())
a=range(N)
C=(Q+1)//2
p=[N*C]*N*3
q=[1]*N*2
for i in a:q[i+1]=(q[i]*C)%Q
for i in a:p[i+2]=(p[i+1]+q[N-2*i-1]*(2*i+3))%Q;print(p[min(i,N-1-i)]%Q)


"""

https://atcoder.jp/contests/arc109/tasks/arc109_e

同色連続をブロックとして考える
3ブロック以上になることはない
[証明]
2ブロック以下とする。
同色側に置くと何も変わらない。異色側に置くと2ブロックになるか、1ブロックになる

端が同じ色なら、全てその色になる→よって期待値は半分

端が違う色の時を考える
WWB?????S?????WBBB
端の自分の色のブロックに先に到達した方が端以外を総取りできる

距離が同じときのみ黒が勝てる
→これだけ考えればよい

sの位置が決まる
sから端ブロックまでの距離がxの時の通り数は

WWB????S????WBBBB

2*pow(2,2x-3)
である

取れるBの個数は、両側を同時に加味すると
n+2x-1

よって (n+2x-1)*pow(2,2x-3)
を計算していけばよい

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

mod = 998244353
half = 499122177
n = int(input())
inv = inverse(pow(2,n,mod),mod)

cnum  = 0
black = 0
ans = [0] * n

for s in range(n):

    if s * 2 < n:

        if s >= 2:
            cnum  += 2*pow(2,2*s-3,mod)
            black += (n+2*s-1)*pow(2,2*s-3,mod)
        ans[s] = ((pow(2,n,mod)-cnum)*n*half + black)*inv % mod
        print (ans[s])

    else:
        print (ans[n-1-s])

n = int(input())
MOD = 998244353
i2 = (MOD + 1) // 2

pi2 = [1]
for i in range(n):
    pi2.append((pi2[-1] * i2) % MOD)

ans = []
sum = n * i2 % MOD
for i in range((n + 1) // 2):
    if i >= 2:
        sum = (sum + pi2[n - 2 * i + 3] * (2 * i - 1)) % MOD
    ans.append(sum)

for i in range(n):
    print((ans[min(i, n - 1 - i)]))


import sys
input = sys.stdin.readline
n = int(input())

mod = 998244353
now = n * pow(2, n - 1, mod)
k = pow(2, n, mod)
k = pow(k, mod - 2, mod)
if n == 1:
    print(now * k % mod)
elif n == 2:
    print(now * k % mod)
    print(now * k % mod)
elif n == 3:
    print(now * k % mod)
    print(now * k % mod)
    print(now * k % mod)
else:
    ans = []
    ans.append(now * k % mod)
    ans.append(now * k % mod)
    for i in range(2, n // 2):
        now += (2 * i - 1) * pow(2, (2 * i - 3), mod)
        ans.append(now * k % mod)
    sna = list(reversed(ans))
    if n % 2 == 1:
        i = n // 2
        now += (2 * i - 1) * pow(2, (2 * i - 3), mod)
        ans.append(now * k % mod)
    print(*(ans + sna), sep="\n")