Counting Labeled Bipartite Graphs

Given a positive integer \( n \) (with \( 1 \le n \le 10^5 \)), consider a bipartite graph on a set of \( n \) labeled vertices with a fixed bipartition: one part contains \( \lfloor n/2 \rfloor \) vertices and the other contains \( \lceil n/2 \rceil \) vertices. In such a graph, an edge can only connect a vertex in the first part to a vertex in the second part. Two graphs are considered different if their edge sets are different.

The task is to count the number of distinct such bipartite graphs modulo \( 998244353 \). Since for the fixed bipartition the only possible edges are those between the two parts, and there are exactly \( \lfloor n/2 \rfloor \times \lceil n/2 \rceil \) potential edges, the answer is

[ ;2^{\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil} \pmod{998244353}. ]

Note: Here the bipartition is fixed as described (the two parts are chosen so that their sizes differ by at most one), and thus the count is exactly the number of subsets of the edge set possible between the two parts.

inputFormat

The input consists of a single integer \( n \) (\( 1 \le n \le 10^5 \)).

outputFormat

Output a single integer: the number \( 2^{\lfloor n/2 \rfloor \cdot \lceil n/2 \rceil} \) modulo \( 998244353 \).

sample

1

1