Sum of LCA Values in a Complete Binary Tree

You are given a complete binary tree defined as follows. The tree is a rooted binary tree with infinitely many nodes. The root has label \(1\). For every node with label \(x (x\ge1)\), its left child has label \(2x\) and its right child has label \(2x+1\).

For a given natural number \(k\), let \(n=2^k-1\). Consider only the nodes with labels in the range \([1,n]\) (which form a perfect binary tree of height \(k\)). For every ordered pair of nodes \((i,j)\) where \(1\le i,j\le n\) (nodes may be the same), let \(\mathrm{LCA}(i,j)\) denote the label of the lowest common ancestor of nodes \(i\) and \(j\). Compute the sum:

\[ S=\sum_{i=1}^n \sum_{j=1}^n \mathrm{LCA}(i,j)\]

Output the value of \(S\) modulo \(998244353\).

Note: It is guaranteed that \(n\) is of the form \(2^k-1\) for some natural number \(k\).

inputFormat

The input consists of a single line containing one integer \(n\) (\(n=2^k-1\) for some natural number \(k\)).

outputFormat

Output a single integer representing the sum \(S=\sum_{i=1}^n \sum_{j=1}^n \mathrm{LCA}(i,j)\) modulo \(998244353\).

sample

1

1