Problem Description

Given a tree with $n$ nodes, numbered from $1$ to $n$. For each node with index $x > 1$, there is an edge to the node with index $\lfloor \sqrt x \rfloor$, and the edge weight is $x-\lfloor \sqrt x \rfloor ^ 2$.

Define the value of a path as the XOR sum of the weights of all edges on this path. If two paths contain different edges, they are considered different paths. Find the product of the values of all essentially different simple paths in this tree (excluding those with value $0$), and output the answer modulo $998\ 244\ 353$.

Input Format

The input contains one line with one integer $n$.

Output Format

Output one line with one integer representing the answer.

5

36

Hint

For $40\%$ of the testdata, $n\le 10^3$.
For $70\%$ of the testdata, $n\le 10^6$.
For all testdata, $1\le n\le 10^9$.

Translated by ChatGPT 5