Counting Paths in a XOR-Defined Directed Graph

You are given 2ⁿ nodes numbered from 1 to 2ⁿ. A directed edge exists from node x to node y if and only if

\(x > y \quad \text{and} \quad x \oplus y = 2^k,\;\; k\in [0,n)\),

where \(\oplus\) denotes the bitwise XOR and \(k\) is an integer.

Let \(f_{x,y}\) be the number of distinct paths from node x to node y (for \(x \neq y\)). You are to compute:

\[ \sum_{i=1}^{2^n}\sum_{j=1}^{2^n} f_{i,j} \quad (i \neq j) \mod 998244353. \]

Explanation: Notice that there is an edge from x to y if and only if there exists some \(k\in [0,n)\) such that the \(k\)th bit of x is 1 and y equals \(x-2^k\) (provided that \(y \ge 1\)). Therefore every path starting from a node x corresponds to turning off one or more of the set bits in its binary representation (in any order) without turning off all of them (since that would result in 0, which is not a valid node).

inputFormat

The only line of input contains a single integer \(n\) (1 \(\le\) n \(\le\) some small bound), meaning that the nodes are numbered from 1 to \(2^n\).

outputFormat

Output a single integer representing the sum of \(f_{i,j}\) for all \(i\neq j\) modulo 998244353.

sample

1

0