There are $n + 2$ towns located on a coordinate line, numbered from $0$ to $n + 1$. The $i$-th town is located at the point $i$.

You build a radio tower in each of the towns $1, 2, \dots, n$ with probability $\frac{1}{2}$ (these events are independent). After that, you want to set the signal power on each tower to some integer from $1$ to $n$ (signal powers are not necessarily the same, but also not necessarily different). The signal from a tower located in a town $i$ with signal power $p$ reaches every city $c$ such that $|c - i| < p$.

After building the towers, you want to choose signal powers in such a way that:

towns $0$ and $n + 1$ don't get any signal from the radio towers;

towns $1, 2, \dots, n$ get signal from exactly one radio tower each.

For example, if $n = 5$, and you have built the towers in towns $2$, $4$ and $5$, you may set the signal power of the tower in town $2$ to $2$, and the signal power of the towers in towns $4$ and $5$ to $1$. That way, towns $0$ and $n + 1$ don't get the signal from any tower, towns $1$, $2$ and $3$ get the signal from the tower in town $2$, town $4$ gets the signal from the tower in town $4$, and town $5$ gets the signal from the tower in town $5$.

Calculate the probability that, after building the towers, you will have a way to set signal powers to meet all constraints.


-----Input-----

The first (and only) line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).


-----Output-----

Print one integer — the probability that there will be a way to set signal powers so that all constraints are met, taken modulo $998244353$.

Formally, the probability can be expressed as an irreducible fraction $\frac{x}{y}$. You have to print the value of $x \cdot y^{-1} mod 998244353$, where $y^{-1}$ is an integer such that $y \cdot y^{-1} mod 998244353 = 1$.


-----Examples-----

Input
2
Output
748683265
Input
3
Output
748683265
Input
5
Output
842268673
Input
200000
Output
202370013


-----Note-----

The real answer for the first example is $\frac{1}{4}$:

with probability $\frac{1}{4}$, the towers are built in both towns $1$ and $2$, so we can set their signal powers to $1$.

The real answer for the second example is $\frac{1}{4}$:

with probability $\frac{1}{8}$, the towers are built in towns $1$, $2$ and $3$, so we can set their signal powers to $1$;

with probability $\frac{1}{8}$, only one tower in town $2$ is built, and we can set its signal power to $2$.

The real answer for the third example is $\frac{5}{32}$. Note that even though the previous explanations used equal signal powers for all towers, it is not necessarily so. For example, if $n = 5$ and the towers are built in towns $2$, $4$ and $5$, you may set the signal power of the tower in town $2$ to $2$, and the signal power of the towers in towns $4$ and $5$ to $1$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Combinatorics

Mathematics


Solutions:
import sys
import math

def II():
	return int(sys.stdin.readline())

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

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()

def FACT(n, mod):
	s = 1
	facts = [1]
	for i in range(1, n + 1):
		s *= i
		s %= mod
		facts.append(s)
	return facts[n]

def C(n, k, mod):
	return FACT(n, mod) * pow(FACT(k, mod) * FACT(n - k, mod) % mod, mod - 2, mod) % mod
n = II()
mod = 998244353
dp = [1, 1, 1]
for i in range(2, n):
	dp.append((dp[-1] + dp[-2]) % mod)
ans = dp[-1]
print(ans * pow(pow(2, n, mod), mod - 2, mod) % mod)


def fib(n):
	f = [1, 1]
	for i in range(2, n):
		f.append(add(f[i - 1], f[i - 2]))
	return f[n - 1]

def mul(a, b):
	return a * b % 998244353

def add(a, b):
	a += b
	while a >= 998244353:
		a -= 998244353
	while a < 0:
		a += 998244353
	return a

def binpow(a, n):
	ans = 1
	while n > 0:
		if n % 2:
			ans = mul(ans, a)
		a = mul(a, a)
		n //= 2
	return ans
n = int(input())
ans = fib(n)
k = binpow(2, n)
a = binpow(k, 998244351) % 998244353
print(mul(ans, a))


def fibonacci(n, m):
	if n < 2:
		return n
	a = 0
	b = 1
	for i in range(n - 1):
		c = b
		b = (a + b) % m
		a = c
	return b

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

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

def pow(a, b, m):
	if b < 0:
		raise Exception('bad')
	ret = 1
	for i in range(b):
		ret *= a
		ret %= m
	return ret
inp = int(input())
p = 998244353
print(fibonacci(inp, p) * modinv(pow(2, inp, p), p) % p)


import sys
input = sys.stdin.readline
from collections import *
n = int(input())
(e, o) = (1, 0)
MOD = 998244353
for i in range(n):
	if i % 2 == 0:
		dp = e
		o += dp
		o %= MOD
	else:
		dp = o
		e += dp
		e %= MOD
print(dp * pow(pow(2, n, MOD), MOD - 2, MOD) % MOD)


M = 998244353
n = int(input())
(a, b) = (1, 1)
for i in range(3, n + 1):
	(a, b) = (b, (a + b) % M)
