Stack has a positive integer P(P > 1).  
He starts a game where his initial score is 0.

In the i^{th} turn, with a probability of \frac{1}{2}, Stack adds \frac{1}{P^{i-1}} to his score. 
 
Stack stops after N turns.

Let S_{i} be his score after i turns and F(i) denote the [expected value] of S_{i}^{2}. 

For each integer i(1 ≤ i ≤ N), find the value of F(i) modulo 998244353. 

------ Input Format ------ 

The only line of input contains two space-separated positive integers N and P, as mentioned in the statement.

------ Output Format ------ 

Print N space-separated integers. For each integer i(1 ≤ i ≤ N), output the value of F(i) modulo 998244353. 

Formally, let M=998244353. It can be shown that the answer can be expressed as an irreducible fraction \frac{x}{y}, where x and y are integers and y \not \equiv 0 \pmod{M}.  
Output the integer equal to x \cdot y^{-1} \bmod M .  
In other words, output such an integer z that 0 ≤ z < M and z \cdot y \equiv x \pmod{M}.
.

------ Constraints ------ 

$1 ≤ N ≤ 3 \cdot 10^{5}$
$2 ≤ P ≤ 10^{5}$

----- Sample Input 1 ------ 
2 2

----- Sample Output 1 ------ 
499122177 124780545

----- explanation 1 ------ 
$S_{1}$ can be $0$ or $1$ with equal probability.
Thus $F(1)=\frac{0 \cdot 0}{2}+\frac{1 \cdot 1}{2} = \frac{1}{2}$.

$F(2)=\frac{7}{8}$.

----- Sample Input 2 ------ 
10 343

----- Sample Output 2 ------ 
499122177 379526990 822885144 761122022 256959043 151932103 340445396 758502677 478338987 125853909

----- explanation 2 ------

Difficulty: HARD
Tags: Mathematics

Probability

Starter code:

Solutions:
import math
mod1 = 998244353

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

def binpow(a, b):
	if b == 0:
		return 1
	tmp = binpow(a, b // 2)
	tmp = mul(tmp, tmp)
	if b % 2:
		return mul(tmp, a)
	return tmp

def mod_inverse(a, m=mod1):
	return binpow(a, m - 2)

def solve():
	(N, P) = map(int, input().split())
	dp = [0] * (N + 1)
	dp2 = [0] * (N + 1)
	dp[1] = dp2[1] = mod_inverse(2)
	inv2 = mod_inverse(2)
	for i in range(1, N + 1):
		y = binpow(P, i - 1)
		y = mod_inverse(y)
		val = dp[i - 1] + mul(binpow(y, 2), inv2) + mul(y, dp2[i - 1])
		val %= mod1
		dp[i] = val
		dp2[i] = (dp2[i - 1] + mul(y, inv2)) % mod1
	print(*dp[1:])
solve()


from fractions import Fraction
(n, p) = input().split()
n = int(n)
p = int(p)
m = 998244353

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):
	res = 1
	while y > 0:
		if y & 1 == 1:
			res = res * x
		y = y >> 1
		x = x * x
	return res
two = 1
k = 1
l = 2
x = 1
s = 1
arr = [499122177]
for i in range(2, n + 1):
	l = l * 2 * p ** 2 % m
	x = x * p % m
	two = two * 2 % m
	k = (2 * k + 2 * x * s + two * x ** 2 % m) % m
	s = (2 * s + x * two) % m
	arr.append(k * modInverse(l, m) % m)
print(' '.join((str(i) for i in arr)))


m = 998244353
(n, p) = [int(x) for x in input().split()]
ppow = ppow2 = pow(2, -1, m)
precip = pow(p, -1, m)
precipsq = pow(p, -2, m)
psum = 0
tot_sum = 0
for i in range(n):
	tot_sum += psum * ppow * 2 % m + ppow2
	tot_sum %= m
	print(tot_sum, end=' ' if i < n - 1 else '\n')
	psum = (psum + ppow) % m
	ppow = ppow * precip % m
	ppow2 = ppow2 * precipsq % m


mod = 998244353
(n, p) = map(int, input().split())
r = pow(2, -1, mod)
x = pow(p, -1, mod)
m = 0
a = 1
print(r, end=' ')
for i in range(n - 1):
	m += pow(x, i, mod)
	a = x * a % mod
	r += a * pow(2, -1, mod) * m + pow(a, 2, mod) * pow(2, -1, mod)
	r = r % mod
	print(r, end=' ')


