Xiaoming is a little kid who loves eating candy and sleeping.

Because eating too much candy can cause cavities, Xiaoming has made an $$$n$$$-day candy-eating plan for himself.

Xiaoming gets sad when he can't eat candy, so he uses a mood level to represent his mood each day. On day $$$0$$$, his mood is $$$0$$$.

Xiaoming's candy-eating plan is described by a string $$$s$$$ of length $$$n$$$ containing only $$$\texttt{01}$$$. For the $$$i$$$-th day of the plan:

• If $$$s_i=\texttt{1}$$$, it means Xiaoming will eat a piece of candy on the $$$i$$$-th day, and his mood will increase by $$$1$$$;
• If $$$s_i=\texttt{0}$$$, it means Xiaoming will not eat candy on the $$$i$$$-th day to prevent cavities, and his mood will decrease by $$$1$$$.

Xiaoming believes that the higher his mood, the more perfect the plan is. Therefore, the perfection of the plan is defined as the maximum mood level he reaches during days $$$0$$$ to $$$n$$$.

However, since Xiaoming is a sleepy little kid, each day he has a $$$\dfrac{1}{2}$$$ probability of sleeping and skipping his plan for the day, and a $$$\dfrac{1}{2}$$$ probability of following the plan as usual.

If Xiaoming chooses to sleep on a certain day, he will not eat candy, and his mood will remain unchanged.

Xiaoming's decisions each day are independent (sleeping or following the plan). Please help him calculate the expected perfection of the plan.

Since the answer may not be an integer, you only need to output the answer modulo $$$998244353$$$.

Specifically, the answer can always be expressed as a rational number $$$\dfrac{p}{q}$$$, where $$$p,q$$$ are coprime, and $$$q$$$ is not a multiple of $$$998244353$$$.

You need to find the unique integer $$$x$$$ satisfying $$$x\times q\equiv 1\pmod {998244353}$$$, and then output the value of $$$xp\bmod 998244353$$$.