wwx 的异或三角形

题目描述

wwx 最近在复习异或的知识，她突发奇想，想知道有多少 $a,b,c$ 满足以下条件：

$0 \leq a,b,c \leq n$

$a\bigoplus b,b\bigoplus c,a\bigoplus c$ 三个异或结果可以构成一个三角形（两短边之和大于第三边）

答案可能很大，所以请对 $998244353$ 取模

输入格式

输入就一个数字 $n$，表示给定的 $n$ 在 二进制 下的表示。

输出格式

输出一个整数，表示答案

数据范围

对于 $10\%$ 的数据：$0\leq n \leq 2^{10}$。 对于 $20\%$ 的数据：$0\leq n \leq 2^{20}$。 对于 $100\%$ 的数据：$0\leq n \leq 2^{200000}$。

样例输入

101

样例输出

12