mod = 998244353
(n, p) = map(int, input().split())
f = pow(2, -1, mod)
q = pow(p, -1, mod)
sumq = 0
Q = 1
print(f, end=' ')
for i in range(n - 1):
	sumq += pow(q, i, mod)
	Q = q * Q % mod
	f += Q * pow(2, -1, mod) * sumq + pow(Q, 2, mod) * pow(2, -1, mod)
	f %= mod
	print(f, end=' ')


def func(i):
	return func2(i, 998244351)

def func2(a, b):
	if b == 0:
		return 1
	temp = func2(a, b // 2)
	temp = func3(temp, temp)
	if b % 2:
		return func3(temp, a)
	return temp

def func3(a, b):
	i = a % 998244353
	j = b % 998244353
	return i * j % 998244353
(n, p) = map(int, input().split())
(l1, l2) = ([0] * (n + 1), [0] * (n + 1))
(l1[1], l2[1], fun2) = (func(2), func(2), func(2))
for i in range(2, n + 1):
	res1 = func2(p, i - 1)
	res2 = func(res1)
	val = l1[i - 1] + func3(func2(res2, 2), fun2) + func3(res2, l2[i - 1])
	l1[i] = val % 998244353
	l2[i] = (l2[i - 1] + func3(res2, fun2)) % 998244353
l1 = l1[1:]
print(*l1)


import math
MOD = 998244353

def multiply(a, b):
	return a % MOD * (b % MOD) % MOD

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

def inverse(a, m=MOD):
	return power(a, m - 2)

def main_func():
	(num_cases, prime) = map(int, input().split())
	dp = [0] * (num_cases + 1)
	dp2 = [0] * (num_cases + 1)
	dp[1] = dp2[1] = inverse(2)
	inv2 = inverse(2)
	for i in range(2, num_cases + 1):
		y = power(prime, i - 1)
		y = inverse(y)
		val = dp[i - 1] + multiply(power(y, 2), inv2) + multiply(y, dp2[i - 1])
		val %= MOD
		dp[i] = val
		dp2[i] = (dp2[i - 1] + multiply(y, inv2)) % MOD
	print(*dp[1:])
main_func()


import sys
from fractions import Fraction
MOD = 998244353
M = lambda i: i % MOD

def inv(a):
	return pow(M(a), MOD - 2, MOD)

def ipow(a, b):
	a = M(a)
	if b < 0:
		return inv(ipow(a, -b))
	else:
		return pow(a, b, MOD)

def solve(n, p):
	last = 0
	f = 0.0
	for k in range(1, n + 1):
		t = ipow(p, k) - 1
		t = M(t * inv(2 * (p - 1) * ipow(p, k - 1)))
		t = M(t + last * inv(p * p))
		last = t
		print(t, end=' ')
	print()
(n, p) = map(int, sys.stdin.read().split())
solve(n, p)


import math
import random
import statistics
import operator
import itertools
import sys
import copy
from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heapify, heappush, heappop
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
KPMOD2 = 1000000007
KPMOD1 = 998244353

def modinverse(a):
	return binpow(a, KPMOD1 - 2)

def modinv(a, KPMOD1=1000000007):
	return binpow(a, KPMOD1 - 2)

def mult(a, b):
	return a % KPMOD1 * (b % KPMOD1) % KPMOD1

def add(a, b):
	return (a % KPMOD1 + b % KPMOD1) % KPMOD1

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

def fact(a):
	if a == 0 or a == 1:
		return 1
	return a * (fact(a) % KPMOD1) % KPMOD1

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
MAX = 100
fact = [1] * MAX
invfact = [1] * MAX
for i in range(1, MAX):
	fact[i] = fact[i - 1] * i % KPMOD1
	invfact[i] = invfact[i - 1] * modinverse(i) % KPMOD1

def factors(n):
	if n == 0:
		return set()
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
(KPN, KPP) = [int(x) for x in input().split()]
KPL1 = [0] * (KPN + 1)
KPL2 = [0] * (KPN + 1)
KPL1[1] = KPL2[1] = modinverse(2)
KPM = modinverse(2)
for i in range(2, KPN + 1):
	KPY = binpow(KPP, i - 1)
	KPY = modinverse(KPY)
	KPV = KPL1[i - 1] + mult(binpow(KPY, 2), KPM) + mult(KPY, KPL2[i - 1])
	KPV %= KPMOD1
	KPL1[i] = KPV
	KPL2[i] = (KPL2[i - 1] + mult(KPY, KPM)) % KPMOD1
for i in range(1, KPN + 1):
	print(KPL1[i], end=' ')


def mod_inv(a, MOD):
	return pow(a, MOD - 2, MOD)
(N, P) = map(int, input().split())
MOD = 998244353
dp = [0] * (N + 1)
dp2 = [0] * (N + 1)
dp[1] = dp2[1] = mod_inv(2, MOD)
inv2 = mod_inv(2, MOD)
for i in range(2, N + 1):
	y = pow(P, i - 1, MOD)
	y = mod_inv(y, MOD)
	val = (dp[i - 1] + pow(y, 2, MOD) * inv2 % MOD + y * dp2[i - 1] % MOD) % MOD
	dp[i] = val
	dp2[i] = (dp2[i - 1] + y * inv2 % MOD) % MOD
for i in range(1, N + 1):
	print(dp[i], end=' ')


maxi = 998244353

def gun(a, b):
	return a % maxi * (b % maxi) % maxi

def hard(a, b):
	if b == 0:
		return 1
	t = hard(a, b // 2)
	t = gun(t, t)
	if b % 2:
		return gun(t, a)
	return t

def inve(a, m=maxi):
	return hard(a, m - 2)

def hardik():
	(k, l) = map(int, input().split())
	pca = [0] * (k + 1)
	pcb = [0] * (k + 1)
	pca[1] = pcb[1] = inve(2)
	inv2 = inve(2)
	for i in range(2, k + 1):
		y = hard(l, i - 1)
		y = inve(y)
		value = (pca[i - 1] + gun(hard(y, 2), inv2) + gun(y, pcb[i - 1])) % maxi
		pca[i] = value
		pcb[i] = (pcb[i - 1] + gun(y, inv2)) % maxi
	for i in range(1, k + 1):
		print(pca[i], end=' ')
	print()
hardik()


m = 998244353
[n, p] = [int(x) for x in input().split()]

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

def inverse(a):
	return gcdExtended(a, m)[1]
cumulative = 1
inverse_list = [1]
modulo_list = [1]
p_inverse = inverse(p)
for i in range(1, 2 * n):
	inverse_list.append(p_inverse * inverse_list[-1] % m)
	modulo_list.append(p * modulo_list[-1] % m)
common = inverse(2 * p - 2)
ans_list = [0]
for i in range(1, n + 1):
	x = ans_list[-1] + common * (m - 1 + modulo_list[i]) * inverse_list[2 * i - 2]
	x = x % m
	ans_list.append(x)
for i in range(1, n + 1):
	print(ans_list[i], end=' ')


def multiply_mod(kane1, kane2, mod=998244353):
	return kane1 % mod * (kane2 % mod) % mod

def power_mod(kane1, kane2, mod=998244353):
	if kane2 == 0:
		return 1
	tmp = power_mod(kane1, kane2 // 2, mod)
	tmp = multiply_mod(tmp, tmp, mod)
	if kane2 % 2:
		return multiply_mod(tmp, kane1, mod)
	return tmp

def inverse_mod(kane1, mod=998244353):
	return power_mod(kane1, mod - 2, mod)

def compute_sequence(N, P):
	dp = [0] * (N + 1)
	dp2 = [0] * (N + 1)
	dp[1] = dp2[1] = inverse_mod(2)
	inv2 = inverse_mod(2)
	for i in range(2, N + 1):
		y = power_mod(P, i - 1)
		y = inverse_mod(y)
		val = dp[i - 1] + multiply_mod(power_mod(y, 2), inv2) + multiply_mod(y, dp2[i - 1])
		val %= 998244353
		dp[i] = val
		dp2[i] = (dp2[i - 1] + multiply_mod(y, inv2)) % 998244353
	return dp[1:]
(N, P) = map(int, input().split())
result = compute_sequence(N, P)
for res in result:
	print(res, end=' ')


MOD = 998244353
(n, p) = map(int, input().split())

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

def tow(x, y):
	if y == 0:
		return 1
	cur = tow(x, y // 2)
	cur = into(cur, cur)
	if y % 2:
		return into(cur, x)
	return cur

def minv(x):
	return tow(x, MOD - 2)
(a, b) = ([0] * (n + 1), [0] * (n + 1))
a[1] = b[1] = minv(2)
i2 = minv(2)
for i in range(2, n + 1):
	tmp = minv(tow(p, i - 1))
	t = (a[i - 1] + into(tow(tmp, 2), i2) + into(tmp, b[i - 1])) % MOD
	(a[i], b[i]) = (t, (into(tmp, i2) + b[i - 1]) % MOD)
print(*a[1:])


def mod_inverse(a, m=998244353):
	return binpow(a, m - 2, m)

def binpow(a, b, mod=998244353):
	if not b:
		return 1
	tmp = binpow(a, b // 2, mod)
	tmp = mul(tmp, tmp, mod)
	if b % 2:
		return mul(tmp, a, mod)
	return tmp

def mul(a, b, mod=998244353):
	return a * b % mod
for _ in range(1):
	(N, P) = map(int, input().split())
	dp2 = [0] * (N + 1)
	dp = [0] * (N + 1)
	dp[1] = dp2[1] = mod_inverse(2)
	inv2 = mod_inverse(2)
	for i in range(2, N + 1):
		y = binpow(P, i - 1, 998244353)
		y = mod_inverse(y, 998244353)
		val = (dp[i - 1] + mul(binpow(y, 2, 998244353), inv2) + mul(y, dp2[i - 1], 998244353)) % 998244353
		dp[i] = val
		dp2[i] = (dp2[i - 1] + mul(y, inv2, 998244353)) % 998244353
	print(*dp[1:])


mod = 998244353

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

def bp(a, b):
	if b == 0:
		return 1
	tmp = bp(a, b // 2)
	tmp = mul(tmp, tmp)
	if b % 2:
		return mul(tmp, a)
	return tmp

def mi(a, m=mod):
	return bp(a, m - 2)
(n, p) = map(int, input().split())
dp = [0] * (n + 1)
dp2 = [0] * (n + 1)
dp[1] = dp2[1] = mi(2)
inv2 = mi(2)
for i in range(2, n + 1):
	y = bp(p, i - 1)
	y = mi(y)
	val = dp[i - 1] + mul(bp(y, 2), inv2) + mul(y, dp2[i - 1])
	val %= mod
	dp[i] = val
	dp2[i] = (dp2[i - 1] + mul(y, inv2)) % mod
print(*dp[1:])


def binaryPow(a, b):
	if b == 0:
		return 1
	tmp = binaryPow(a, b // 2)
	tmp = modMultiply(tmp, tmp)
	if b % 2:
		return modMultiply(tmp, a)
	return tmp

def modulo1():
	return 998244353

def inverseMod(a, m=modulo1()):
	return pow(a, m - 2, m)

def modMultiply(a, b):
	return a % modulo1() * (b % modulo1()) % modulo1()
(N, P) = map(int, input().split())
DP = [0] * (N + 1)
DP2 = [0] * (N + 1)
DP[1] = DP2[1] = inverseMod(2)
inverse2 = inverseMod(2)
for i in range(2, N + 1):
	y = binaryPow(P, i - 1)
	y = inverseMod(y)
	val = DP[i - 1] + modMultiply(binaryPow(y, 2), inverse2) + modMultiply(y, DP2[i - 1])
	val %= modulo1()
	DP[i] = val
	DP2[i] = (DP2[i - 1] + modMultiply(y, inverse2)) % modulo1()
print(*DP[1:])


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

def binpow(a, b, mod=998244353):
	result = 1
	while b > 0:
		if b & 1:
			result = mul(result, a, mod)
		a = mul(a, a, mod)
		b >>= 1
	return result

def mod_inverse(a, m=998244353):
	return binpow(a, m - 2, m)

def solve():
	(N, P) = map(int, input().split())
	dp = [0 for i in range(N + 1)]
	dp2 = [0 for i in range(N + 1)]
	dp[1] = dp2[1] = mod_inverse(2)
	inv2 = mod_inverse(2)
	for i in range(2, N + 1):
		y = pow(P, i - 1, 998244353)
		y = mod_inverse(y)
		val = (dp[i - 1] + mul(pow(y, 2, 998244353), inv2) + mul(y, dp2[i - 1])) % 998244353
		dp[i] = val
		dp2[i] = (dp2[i - 1] + mul(y, inv2)) % 998244353
	for i in range(1, N + 1):
		print(dp[i], end=' ')
	print()
solve()


from functools import total_ordering
from numbers import Number
__version__ = '0.3.0'

@total_ordering
class Mod:

	def __init__(self, value, modulus):
		if not isinstance(value, Number):
			raise ValueError('Value is not a number')
		if not isinstance(modulus, Number):
			raise ValueError('Modulus is not a number')
		if modulus == 0:
			raise ValueError('Modulus value cannot be zero')
		if modulus != int(modulus):
			raise ValueError('Modulus is not an integer')
		self._modulus = int(modulus)
		self._value = int(value) % self._modulus

	def __int__(self):
		return self._value

	def __float__(self):
		return float(self._value)

	def __hash__(self):
		return hash(self._value)

	@property
	def modulus(self):
		return self._modulus

	def copy(self, modulus=None):
		return Mod(self._value, modulus if modulus else self._modulus)

	def _extended_gcd(self):
		t_value = 0
		new_t = 1
		r_value = self._modulus
		new_r = self._value
		while True:
			if new_r == 0:
				return [r_value, t_value]
			quotient = r_value // new_r
			(t_value, new_t) = (new_t, t_value - quotient * new_t)
			(r_value, new_r) = (new_r, r_value - quotient * new_r)

	@property
	def inverse(self):
		(r_value, t_value) = self._extended_gcd()
		if r_value != 1:
			raise ValueError('the value {} cannot be inverted'.format(self))
		value = t_value + (self._modulus if t_value < 0 else 0)
		return Mod(value, self._modulus)

	def __eq__(self, other):
		if not isinstance(other, Number):
			return False
		if isinstance(other, Mod):
			modulus = min((self._modulus, other._modulus))
		else:
			modulus = self._modulus
		return int(self) % modulus == int(other) % modulus

	def __lt__(self, other):
		if not isinstance(other, Number):
			return False
		if isinstance(other, Mod):
			modulus = min((self._modulus, other._modulus))
		else:
			modulus = self._modulus
		return int(self) % modulus < int(other) % modulus

	def __pos__(self):
		return self.copy()

	def __neg__(self):
		return Mod(-self._value, self._modulus)

	def _convert(self, other):
		if isinstance(other, Mod):
			if other._modulus != self._modulus:
				raise ValueError('Not same modulus: {} != {}'.format(self._modulus, other._modulus))
			return other
		if isinstance(other, int):
			return Mod(other, self._modulus)
		return None

	def __add__(self, other):
		converted = self._convert(other)
		if converted is None:
			return self._value + other
		return Mod(self._value + converted._value, self._modulus)
	__radd__ = __add__

	def __sub__(self, other):
		converted = self._convert(other)
		if converted is None:
			return self._value - other
		return Mod(self._value - converted._value, self._modulus)

	def __rsub__(self, other):
		return -self + other

	def __mul__(self, other):
		converted = self._convert(other)
		if converted is None:
			return self._value * other
		return Mod(self._value * converted._value, self._modulus)
	__rmul__ = __mul__

	def __truediv__(self, other):
		return float(self) / float(other)

	def __rtruediv__(self, other):
		return float(other) / float(self)

	def __floordiv__(self, other):
		converted = self._convert(other)
		if converted is None:
			return self._value // other
		if converted._value == 0:
			raise ZeroDivisionError('integer division by {}'.format(converted))
		inverted = other * self.inverse
		return inverted.inverse

	def __rfloordiv__(self, other):
		converted = self._convert(other)
		if converted is None:
			return other // self._value
		return converted * self.inverse

	def __pow__(self, other):
		converted = self._convert(other)
		if converted is None:
			return self._value ** other
		if isinstance(other, Mod):
			result = pow(self._value, other._value, self._modulus)
		else:
			result = pow(self._value, other, self._modulus)
		return Mod(result, self._modulus)

	def __rpow__(self, other):
		converted = self._convert(other)
		if converted is None:
			return pow(other, self._value, self._modulus)
		result = pow(converted._value, self._value, self._modulus)
		return Mod(result, self._modulus)
MOD = 998244353
(n, p) = map(int, input().split())
a = Mod(0, MOD)
b = Mod(0, MOD)
score_for_round = Mod(1, MOD)
for i in range(1, n + 1):
	a += score_for_round
	b += score_for_round * score_for_round
	result = (a * a + b) // 4
	print(int(result), end='' if i == n else ' ')
	score_for_round //= p