小 $X$ 使用分治算法解决了一个序列问题，大致代码如下：

其中 $\operatorname{Solve}(l,r)$ 的运算次数恰好为 $\operatorname{mex}\ a[l \dots r]$，即在 $a[l \dots r]$ 中最小的未出现的非负整数。请注意，在上述伪代码流程中，实际上并不可能让 $\operatorname{Solve}(l,r)$ 只运行这么多次，你可以认为小 $X$ 经过了一些其他操作达成了这一点，本题中我们忽略这一部分。

小 $X$ 统计了几组数据下的运算次数后，扬言该代码的时间复杂度是 $O(n)$ 的。 作为一名撅世高手，你不这么认为。请你构造一个长度为 $n$ 的非负整数序列 $a_i$，最大化上述代码的运行次数，以击碎这个菜鸟美好的幻想！

为了保持一个撅世高手的神秘感，你不会告诉他这个序列 $a_i$，你只需要告诉他最大运行次数对 998244353 取模后的结果即可。

输入格式

输入一行一个正整数 $n$。注意，为了选手方便，将以二进制的形式表示 $n$。

输出格式

输出一行一个非负整数，表示最大运行次数对 $998244353$ 取模后的结果。

样例输入

111

样例输出

17

样例解释

有多个运行次数达到 17 的序列，其中一个为 $\{3,2,1,0,1,0,4\}$。可以证明没有运行次数更多的方案。

子任务

对于所有测试数据，$1 \le n < 2^{200000}$。

设置了合理的子任务依赖。

特殊性质 A: 存在整数 $k$ 使得 $n = 2^k$。