Product of Non‐Zero XOR Path Values in a Special Tree

You are given a tree with n nodes numbered from 1 to n. For every node with index x > 1, there is an edge connecting node x with node \(\lfloor \sqrt{x} \rfloor\) with weight
\[ w(x)= x-\lfloor \sqrt{x} \rfloor^2. \]

For any simple path in this tree (i.e. a path in which no node is repeated), define its value as the XOR-sum of all edge weights along the path. (Two paths are considered different if the sets of edges they contain are different even if the XOR value is the same.)

Your task is to compute the product of the values of all simple paths in the tree, excluding those whose XOR value is 0. Since the answer can be very large, output it modulo \(998\,244\,353\).

Note: In a tree there is exactly one simple path between any two distinct nodes. Thus you are effectively taking the product over all unordered pairs \((u,v)\) with \(1 \le u < v \le n\) for which \(A(u)\) XOR \(A(v)\) is nonzero, where \(A(x)\) is defined as the XOR of edge weights on the unique path from node 1 to node \(x\) (with \(A(1)=0\)). In other words, for every pair of nodes \(u,v\) with \(A(u)\ne A(v)\) the contribution is \(A(u) \oplus A(v)\), and pairs with \(A(u)=A(v)\) (which yield 0) are skipped.

Hint: Notice that if you compute \(A(x)\) for each node, then for any two nodes \(u\) and \(v\) the XOR value of the path between them is \(A(u)\oplus A(v)\). Group the nodes by their \(A(\cdot)\) values. For two different groups with values \(a\) and \(b\) with frequencies \(f(a)\) and \(f(b)\), the contribution from all pairs between these groups is \((a\oplus b)^{f(a)\cdot f(b)}\).

inputFormat

The input consists of a single integer n (\(1 \le n\le 10^5\)) representing the number of nodes in the tree.

outputFormat

Output a single integer, the product of the XOR values of all simple paths (excluding those whose value equals 0) modulo \(998\,244\,353\).

sample

1

1