小 $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}$。
设置了合理的子任务依赖。
| 子任务编号 | $n <$ | 特殊限制 | 分值 |
|---|---|---|---|
| 1 | 8 | 无 | 10 |
| 2 | 128 | 10 | |
| 3 | 262144 | 20 | |
| 4 | $2^{200}$ | A | 5 |
| 5 | 无 | 5 | |
| 6 | $2^{2000}$ | A | 5 |
| 7 | 无 | 10 | |
| 8 | $2^{200000}$ | A | 10 |
| 9 | 无 | 25 |
特殊性质 A: 存在整数 $k$ 使得 $n = 2^k$。