P10583 [蓝桥杯 2024 国 A] 异或路径

给定一棵有 $n$ 个结点的树，结点 $1$ 至 $n$ 编号。编号为 $x > 1$ 的结点与编号为 $\lfloor \sqrt x \rfloor$ 的结点有一条权值为 $x-\lfloor \sqrt x \rfloor ^ 2$ 的边。 定义一条路径的价值为这条路径上的所有边的权值的异或和。如果两条路径包含不同的边，则认为这两条路径不同。求这棵树的所有本质不同的简单路的价值的乘积（价值为 $0$ 的除外），答案对 $998\ 244\ 353$ 取模。

输入一行包含一个整数 $n$。

输出一行包含一个整数表示答案。

对于 $40\%$ 的评测用例，$n\le 10^3$； 对于 $70\%$ 的评测用例，$n\le 10^6$； 对于所有评测用例，$1\le n\le 10^9$。