该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

1. $0 \leq a,b,c \leq n$
2. $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