问题描述(pair.cpp)

梦梦喜欢位运算。

对于一对数 $x,y$，如果 $x \oplus y$ 的权值和 $x$ $|$ $y$ 恰好相同，那么梦梦认为这一对数是好的。

其中 $\oplus$ 表示异或操作，$|$ 表示或运算。

熊熊给出了正整数 $N$，梦梦想知道有多少个好的数对 $(x,y)$，满足 $x,y \in [0,N]$​。

$N$ 将以二进制的形式给出，答案对 $998244353$​ 取模。

输入格式

输入共 $1$ 行，包含一个正整数 $N$，通过二进制的形式给出，不含前导零。

输出格式

输出共 $1$ 行，输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入1

10

样例输出1

7

样例解释1

好的数对有 $(0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)$。

样例输入2

111

样例输出2

27

样例输入3

1110101010101001010010101010010101001010101010010101001010011111010010101

样例输出3

974423055

评测数据规模

对于 $30\%$ 的数据，$1 \leq N < 2^{10}$。

对于 $60\%$ 的数据，$1 \leq N < 2^{1000}$​。

对于 $100\%$ 的数据，$1 \leq N < 2^{1000000}$。