給定一棵有 n 個結(jié)點(diǎn)的樹，結(jié)點(diǎn) 1 至 n 編號。編號為 x > 1 的結(jié)點(diǎn)與編號為 ?√x? 的結(jié)點(diǎn)有一條權(quán)值為 x ? ? √x?² 的邊。

定義一條路徑的價值為這條路徑上的所有邊的權(quán)值的異或和。如果兩條路徑包含不同的邊，則認(rèn)為這兩條路徑不同。求這棵樹的所有本質(zhì)不同的簡單路的價值的乘積（價值為 0 的除外），答案對 998244353 取模。

輸入一行包含一個整數(shù) n 。

輸出一行包含一個整數(shù)表示答案。

5

36

【評測用例規(guī)模與約定】

對于 40% 的評測用例，n ≤ 10³ ；

對于 70% 的評測用例，n ≤ 10⁶ ；

對于所有評測用例，1 ≤ n ≤ 10⁹ 。