Minimum Operations on Fractions

Define a function \( f(x) \) as follows:

Consider a fraction \( \frac{0}{x} \) (with denominator given by \( x \)). You are allowed to perform the following two operations until the fraction becomes \( 1 \) (i.e. \( \frac{1}{1} \), in reduced form):

1. Add \( 1 \) to the numerator. Then, if the fraction can be simplified, reduce it to lowest terms.
2. Add \( 1 \) simultaneously to both the numerator and the denominator. Then, if the fraction can be simplified, reduce it to lowest terms.

Let \( f(x) \) be the minimum number of operations required to transform \( \frac{0}{x} \) into \( 1 \). Given an integer \( n \), compute \[ S(n)=\sum_{i=1}^{n} f(i) \bmod 998244353. \]

Observation: It can be shown that for every \( x\ge1 \), we have \[ f(x)=1+\lceil\log_2 x\rceil, \quad \text{with } f(1)=1. \] Thus the answer can be reformulated as \[ S(n)=\sum_{i=1}^{n} \Bigl(1+\lceil\log_2 i\rceil\Bigr) \bmod 998244353. \]

For example, when \( n=4 \): \[ f(1)=1,\quad f(2)=2,\quad f(3)=3,\quad f(4)=3, \quad \text{so } S(4)=1+2+3+3=9. \]

inputFormat

The input consists of a single line containing one integer \( n \) (\( 1\le n \le 10^{12} \) or similar constraints).

outputFormat

Output a single integer: \( S(n) \) modulo \( 998244353 \).

sample

1

1