Problem Description

数对 $(x,y)$ 是好的，当且仅当 $x \oplus y = x$ $|$ $y$，其中 $\oplus$ 表示异或操作，$|$ 表示或运算。

给定正整数 $N$，请你求解有多少个好的数对 $(x,y)$，满足 $x,y \in [0,N]$​。

因为出题人小 $M$ 比较仁慈，所以 $N$ 将以二进制的形式给出。

答案对 $998244353$​ 取模。

Input

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


#### 评测数据规模：

对于所有测评数据，$1 \leq N<2^{1234567}$。

Output

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

111

27