print(b * pow(pow(2, n, M), M - 2, M) % M)


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
mod = 998244353
N = 2 * 10 ** 5
g1 = [1] * (N + 1)
g2 = [1] * (N + 1)
inverse = [1] * (N + 1)
for i in range(2, N + 1):
	g1[i] = g1[i - 1] * i % mod
	inverse[i] = -inverse[mod % i] * (mod // i) % mod
	g2[i] = g2[i - 1] * inverse[i] % mod
inverse[0] = 0
n = int(input())
res = 0
for k in range(1, n + 1):
	if (n - k) % 2 == 0:
		res += cmb((n - k) // 2 + k - 1, k - 1, mod)
		res %= mod
res *= pow(inverse[2], n, mod)
res %= mod
print(res)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
sys.setrecursionlimit(99999)
mod = 998244353
n = int(input())
(a, b) = (0, 1)
for i in range(2, n + 1):
	(a, b) = (b, (a + b) % mod)
print(b * pow(2, n * (mod - 2), mod) % mod)


def bp(b, p):
	if p == 1:
		return b
	if p % 2 == 0:
		t = bp(b, p // 2)
		return t * t % q
	else:
		return bp(b, p - 1) * b % q

def inv(x):
	return bp(x, q - 2)

def div(a, b):
	return a * inv(b) % q
n = int(input())
q = 998244353
dp = [0] * (n + 1)
dp[0] = dp[1] = 1
sm0 = 1
sm1 = 1
for i in range(2, n + 1):
	if i % 2 == 0:
		dp[i] = sm1
		sm0 += dp[i]
		sm0 %= q
	else:
		dp[i] = sm0
		sm1 += dp[i]
		sm1 %= q
print(div(dp[n], pow(2, n, q)))


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass
n = L()[0]
F = [0, 1]
while len(F) != n + 1:
	F.append((F[-1] + F[-2]) % mod2)
deno = pow(2, n, mod2)
deno = pow(deno, mod2 - 2, mod2)
print(F[-1] * deno % mod2)
endtime = time.time()


(n, jt) = (int(input()), 998244353)
ksmii = lambda a, b: ksmii(a, b >> 1) ** 2 * (a if b & 1 else 1) % jt if b else 1
fib = [0, 1, 1]
for i in range(n):
	fib.append((fib[-1] + fib[-2]) % jt)
print(fib[n] * ksmii(2, jt - n - 1) % jt)


def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
b = 1
g = [0] * (n + 1)
g[1] = 1
for j in range(2, n + 1):
	g[j] = (g[j - 1] + g[j - 2]) % 998244353
c = 0
k = g[n]
while k % 2 == 0:
	c = c + 1
	k = k // 2
for j in range(n - c):
	b = b * 2 % 998244353
print(k * modInverse(b, 998244353) % 998244353)


import sys
input = sys.stdin.readline
m = 998244353

def mI(x):
	y = m - 2
	p = pow(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def main():
	n = int(input())
	y = mI(pow(2, n))
	(a, b) = (1, 1)
	for i in range(n - 2):
		(a, b) = (b % m, (a + b) % m)
	x = b
	print(x * y % m)
main()


MOD = 998244353
n = int(input())
mult = pow(2, MOD - 1 - n, MOD)
(a, b) = (0, 1)
for i in range(n):
	(a, b) = (b, (a + b) % MOD)
print(a * mult % MOD)


from sys import stdin, stdout
input = stdin.readline
m = 998244353
t = 1
for _ in range(t):
	n = int(input())
	dp = [0 for x in range(n + 1)]
	dp[1] = 1
	for i in range(2, n + 1):
		dp[i] = (dp[i - 1] % m + dp[i - 2] % m) % m
	q = pow(2, n)
	ans = dp[-1] % m * pow(q, m - 2, m) % m
	print(ans)


n = int(input())
fib = [0, 1, 1]
total = [1, 2, 4]
MOD = 998244353
for i in range(3, n + 1):
	fib.append((fib[i - 1] + fib[i - 2]) % MOD)
	total.append(total[i - 1] * 2 % MOD)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
print(fib[n] * modInverse(total[n], MOD) % MOD)


lim = 2 * 10 ** 5 + 10
mod = 998244353
f = [1] * lim
for i in range(2, lim):
	f[i] = i * f[i - 1] % mod

def C(n, r):
	num = f[n]
	den = f[n - r] * f[r] % mod
	ans = num * pow(den, mod - 2, mod)
	return ans

def solve(n):
	(N, R) = (n // 2, 1)
	if n % 2:
		R -= 1
	ans = 0
	while N >= R:
		ans += C(N, R)
		ans %= mod
		N += 1
		R += 2
	ans = ans * pow(2, n * (mod - 2) % (mod - 1), mod) % mod
	return ans
n = int(input())
print(solve(n))


n = int(input())
mod = 998244353
(a, b) = (0, 1)
for i in range(n):
	(a, b) = (b, a + b)
	if b > mod:
		b %= mod
fib = a
y = pow(pow(2, n, mod), mod - 2, mod)
print(fib * y % mod)


n = int(input())
m = 998244353
d = [1] * (n + 1)
e = [1] * 2
c = 0
for i in range(2, n + 1):
	d[i] = d[i - 1]
	if i > 2:
		d[i] = (d[i] + e[(i + 1) % 2] - d[i - 1]) % m
	e[i % 2] = (e[i % 2] + d[i]) % m
x = d[-1]
y = pow(2, n, m)
print(x * pow(y, m - 2, m) % m)


n = int(input())

def fib(a):
	ans1 = 1
	ans2 = 1
	t = a
	while t > 0:
		t -= 1
		k = ans1
		ans1 += ans2
		ans2 = k
	return ans1

def binpow(a, b):
	if b == 0:
		return 1
	elif b % 2 == 1:
		return binpow(a, b - 1) * a % 998244353
	else:
		k = binpow(a, b / 2)
		return k * k % 998244353
m = 0
if n < 4:
	m = n - 1
else:
	m = fib(n - 2)
if n == 1:
	print(499122177)
else:
	l = binpow(2, n)
	ans = m * binpow(l, 998244351) % 998244353
	print(ans)


class mi:

	def __init__(self, val, mod=10 ** 9 + 7):
		self.val = val
		self.MOD = mod

	def __add__(self, other):
		if type(other) == int:
			other = mi(other % self.MOD, self.MOD)
		return mi((self.val + other.val) % self.MOD, self.MOD)

	def __sub__(self, other):
		if type(other) == int:
			other = mi(other % self.MOD, self.MOD)
		return mi((self.val - other.val) % self.MOD, self.MOD)

	def __mul__(self, other):
		if type(other) == int:
			other = mi(other % self.MOD, self.MOD)
		return mi(self.val * other.val % self.MOD, self.MOD)

	def __truediv__(self, other):
		if type(other) == int:
			other = mi(other % self.MOD, self.MOD)
		return mi(self.val * (other ** (self.MOD - 2)).val % self.MOD, self.MOD)

	def __pow__(self, b):
		if type(b) == mi:
			b = b.val
		b %= self.MOD
		a = mi(self.val, self.MOD)
		res = mi(1, self.MOD)
		while b:
			if b % 2:
				res *= a
			b //= 2
			a *= a
		return res

	def __repr__(self):
		return str(self.val)
n = int(input())
MOD = 998244353
fib = [mi(0, MOD), mi(1, MOD)]
for i in range(2, 200001):
	fib.append(fib[-1] + fib[-2])
print(fib[n] / mi(2, MOD) ** n)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from math import ceil, floor, sqrt, pow, factorial

def modInverse(a, m):
	g = gcd(a, m)
	return power1(a, m - 2, m)

def power1(x, y, m):
	if y == 0:
		return 1
	p = power1(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
n = N()
fi0 = 0
fi1 = 1
ans = 1
for i in range(2, n + 1):
	ans = fi0 + fi1
	fi0 = fi1
	fi1 = ans
x = ans
y = power(2, n, 998244353)
inv = modInverse(y, 998244353)
print(x * inv % 998244353)


import math
import sys
m = 998244353
input = sys.stdin.readline
fibo = [1, 1]
for i in range(200002):
	fibo.append(fibo[-1] + fibo[-2])
	fibo[-1] %= m
n = int(input())
deno = 1 << n
inv = pow(deno, m - 2, m)
ans = fibo[n - 1] * inv % m
print(ans)


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def solve():
	n = mint()
	dp = [1] * (n + 1)
	dp1 = [1] * (n + 1)
	MOD = 998244353
	for i in range(1, n + 1):
		dp[i] = dp1[i - 1]
		dp1[i] = (dp[i] + (dp1[i - 2] if i - 2 >= 0 else 0)) % MOD
	print(dp[n] * pow(2, (MOD - 2) * n, MOD) % MOD)
solve()


import sys
from collections import deque
from math import ceil, sqrt, gcd, factorial
from bisect import bisect_right, bisect_left
mod = 998244353
INF = 10 ** 18
NINF = -INF

def I():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def modi(x):
	return pow(x, mod - 2, mod)

def lcm(x, y):
	return x * y // gcd(x, y)

def write(l):
	for i in l:
		print(i, end=' ')
	print()
arr = [0, 1]
for i in range(200002):
	arr.append((arr[-1] + arr[-2]) % mod)
n = int(input())
iden = modi(pow(2, n, mod))
ans = arr[n] * iden % mod
print(ans)


mod = 998244353
n = int(input())
dp = [0] * 200010
sumdp = [0] * 200010
sumdp[0] = 1
for i in range(1, n + 1):
	dp[i] = sumdp[i - 1]
	sumdp[i] = (sumdp[i - 2] + dp[i]) % mod
ALL = pow(2, n, mod)
print(dp[n] * pow(ALL, mod - 2, mod) % mod)


n = int(input())
mod = 998244353
y = pow(2, n, mod)
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
	dp[i] = (dp[i - 1] + dp[i - 2]) % mod
ans = dp[n] * pow(y, mod - 2, mod) % mod
print(ans)


def fib(n):
	if n == 0:
		return 0
	if n == 1 or n == 2:
		return 1
	constn_1 = 1
	constn_2 = 1
	for i in range(3, n + 1):
		const = (constn_1 + constn_2) % 998244353
		constn_2 = constn_1 % 998244353
		constn_1 = const % 998244353
	return const % 998244353

def tower(n):
	x = fib(n)
	return x * pow(2 ** n, -1, 998244353) % 998244353
print(tower(int(input())))


import sys
import math
mod = 998244353
LI = lambda : [int(k) for k in input().split()]
input = lambda : sys.stdin.readline().rstrip()
IN = lambda : int(input())
S = lambda : input()
r = range
if 1:
	n = int(input())
	dp = [0] * (n + 1)
	dp[1] = 1
	for i in range(2, n + 1):
		dp[i] = (dp[i - 1] + dp[i - 2]) % mod
	den = pow(2, n, mod)
	deninv = pow(den, mod - 2, mod)
	print(dp[n] * deninv % mod)


m = 998244353
n = int(input())

def fib(n):
	F = [[1, 1], [1, 0]]
	if n == 0:
		return 0
	power(F, n - 1)
	return F[0][0]

def multiply(F, M):
	x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
	y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
	z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
	w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
	F[0][0] = x
	F[0][1] = y
	F[1][0] = z
	F[1][1] = w

def power(F, n):
	if n == 0 or n == 1:
		return
	M = [[1, 1], [1, 0]]
	power(F, n // 2)
	multiply(F, F)
	if n % 2 != 0:
		multiply(F, M)
numerator = fib(n) % m
denominator = pow(2, n) % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def modexp(x, n):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return modexp(x * x % m, n // 2)
	else:
		return x * modexp(x * x % m, (n - 1) / 2) % m

def getFractionModulo(a, b):
	c = gcd(a, b)
	a = a // c
	b = b // c
	d = modexp(b, m - 2)
	ans = a % m * (d % m) % m
	return ans
print(getFractionModulo(numerator % m, denominator % m))


def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m
n = int(input())
mod = 998244353
if n == 1 or n == 2:
	x = 1
else:
	a = 1
	b = 1
	for i in range(n - 2):
		c = (a + b) % mod
		a = b
		b = c
	x = c
y = power(pow(2, n, mod), mod - 2, mod)
print(x * y % mod)


import math
n = int(input())
dp = [0] * (2 * 10 ** 5 + 10)
dp[1] = 1
mod = 998244353
for i in range(2, n + 1):
	dp[i] = (dp[i - 1] + dp[i - 2]) % mod
po = pow(2, n, mod)
ans = dp[n] * pow(po, mod - 2, mod) % mod
print(ans)


from sys import stdin
n = int(stdin.readline())
M = 998244353

def fib(n):
	if n == 1:
		return 1
	elif n == 2:
		return 1
	else:
		(a, b) = (1, 1)
		for _ in range(n - 2):
			c = (a + b) % M
			a = b
			b = c
		return b % M
print(fib(n) * pow(pow(2, n), M - 2, M) % M)


p = 998244353

def multiply(a, b):
	mul = [[0 for i in range(2)] for j in range(2)]
	for i in range(2):
		for j in range(2):
			for k in range(2):
				mul[i][j] += a[i][k] * b[k][j] % p
	for i in range(2):
		for j in range(2):
			a[i][j] = mul[i][j] % p

def power(F, n):
	M = [[0, 1], [1, 1]]
	if n == 1:
		return (F[0][0] + F[0][1]) % p
	power(F, n // 2)
	multiply(F, F)
	if n % 2 == 1:
		multiply(F, M)
	return (F[0][0] + F[0][1]) % p

def fib(n):
	F = [[0, 1], [1, 1]]
	if n == 1 or n == 2:
		return 1
	return power(F, n - 1) % p
n = int(input())
print(fib(n) * pow(2 ** n, -1, p) % p)


M = 998244353

def fibo(n):
	a = 1
	b = 1
	for i in range(2, n):
		(a, b) = (b, a + b)
	return b % M

def modInverse(a):
	return pow(a, M - 2, M)
n = int(input())
print(fibo(n) * modInverse(pow(2, n, M)) % M)


MOD = 998244353

def ADD(x, y):
	return (x + y) % MOD

def MUL(x, y):
	return x * y % MOD

def BINPOW(x, y):
	ans = 1
	while y > 0:
		if y % 2 == 1:
			ans = MUL(ans, x)
		x = MUL(x, x)
		y = y // 2
	return ans

def DIVIDE(x, y):
	return MUL(x, BINPOW(y, MOD - 2))
n = int(input())
dp = [0, 1]
for i in range(n - 1):
	(dp[0], dp[1]) = (dp[1], ADD(dp[0], dp[1]))
ans = DIVIDE(dp[1], BINPOW(2, n))
print(ans)


import sys
input = sys.stdin.readline
import math
m = 998244353
n = int(input())
a = 1
c = 1
f = [0] * (n + 2)
f[1] = 1
f[2] = 1
for i in range(3, n + 1):
	f[i] = (f[i - 1] + f[i - 2]) % m
a = f[n]
b = pow(pow(2, n), m - 2, m)
a = a * b
a %= m
print(a)


n = int(input())
dp = [1, 1]
for i in range(n - 2):
	dp.append(dp[-1] + dp[-2])
	dp = dp[1:]
x = dp[-1]
m = 998244353
y = pow(2, n, m)
y_inv = pow(y, m - 2, m)
ans = x * y_inv % m
print(ans)


import math
t = 1
l = [1, 1]
for i in range(2, 200001):
	l.append((l[i - 1] + l[i - 2]) % 998244353)
while t:
	t -= 1
	n = int(input())
	x = l[n - 1]
	y = pow(2, n)
	print(x * pow(y, 998244351, 998244353) % 998244353)


def calc(x):
	if x == 0:
		return (0, 1)
	else:
		(k, kplusone) = calc(int(x // 2))
		twok = k * pow(2 * kplusone - k + r, 1, r)
		twokplusone = pow(pow(k ** 2, 1, r) + pow(kplusone ** 2, 1, r), 1, r)
		if x % 2 == 0:
			return (twok, twokplusone)
		else:
			return (twokplusone, pow(twok + twokplusone, 1, r))
(n, r) = (int(input()), 998244353)
top = calc(n)[0] % r
bottom = pow(2 ** n, -1, r)
print(top * bottom % r)


import sys
input = sys.stdin.readline
from collections import defaultdict as dc
from collections import Counter
from bisect import bisect_right, bisect_left
import math
from operator import itemgetter
from heapq import heapify, heappop, heappush
n = int(input())
m = 998244353
if n == 1:
	c = 1
else:
	a = 0
	b = 1
	m = 998244353
	for i in range(2, n + 1):
		c = a + b
		a = b
		b = c
p = pow(2, n, m)
y = pow(p, m - 2, m)
print(c * y % m)


def gcd_extended(a, b):
	if a == 0:
		return (b, 0, 1)
	(gcd, x1, y1) = gcd_extended(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (gcd, x, y)

def power(a, n, p):
	if n == 0:
		return 1
	x = power(a, n // 2, p)
	x = x * x % p
	if n % 2 == 1:
		x = x * a % p
	return x % p
p = 998244353
n = int(input())
rev_2 = gcd_extended(2, p)[1] % p
a = [1, rev_2]
c = [1, rev_2]
powers = [1]
rev_powers = [1]
for i in range(1, 2 * 10 ** 5 + 1):
	powers.append(powers[-1] * 2 % p)
	rev_powers.append(rev_powers[-1] * rev_2 % p)
for k in range(2, n + 1):
	l = 1
	s = 0
	maxp = k if k % 2 == 1 else k - 1
	if k < 3:
		while l <= k:
			s += a[k - l] * powers[maxp - l] % p
			l += 2
		c.append(int(s * rev_2 ** (k - 1)) % p)
	else:
		c.append(int((c[k - 2] * rev_2 * rev_2 + c[k - 1] * rev_2) % p))
print(c[n])


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

def modinv(n):
	return pow(n, mod - 2, mod)
if n == 1:
	print(modinv(2))
	exit()
u = [0] * (n + 1)
u[0] = 1
u[1] = 1
u[2] = 1
k = pow(2, n, mod)
acum = [0] * (n + 1)
acum[0] = 1
acum[1] = 2
acum[2] = 3
for i in range(3, n + 1):
	acum[i] = (acum[i - 2] + acum[i - 1]) % mod
print(acum[-3] * modinv(k) % mod)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 998244353

def fib(n):
	f = [1, 1]
	for i in range(2, n):
		f.append((f[-1] + f[-2]) % mod)
	return f[n - 1] % mod
n = stdint()
num = fib(n)
den = pow(2 ** n, mod - 2, mod)
print(num * den % mod)


MOD = 998244353

class ModInt:

	def __init__(self, x):
		self.x = x % MOD

	def __str__(self):
		return str(self.x)
	__repr__ = __str__

	def __add__(self, other):
		return ModInt(self.x + other.x) if isinstance(other, ModInt) else ModInt(self.x + other)

	def __sub__(self, other):
		return ModInt(self.x - other.x) if isinstance(other, ModInt) else ModInt(self.x - other)

	def __mul__(self, other):
		return ModInt(self.x * other.x) if isinstance(other, ModInt) else ModInt(self.x * other)

	def __truediv__(self, other):
		return ModInt(self.x * pow(other.x, MOD - 2, MOD)) if isinstance(other, ModInt) else ModInt(self.x * pow(other, MOD - 2, MOD))

	def __pow__(self, other):
		return ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(self.x, other, MOD))
	__radd__ = __add__

	def __rsub__(self, other):
		return ModInt(other.x - self.x) if isinstance(other, ModInt) else ModInt(other - self.x)
	__rmul__ = __mul__

	def __rtruediv__(self, other):
		return ModInt(other.x * pow(self.x, MOD - 2, MOD)) if isinstance(other, ModInt) else ModInt(other * pow(self.x, MOD - 2, MOD))

	def __rpow__(self, other):
		return ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else ModInt(pow(other, self.x, MOD))
N = int(input())
dp = [ModInt(1)] * (N + 1)
for i in range(3, N + 1):
	dp[i] = dp[i - 1] + dp[i - 2]
print(dp[-1] / pow(ModInt(2), N))


def mi(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
n = int(input())
f = 0
s = 1
m = 998244353
for i in range(n - 1):
	a = f + s
	f = s
	s = a
i = n
while s % 2 == 0:
	s = s // 2
	i -= 1
print(s * mi(pow(2, i, m), m) % m)


import sys

def II():
	return int(sys.stdin.readline())
n = II()
dp = [1, 1]
mod = 998244353
for i in range(2, n):
	dp.append((dp[-1] + dp[-2]) % mod)
ans = dp[-1]
print(ans * pow(pow(2, n, mod), mod - 2, mod) % mod)


import io, os, sys
from math import *

def read_ints():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_str():
	return sys.stdin.readline().strip()

def power(a, n, p):
	if n == 0:
		return 1
	x = power(a, n // 2, p)
	x *= x
	if n % 2 == 1:
		x *= a
	return x % p

def modinv(x, p):
	return power(x, p - 2, p)

def add(a, b, c, d):
	if b < d:
		m = d // b
		b *= m
		a *= m
	if d < b:
		m = b // d
		d *= m
		c *= m
	return (a + c, b)

def main():
	M = 998244353
	n = read_ints()[0]
	x = [1] * (n + 2)
	y = [0] * (n + 2)
	y[0] = 1
	y[1] = 2
	y[2] = 4
	for i in range(3, n + 1):
		a = x[i - 1]
		b = y[i - 1] * 2 % M
		c = x[i - 2]
		d = y[i - 2] * 4 % M
		(x[i], y[i]) = add(a, b, c, d)
		x[i] %= M
		y[i] %= M
	inv = modinv(y[n], M)
	print(x[n] * inv % M)
main()


import os, sys
from io import BytesIO, IOBase

def main():
	mod = 998244353
	n = int(input())
	dp = [0] * (n + 1)
	(dp[1], dp[0]) = (1, 1)
	su = 1
	for i in range(2, n + 1):
		dp[i] = su
		su = (su + dp[i - 1]) % mod
	print(dp[n] * pow(pow(2, n, mod), mod - 2, mod) % mod)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from bisect import *
from collections import *
from random import *
from decimal import *
from random import *
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = 1
p = 998244353
while t:
	t -= 1
	n = inp()
	if n == 1:
		de = pow(2, n, p)
		de = pow(de, p - 2, p)
		print(de % p)
		exit(0)
	pr = [1, 2]
	for i in range(n - 2):
		pr.append((pr[-1] + pr[-2]) % p)
	nu = pr[n - 2]
	de = pow(2, n, p)
	de = pow(de, p - 2, p)
	print(int(nu * de % p))


import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd

def lcm(x, y):
	return x * y / gcd(x, y)

def arr2D(n, m, default=0):
	return [[default for j in range(m)] for i in range(n)]

def arr3D(n, m, r, default=0):
	return [[[default for k in range(r)] for j in range(m)] for i in range(n)]

def sortDictV(x):
	return {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}

class DSU:

	def __init__(self, length):
		self.length = length
		self.parent = [-1] * self.length

	def getParent(self, node, start):
		if node >= self.length:
			return False
		if self.parent[node] < 0:
			if start != node:
				self.parent[start] = node
			return node
		return self.getParent(self.parent[node], start)

	def union(self, node1, node2):
		parent1 = self.getParent(node1, node1)
		parent2 = self.getParent(node2, node2)
		if parent1 == parent2:
			return False
		elif self.parent[parent1] <= self.parent[parent2]:
			self.parent[parent1] += self.parent[parent2]
			self.parent[parent2] = parent1
		else:
			self.parent[parent2] += self.parent[parent1]
			self.parent[parent1] = parent2
		return True

	def getCount(self, node):
		return -self.parent[self.getParent(node, node)]
m = 998244353

def modexp(x, n):
	if n == 0:
		return 1
	elif n % 2 == 0:
		return modexp(x * x % m, n // 2)
	else:
		return x * modexp(x * x % m, (n - 1) / 2) % m

def mod1(a, b):
	c = gcd(a, b)
	a = a // c
	b = b // c
	d = modexp(b, m - 2)
	ans = a % m * (d % m) % m
	return ans

def solve(n):
	summ = 0
	a = 0
	b = 1
	for i in range(n):
		c = b
		b = a + b
		a = c
	return mod1(a, 2 ** n)
n = int(input())
print(solve(n))


def Huge_Fib(n, m):
	(v1, v2, v3) = (1, 1, 0)
	for rec in bin(n)[3:]:
		calc = v2 * v2 % m
		(v1, v2, v3) = ((v1 * v1 + calc) % m, (v1 + v3) * v2 % m, (calc + v3 * v3) % m)
		if rec == '1':
			(v1, v2, v3) = ((v1 + v2) % m, v1, v2)
	return v2
n = int(input())
p = 998244353
if n <= 2:
	f = 1
else:
	f = Huge_Fib(n, p)
mul = (p + 1) // 2
s = 0
while f % 2 == 0:
	s = s + 1
	f = f // 2
base = pow(mul, n - s, p)
print(base * f % p)


MOD = 998244353

def powr(n, N):
	temp = 1
	while N > 0:
		if N % 2 != 0:
			temp = temp * n % MOD
		n = n * n % MOD
		N = N // 2
	return temp % MOD
n = int(input())
L = [0, 1]
for i in range(2, n + 1):
	L.append((L[-1] + L[-2]) % MOD)
num = L[-1] % MOD
dem = powr(2, n) % MOD
tt = pow(dem, MOD - 2, MOD) % MOD
ans = num * tt % MOD
print(ans)


import sys
input = sys.stdin.readline

def prog():
	mod = 998244353
	n = int(input())
	dp = [0] * (n + 1)
	dp[0] = 1
	prev_states = [0, 1]
	for i in range(1, n + 1):
		dp[i] = prev_states[i % 2]
		prev_states[(i - 1) % 2] = (prev_states[(i - 1) % 2] + dp[i]) % mod
	print(dp[n] * pow(pow(2, n, mod), mod - 2, mod) % mod)
prog()


M = 998244353

def inv2(a, mod=998244353):
	(res, b) = (1, mod - 2)
	while b != 0:
		if b & 1:
			res = res * a % mod
		(a, b) = (a * a % mod, b >> 1)
	return res
n = int(input())
(a, b) = (1, 1)
for i in range(3, n + 1):
	(a, b) = (b, (a + b) % M)
print(b * inv2(2 ** n) % M)


import sys
import math, bisect
sys.setrecursionlimit(10 ** 6)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.readline())
neo = lambda : map(int, sys.stdin.readline().split())
Neo = lambda : list(map(int, sys.stdin.readline().split()))
n = I()
m = 998244353

def fib(n):
	F = [[1, 1], [1, 0]]
	if n == 0:
		return 0
	power(F, n - 1)
	return F[0][0]

def multiply(F, M):
	x = F[0][0] * M[0][0] + F[0][1] * M[1][0]
	y = F[0][0] * M[0][1] + F[0][1] * M[1][1]
	z = F[1][0] * M[0][0] + F[1][1] * M[1][0]
	w = F[1][0] * M[0][1] + F[1][1] * M[1][1]
	F[0][0] = x
	F[0][1] = y
	F[1][0] = z
	F[1][1] = w

def power(F, n):
	if n == 0 or n == 1:
		return
	M = [[1, 1], [1, 0]]
	power(F, n // 2)
	multiply(F, F)
	if n % 2 != 0:
		multiply(F, M)
print(fib(n) * pow(2 ** n, m - 2, m) % m)


n = int(input())
k1 = 1
k2 = 1
MOD = 998244353
for i in range(n - 2):
	tmp = k2
	k2 = k1 + k2
	k1 = tmp
ans = k2
s = pow(2, MOD - 2, MOD)
ans = ans * pow(s, n, MOD) % MOD
print(ans)


n = int(input())
m = 998244353
(f0, f1) = (0, 1)
for _ in range(2, n + 1):
	(f0, f1) = (f1, (f0 + f1) % m)
print(f1 * pow(2 ** n, m - 2, m) % m)


import sys

def main():
	inp = [int(x) for x in sys.stdin.read().split()]
	ii = 0
	n = inp[ii]
	ii += 1
	MOD = 998244353
	dp = [0] * (n + 1)
	dp[1] = 1
	for x in range(2, n + 1):
		dp[x] = (dp[x - 1] + dp[x - 2]) % MOD
	de = pow(2, -n, MOD)
	print(dp[n] * de % MOD)
main()


from collections import Counter, defaultdict, deque
import math
import sys
input = sys.stdin.readline
MOD = 998244353

def solve():
	n = int(input())
	f = [1, 1]
	for i in range(n):
		f.append((f[-1] + f[-2]) % MOD)
	den = pow(2, n, MOD)
	den = pow(den, MOD - 2, MOD)
	res = f[n - 1] * den % MOD
	print(res)
tt = 1
for test in range(tt):
	solve()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def getint():
	return int(input())

def getints():
	return list(map(int, input().split()))

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))
m = 998244353

def fib(n):
	if n == 1:
		return 1
	elif n == 2:
		return 1
	else:
		a = 1
		b = 1
		for i in range(n - 2):
			c = (a + b) % m
			a = b
			b = c
		return b
from datetime import datetime

def main():
	n = getint()
	st = datetime.now()
	v = fib(n) % m
	et = datetime.now()
	st = datetime.now()
	out = v * pow(pow(2, n), m - 2, m) % m
	et = datetime.now()
	print(out)
main()


M = 998244353
n = int(input())
F = [1, 1, 1]
for i in range(n - 2):
	F.append((F[-1] + F[-2]) % M)
print(F[-1] * pow(2, M - n - 1, M) % M)


mod = 998244353

def binpow(a, b):
	if b == 0:
		return 1
	res = binpow(a, b // 2)
	if b % 2:
		return res * res * a % mod
	else:
		return res * res % mod

def inverse(n):
	return binpow(n, mod - 2)

def case():
	n = int(input())
	fi = [0] * (n + 2)
	fi[1] = 1
	fi[2] = 1
	for i in range(3, n + 1):
		fi[i] = (fi[i - 1] + fi[i - 2]) % mod
	ans = inverse(binpow(2, n))
	print(ans * fi[n] % mod)
for _ in range(1):
	case()


n = int(input())
M = 998244353
(a1, a2) = (1, 1)
if n > 2:
	for i in range(n - 2):
		(a2, a1) = ((a1 + a2) % M, a2 % M)
	ans = a2 % M
else:
	ans = a2 % M
print(ans * pow(2, M - n - 1, M) % M)


n = int(input())

def fun(n):
	(v1, v2, v3) = (1, 1, 0)
	for rec in bin(n)[3:]:
		calc = v2 * v2
		(v1, v2, v3) = (v1 * v1 + calc, (v1 + v3) * v2, calc + v3 * v3)
		if rec == '1':
			(v1, v2, v3) = (v1 + v2, v1, v2)
	return v2
ans = fun(n)
ans1 = pow(pow(2, n), 998244351, 998244353)
print(ans1 * ans % 998244353)


n = int(input())
(x, y) = (0, 1)
mod = 998244353
z = pow(2, mod - 1 - n, mod)
for i in range(n - 1):
	(x, y) = (y, (x + y) % mod)
print(y * z % mod)


mod = 998244353
n = int(input())
a = 1
b = 1
m = pow(2, n)
n -= 2
while n > 0:
	(a, b) = (b % mod, (a + b) % mod)
	n -= 1
while b % 2 == 0:
	b = b >> 1
	m = m >> 1
print(b * pow(m, mod - 2, mod) % mod)


MOD = 998244353
n = int(input())
dp = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
	if i == 1:
		dp[i] = 1
	elif i == 2:
		dp[i] = 1
	else:
		dp[i] = dp[i - 1] + dp[i - 2]
		dp[i] %= MOD
nWays = dp[n]
den = pow(2, n, MOD)
ans = nWays * pow(den, MOD - 2, MOD) % MOD
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
m = 998244353
(f0, f1) = (0, 1)
for _ in range(2, n + 1):
	(f0, f1) = (f1, (f0 + f1) % m)
print(f1 * pow(2 ** n, -1, m) % m)


import sys
import math
from collections import Counter, defaultdict
LI = lambda : list(map(int, input().split()))
MAP = lambda : map(int, input().split())
IN = lambda : int(input())
S = lambda : input()
mod = 998244353

def binpow(a, b):
	if b == 0:
		return 1
	res = binpow(a, b // 2)
	if b % 2:
		return res * res * a % mod
	else:
		return res * res % mod

def inverse(n):
	return binpow(n, mod - 2)

def case():
	n = IN()
	fi = [0] * (n + 2)
	fi[1] = 1
	fi[2] = 1
	for i in range(3, n + 1):
		fi[i] = (fi[i - 1] + fi[i - 2]) % mod
	ans = inverse(binpow(2, n))
	print(ans * fi[n] % mod)
for _ in range(1):
	case()


MOD = 998244353

def somma(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	else:
		a = power(x, y // 2)
		b = multiply(a, a)
		if y % 2:
			b = multiply(x, b)
		return b

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def fact(x):
	res = 1
	i = 2
	while i <= x:
		res = multiply(res, i)
		i += 1
	return res
n = int(input())
k = 1 if n % 2 else 2
f_num = fact((n + k) // 2 - 1)
f_den1 = fact(k - 1)
f_den2 = fact((n - k) // 2)
res = divide(f_num, multiply(f_den1, f_den2)) % MOD
while k + 2 <= n:
	k += 2
	f_num = multiply((n + k) // 2 - 1, f_num)
	f_den1 = multiply(multiply(k - 1, f_den1), k - 2)
	if n == k:
		f_den2 = 1
	else:
		f_den2 = divide(f_den2, (n - k) // 2 + 1)
	res1 = divide(f_num, multiply(f_den1, f_den2)) % MOD
	res = somma(res, res1)
print(divide(res, power(2, n)))


import math

def extended_gcd(a, b):
	(s, old_s) = (0, 1)
	(r, old_r) = (b, a)
	while r:
		q = old_r // r
		(old_r, r) = (r, old_r - q * r)
		(old_s, s) = (s, old_s - q * s)
	return (old_r, old_s, (old_r - old_s * a) // b if b else 0)

def modinv(a, m):
	(g, x, _) = extended_gcd(a % m, m)
	return x % m if g == 1 else None
from fractions import Fraction

def Pok(n):
	if n < 0:
		return 0
	if n == 0:
		return 1
	ret = 0
	f = Fraction(1, 2)
	x = n - 1
	while x >= 0:
		ret += f * Pok(x)
		x -= 2
		f *= Fraction(1, 4)
	return ret
P = 998244353

def fib(n):
	(a, b) = (1, 1)
	for _ in range(n - 1):
		(a, b) = (b, a + b)
		a %= P
		b %= P
	return a

def ans(i):
	ret = fib(i) * modinv(pow(2, i, P), P)
	ret %= P
	ret += P
	ret %= P
	return ret
print(ans(int(input())))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	n = int(input())
	(x, y) = (0, 1)
	mod = 998244353
	for i in range(n - 1):
		(x, y) = (y, x + y)
		x %= mod
		y %= mod
	twop = pow(2, n, mod)
	print(y * pow(twop, mod - 2, mod) % mod)


n = int(input())
mod = 998244353
totientMod = 998244352
totalWays = pow(2, n, mod)
totalWaysInv = pow(totalWays, totientMod - 1, mod)
if n == 1:
	ways = 1
elif n == 2:
	ways = 1
else:
	(a, b) = (1, 1)
	for i in range(2, n):
		(a, b) = (b, (a + b) % mod)
	ways = b
print(ways * totalWaysInv % mod)


import sys, math
input = sys.stdin.readline
n = int(input())
mod = 998244353
denom = pow(2, n * (mod - 2) % (mod - 1), mod)
a = 0
b = 1
for i in range(n - 1):
	temp = a + b
	a = b
	b = temp
	a %= mod
	b %= mod
ans = b * denom % mod
print(ans)


mod = 998244353

def qpow(a, b):
	ans = 1
	base = a
	while b:
		if b & 1:
			ans = (ans * base % mod + mod) % mod
		base = (base * base % mod + mod) % mod
		b = b >> 1
	return ans
n = input()
n = int(n)
a = b = 1
c = 0
if n == 1 or n == 2:
	c = 1
else:
	for i in range(3, n + 1):
		c = (a + b) % mod
		a = b
		b = c
print(b * qpow(qpow(2, n), mod - 2) % mod)


def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(gcd, x, y) = egcd(b % a, a)
		return (gcd, y - b // a * x, x)
n = int(input())
mod = 998244353
(_, _, inv2) = egcd(mod, 2)
inv2 = inv2 % mod
(x1, x2) = (0, inv2)
for _ in range(n - 1):
	(x1, x2) = (x2, x1 * inv2 * inv2 % mod + x2 * inv2 % mod)
print(x2 % mod)


p = 998244353
n = int(input())
dp = [1 for i in range(n + 1)]
(odd, even) = (1, 1)
for i in range(2, n + 1):
	if i % 2 == 0:
		dp[i] = odd
		even = (even + odd) % p
	else:
		dp[i] = even
		odd = (odd + even) % p
ways = dp[n]
den = pow(2, n, p)
ans = ways * pow(den, p - 2, p) % p
print(ans)


def power(a, b, mod):
	res = 1
	while b:
		if b % 2:
			res = res * a % mod
		b //= 2
		a = a * a % mod
	return res % mod

def divide(a, b, mod):
	return a * power(b, mod - 2, mod) % mod
n = int(input())
MOD = 998244353
fib = [0, 1]
for i in range(2, 200001):
	fib.append((fib[-1] + fib[-2]) % MOD)
print(divide(fib[n], power(2, n, MOD), MOD))


n = int(input())
M = 998244353

def fastfrac(a, b):
	numb = pow(b, M - 2, M)
	return a % M * (numb % M) % M
if n < 3:
	num = 1
else:
	oddsum = 1
	evensum = 1
	i = 0
	for i in range(2, n + 1):
		if i % 2 == 1:
			num = evensum
			oddsum += num
		else:
			num = oddsum
			evensum += num
divisor = pow(2, n, M)
print(fastfrac(num, divisor))


def modinv(a, m):
	(b, u, v) = (m, 1, 0)
	while b:
		t = a // b
		a -= t * b
		(a, b) = (b, a)
		u -= t * v
		(u, v) = (v, u)
	u %= m
	return u
n = int(input())
dp = [0] * (n + 1)
sdp0 = [0, 1]
sdp1 = [0, 1]
dp[0] = 1
dp[1] = 1
MOD = 998244353
for i in range(2, n + 1):
	if i % 2 == 0:
		dp[i] = sdp1[i // 2] % MOD
		sdp0.append((dp[i] + sdp0[-1]) % MOD)
	else:
		dp[i] = sdp0[i // 2 + 1] % MOD
		sdp1.append((dp[i] + sdp1[-1]) % MOD)
x = dp[n]
y = pow(2, n, MOD)
ans = x * modinv(y, MOD)
print(ans % MOD)


n = int(input())
m = 998244353
inv = 499122177
x = [inv, inv ** 2 % m]
for _ in range(max(0, n - 2)):
	x.append((x[-1] * x[0] + x[-2] * x[1]) % m)
print(x[n - 1])


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def power(x, y, z):
	if y == 0:
		return 1
	temp = power(x, y // 2, z)
	if y % 2 == 0:
		return temp * temp % z
	return x * temp * temp
z = 998244353
b = power(2, n, z)

def fib(n):
	if n < 3:
		return 1
	a = 1
	b = 1
	for i in range(n - 2):
		if i % 2 == 0:
			a += b
		else:
			b += a
	return max(a, b)
a = fib(n)
a = a % z
c = modInverse(b, z)
a *= c
a %= z
print(a)


mod = 998244353
n = int(input())
if n == 1:
	ans = pow(2, mod - 2, mod)
	print(ans)
else:
	a = 0
	b = 1
	for i in range(n - 1):
		c = (b + a) % mod
		a = b
		b = c
	ans = pow(2, n, mod)
	ans = pow(ans, mod - 2, mod)
	print(ans * c % mod)


mod = 998244353

def modInverse(a, m):
	g = gcd(a, m)
	return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
n = int(input())
l = []
l.append(0)
l.append(1)
i = 2
while i <= n:
	l.append((l[i - 1] + l[i - 2]) % mod)
	i += 1
y = modInverse(pow(2, n), mod)
print(l[n] * y % mod)


from sys import stdin
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
n = it()
mod = 998244353
(a, b) = (0, 1)
for i in range(2, n + 1):
	(a, b) = (b, (a + b) % mod)
print(b * pow(2 ** n, mod - 2, mod) % mod)


def Fibonacci(n):
	a1 = 0
	a2 = 1
	for i in range(n):
		a2 = (a2 + a1) % 998244353
		a1 = a2 - a1
	return a1

def Denominador(n):
	MOD = 998244353
	return pow(2, -n, MOD)

def Func(n):
	return Fibonacci(n) * Denominador(n) % 998244353
n = int(input())
print(Func(n))


p = 998244353
n = int(input())
ar = [0] * (n + 10)
ar[0] = 1
ar[1] = 1
ar[2] = 1
for i in range(3, n + 1):
	ar[i] = (ar[i - 1] + ar[i - 2]) % p
d = int(pow(2, n, p))
d = int(pow(d, p - 2, p))
print(ar[n] * d % p)


m = 998244353
dp = [1, 1, 1]
n = int(input())
d1 = 1
d2 = 2
for i in range(3, n + 1):
	if i % 2 == 0:
		dp.append(d1 % m)
		d2 = (d2 + dp[-1]) % m
	else:
		dp.append(d2)
		d1 = (d1 + dp[-1]) % m
d = pow(2, n, m)
print(dp[n] * pow(d, m - 2, m) % m)


def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		print("Inverse doesn't exist")
	else:
		return power(a, m - 2, m)

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def solution():
	n = int(input())
	mod = 998244353
	a = [0] * (n + 5)
	a[1] = 1
	a[2] = 1
	for i in range(3, n + 1):
		a[i] += (a[i - 1] + a[i - 2]) % mod
	q = modInverse(power(2, n, mod), mod)
	print(a[n] * q % mod)
t = 1
for _ in range(t):
	solution()


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from itertools import permutations as p
from bisect import bisect_left as bl, bisect_right as br
mod = 998244353

def fibo_n(n):
	if n == 0:
		return 0
	if n <= 2:
		return 1
	a = 1
	b = 1
	for i in range(3, n + 1):
		(a, b) = (b, a + b)
	return b
mp = lambda : map(int, input().split())
it = lambda : int(input())
n = it()
print(round(fibo_n(n)) * pow(2 ** n, mod - 2, mod) % mod)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def expo(a, b):
	(x, y) = (1, a)
	while b > 0:
		if b & 1:
			x = x * y
		y = y * y
		b >>= 1
	return x

def power(x, y, m):
	if y == 0:
		return 1
	p = power(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return -1
	else:
		return power(a, m - 2, m)

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def main():
	try:
		n = I()
		fib = [0, 1]
		for i in range(2, n + 1):
			temp = fib[-1] + fib[-2]
			fib[-2] = fib[-1]
			fib[-1] = temp
		ans = fib[-1] % M * modInverse(expo(2, n), M) % M % M
		print(ans)
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


import io, os
from math import gcd
M = 998244353

def inv(a):
	return pow(a, M - 2, M)
N = int(input())
fact = [0 for _ in range(N)]
fact[0] = acc = 1
finv = [0 for _ in range(N)]
finv[0] = accinv = 1

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
for i in range(1, len(fact)):
	acc = acc * i % M
	fact[i] = acc
	accinv = accinv * modInverse(i, M) % M
	finv[i] = accinv

def binom(n, r):
	return fact[n] * finv[r] * finv[n - r]
ans = 0
for towers in range(1, N + 1):
	target = N - towers
	if target % 2:
		continue
	target //= 2
	ans = (ans + binom(target + towers - 1, towers - 1)) % M
i2 = inv(2)
ans = ans * pow(i2, N, M) % M
print(ans)


MOD = 998244353
n = int(input())
a = 1
b = 1
for i in range(n - 1):
	tmp_b1 = b
	b = a + b
	a = tmp_b1
print(a * pow(1 << n, MOD - 2, MOD) % MOD)


from sys import stdin, stdout

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a, m):
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
inv2 = modinv(2, 998244353)
inv4 = modinv(4, 998244353)
n = int(stdin.readline())
if n == 1:
	stdout.write(str(inv2) + '\n')
	exit()
if n == 2:
	stdout.write(str(inv4) + '\n')
	exit()
P_n_minus_2 = inv2
P_n_minus_1 = inv4
i = 5
while i <= n + 2:
	P_n = inv4 * (2 * P_n_minus_1 + P_n_minus_2) % 998244353
	(P_n_minus_2, P_n_minus_1) = (P_n_minus_1, P_n)
	i += 1
stdout.write(str(P_n) + '\n')


import bisect
from itertools import accumulate, count
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
from sys import maxsize
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime

def primefactors(n):
	fac = []
	while n % 2 == 0:
		fac.append(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 2):
		while n % i == 0:
			fac.append(i)
			n = n // i
	if n > 1:
		fac.append(n)
	return sorted(fac)

def factors(n):
	fac = set()
	fac.add(1)
	fac.add(n)
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			fac.add(i)
			fac.add(n // i)
	return list(fac)

def modInverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x
M = 998244353
n = int(input())
(a, b) = (0, 1)
for i in range(2, n + 1):
	(a, b) = (b, (a + b) % M)
print(b * pow(2, n * (M - 2), M) % M)


(x, y) = (0, 0)

def extgcd(a, b):
	global x, y
	if b == 0:
		(x, y) = (1, 0)
	else:
		(x, y) = (y, x)
		extgcd(b, a % b)
		(x, y) = (y, x)
		y -= a // b * x

def fib(n):
	(f1, f2) = (0, 1)
	for _ in range(n):
		(f1, f2) = (f2, f1 + f2)
	return f1

def sol(n):
	a = 2 ** n
	b = 998244353
	extgcd(a, b)
	global x, y
	while x < 0:
		x += b
	print(x * fib(n) % b)
sol(int(input()))


import sys
input = sys.stdin.readline
n = int(input())
DP = [0] * (n + 5)
SUM = [0] * (n + 5)
SUM[0] = 1
mod = 998244353
for i in range(n):
	SUM[i] = (SUM[i] + SUM[i - 2]) % mod
	DP[i] = SUM[i]
	SUM[i + 1] = DP[i]
print(DP[n - 1] * pow(pow(2, n, mod), mod - 2, mod) % mod)


def answer(n):
	f1 = 1
	f2 = 1
	m = 998244353
	for i in range(3, n + 1):
		f = f1 + f2
		f1 = f2
		f2 = f
	x = pow(2, n, m)
	x = pow(x, m - 2, m)
	return f2 * x % m
t = int(input())
print(answer(t))


MOD = 998244353

def find(x: int, mod=MOD):
	k = mod - 2
	ans = 1
	while k:
		if k & 1:
			ans = ans * x % mod
		x = x * x % mod
		k >>= 1
	return ans
n = int(input())
ans = 1
pre = [1, 1]
for i in range(2, n + 1):
	ans = pre[i % 2]
	pre[i % 2 ^ 1] = (pre[i % 2 ^ 1] + ans) % MOD
print(ans * find(pow(2, n, MOD)) % MOD)


mod = 998244353
dp = [0] * (2 * 10 ** 5 + 1)
dp[0] = 1
dp[1] = 1
dp[2] = 1
even = 2
odd = 1
for i in range(3, 2 * 10 ** 5 + 1):
	if i % 2 == 1:
		dp[i] = even % mod
		odd += dp[i]
		odd %= mod
	else:
		dp[i] = odd % mod
		even += dp[i]
		even %= mod
n = int(input())
r = pow(2, n, mod)
dp[n] *= pow(r, mod - 2, mod)
print(dp[n] % mod)


n = int(input())
m = 998244353
a = 1
b = 1
for i in range(3, n + 1):
	(a, b) = (b, a + b)
ans = b % m * pow(2, n * (m - 2), m) % m
print(ans)


m = 998244353

def fib(n):
	if n == 1:
		return 1
	elif n == 2:
		return 1
	else:
		a = 1
		b = 1
		for i in range(n - 2):
			c = (a + b) % m
			a = b
			b = c
		return b % m
n = int(input())
v = fib(n) % m
out = v * pow(pow(2, n), m - 2, m) % m
print(out)


n = int(input())
m = 998244353
(x, y) = (1, 1)
for _ in range(2, n):
	(x, y) = (y, x + y)
print(y * pow(pow(2, n, m), m - 2, m) % m)


n = int(input(''))
mod = 998244353
dp = [1, 1]
for i in range(2, n):
	dp.append((dp[-1] + dp[-2]) % mod)
print(pow(pow(2, n, mod), mod - 2, mod) * dp[n - 1] % mod)


mod = 998244353

def pow(n, k):
	if k == 0:
		return 1
	if k % 2 == 0:
		a = pow(n, k // 2)
		return a * a % mod
	return n * pow(n, k - 1) % mod
n = int(input())
a = 0
b = 1
for i in range(n):
	b += a
	a = b - a
y = pow(2, n)
print(pow(y, mod - 2) * a % mod)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush, nsmallest
from math import ceil, floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
from decimal import Decimal
from copy import deepcopy
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var, end='\n'):
	sys.stdout.write(str(var) + end)

def outa(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
arr = [0, 1, 1]
for i in range(200000):
	arr.append((arr[-1] + arr[-2]) % mod2)
n = int(data())
out(arr[n] * pow(pow(2, n, mod2), mod2 - 2, mod2) % mod2)


t = 1
for _ in range(t):
	n = int(input())
	modo = 998244353
	(k1, k2) = (1, 1)
	for i in range(n - 2):
		tmp = k2
		k2 = k1 + k2
		k1 = tmp
	ans = k2
	explanation = 'as k2 store current ans , we use k1 as a storing element'
	s = pow(2, modo - 2, modo)
	ans = ans * pow(s, n, modo) % modo
	print(ans)


n = int(input())
m = 998244353
(x, y) = (0, 1)
for i in range(n - 1):
	(x, y) = (y, x + y)
	x %= m
	y %= m
r = pow(2, n, m)
print(y * pow(r, m - 2, m) % m)


def modinv(n, p):
	return pow(n, p - 2, p)

def main():
	MOD = 998244353
	n = int(input())
	q = modinv(pow(2, n, MOD), MOD)
	fib = [0] * 200005
	fib[1] = 1
	fib[2] = 1
	for i in range(3, 200005):
		fib[i] = fib[i - 1] + fib[i - 2]
		fib[i] %= MOD
	p = fib[n]
	ans = p % MOD * q % MOD % MOD
	print(ans)
main()


def calculate(p, q):
	mod = 998244353
	expo = 0
	expo = mod - 2
	while expo:
		if expo & 1:
			p = p * q % mod
		q = q * q % mod
		expo >>= 1
	return p
n = int(input())
a = 0
b = 1
for j in range(2, n + 1):
	(a, b) = (b, a + b)
print(calculate(b, 2 ** n))


import math

def compute_hcf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def fast_exp(a, p, m):
	if p == 0:
		return 1
	if p == 1:
		return a
	R = fast_exp(a, p // 2, m)
	if p % 2 == 0:
		return R % m * (R % m) % m
	else:
		return R % m * a * (R % m) % m

def small_q(number, r, div):
	if div == 1:
		return max(0, math.ceil(-(r / number)))
	q = (div * small_q(div, div - r, number % div) + (div - r)) / (number % div)
	return q
num = 998244353
n = int(input())
if n == 1:
	i = 1
	while int((num * i + 1) / 2) != (num * i + 1) / 2:
		i += 1
	y_inv = (num * i + 1) / 2
	print(int(y_inv % num))
elif n == 2 or n == 3:
	print(748683265)
else:
	t2 = 1
	t3 = 2
	t = 0
	for i in range(4, n + 1):
		t = t2 + t3
		t2 = t3
		t3 = t
	c = 0
	while t % 2 == 0:
		c += 1
		t //= 2
	found1 = 2 ** (n - c)
	ans1 = fast_exp(found1, num - 2, num)
	print(t % num * ans1 % num)


import copy
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
mo = 998244353

def exgcd(a, b):
	if not b:
		return (1, 0)
	(y, x) = exgcd(b, a % b)
	y -= a // b * x
	return (x, y)

def getinv(a, m):
	(x, y) = exgcd(a, m)
	return --1 if x == 1 else x % m

def comb(n, b):
	res = 1
	b = min(b, n - b)
	for i in range(b):
		res = res * (n - i) * getinv(i + 1, mo) % mo
	return res % mo

def quickpower(a, n):
	res = 1
	while n:
		if n & 1:
			res = res * a % mo
		n >>= 1
		a = a * a % mo
	return res
t = int(input())
li = [1, 1]
iv = getinv(2, mo)
while len(li) < t:
	li.append((li[-1] + li[-2]) % mo)
print(li[-1] * quickpower(iv, t) % mo)


def modInverse(a, m):
	m0 = m
	(y, x) = (0, 1)
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		return x + m0
	else:
		return x
n = int(input())
mod = 998244353
if n <= 2:
	print(modInverse(pow(2, n, mod), mod))
else:
	l = 1
	r = 1
	for _ in range(n - 2):
		mem = r
		r = (l + r) % mod
		l = mem
	print(r * modInverse(pow(2, n, mod), mod) % mod)


def modinv(a, m):
	b = m
	u = 1
	v = 0
	while b:
		t = a // b
		a -= t * b
		(a, b) = (b, a)
		u -= t * v
		(u, v) = (v, u)
	u %= m
	return u
n = int(input())
MOD = 998244353
dpsum = [0] * (n + 1)
dp = 1
for i in range(n):
	dpsum[i + 1] = (dp + dpsum[i]) % MOD
	dp = dpsum[i] % MOD
ans = dpsum[n]
div = modinv(2, MOD)
for _ in range(n):
	ans *= div
	ans %= MOD
print(ans)


def modInverse(a, m):
	g = gcd(a, m)
	if g != 1:
		return 1
	else:
		return power_fct(a, m - 2, m)

def power_fct(x, y, m):
	if y == 0:
		return 1
	p = power_fct(x, y // 2, m) % m
	p = p * p % m
	if y % 2 == 0:
		return p
	else:
		return x * p % m

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def radio_towers():
	n = int(input())
	modulo = 998244353
	fib = [1, 0]
	power = 2
	for i in range(1, n):
		fib = [sum(fib) % modulo, fib[0]]
		power = power * 2 % modulo
	print(modInverse(power, modulo) * fib[0] % modulo)
radio_towers()


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
md = 998244353
f2 = pow(2, md - 2, md)
f4 = pow(4, md - 2, md)
n = II()
dp = [0] * (n + 1)
s0 = f2
s1 = 0
for i in range(n):
	if i & 1:
		dp[i + 1] = s1
		s0 = (s0 * f4 + s1 * f2) % md
	else:
		dp[i + 1] = s0
		s1 = (s1 * f4 + s0 * f2) % md
print(dp[-1])


INF = 10 ** 10
TEST_CASES = False

def main():
	P = 998244353
	n = get_int()
	fib = [0, 1, 1]
	for i in range(3, n + 1):
		fib.append((fib[-1] + fib[-2]) % P)
	print(fib[n] * pow(pow(2, n, P), P - 2, P) % P)
import sys
out = []
get_int = lambda : int(input())
get_list = lambda : list(map(int, input().split()))
get_float_list = lambda : list(map(float, input().split()))
if not TEST_CASES:
	main()
else:
	[main() for _ in range(int(input()))]


import sys, os
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
m = 998244353

def main():
	n = int(input())
	(a, b) = (0, 1)
	for i in range(n - 1):
		(a, b) = (b, (a + b) % m)
	print(b * pow(2, n * (m - 2), m) % m)
main()