Little $X$ used a divide-and-conquer algorithm to solve a sequence problem, with the code roughly as follows:

The number of operations performed by $\operatorname{Solve}(l,r)$ is exactly $\operatorname{mex}\ a[l \dots r]$, which is the smallest non-negative integer not appearing in $a[l \dots r]$. Note that in the pseudocode flow above, it is not actually possible for $\operatorname{Solve}(l,r)$ to run exactly that many times; you may assume Little $X$ performed some other operations to achieve this, and we ignore that part in this problem.

After counting the number of operations for several sets of data, Little $X$ claimed that the time complexity of this code is $O(n)$. As a master of the craft, you do not agree. Please construct a sequence $a_i$ of non-negative integers of length $n$ to maximize the number of operations of the above code, in order to shatter this novice's beautiful fantasy!

To maintain the mystery of a master, you will not tell him the sequence $a_i$; you only need to tell him the result of the maximum number of operations modulo 998244353.

Input

A single positive integer $n$ in one line. Note that for the convenience of the contestants, $n$ is represented in binary.

Output

Output a single non-negative integer in one line, representing the result of the maximum number of operations modulo 998244353.

Examples

Input 1

111

Output 1

17

Note 1

There are multiple sequences that achieve 17 operations, one of which is $\{3,2,1,0,1,0,4\}$. It can be proven that there is no scheme with more operations.

Subtasks

For all test data, $1 \le n < 2^{200000}$.

Reasonable subtask dependencies have been set.

Special Constraint A: There exists an integer $k$ such that $n = 2^k$.