P10583 [Lanqiao Cup 2024 National A] XOR Paths

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$.

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

Output one line with one integer representing the answer.

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