Background

This problem is an enhanced version of Inequality Relations. It is recommended that you solve the original problem before challenging this enhanced version.

Problem Description

Given a string $s_1,s_2,\cdots ,s_n$ consisting only of the two characters < and >.

Let $f(s)$ be the number of permutations $p_1,p_2,\cdots ,p_{n+1}$ such that $p_i<p_{i+1}$ if and only if $s_i$ is <.

Now, please compute the sum of $f(s)$ over all $2^n$ strings $s$ of length $n$.

Since the answer may be large, you only need to output the result modulo $998244353$.

Input Format

One line containing a positive integer $n$.

Output Format

One line containing an integer, representing the number of permutations satisfying the requirement modulo $998244353$.

1

2

Hint

Sample Explanation

For the string $s1=$ <, there is exactly one permutation $(1,2)$ that satisfies the requirement, so $f(s1)=1$.

For the string $s2=$ >, there is exactly one permutation $(2,1)$ that satisfies the requirement, so $f(s2)=1$.

Therefore, the answer is $f(s1)+f(s2)=2$.

Constraints

For all testdata, it is guaranteed that $1\le n\le 100$.

Translated by ChatGPT 5