Lloyd's Operation Sequence Sum

Lloyd starts with a positive integer t which is initially either \(t=2\) or \(t=3\). In each move, he can update \(t\) in one of the following ways:

• \(t \gets t + 2^t\)
• \(t \gets t + \lfloor \log_2(t-1) \rfloor\)

Define \(f(x)\) as the minimum number of operations required to obtain \(t=x\) (starting from either 2 or 3). If \(x\) cannot be reached, then \(f(x)=0\). Given a positive integer \(n\), compute:

[ S = \sum_{i=1}^{n} f(i) \mod 998244353 ]

Note that the initial values \(2\) and \(3\) are reached with 0 operations.

inputFormat

The input consists of a single integer (n) ((1 \le n\le 10^6) or as defined by the problem constraints).

outputFormat

Output a single integer which is (S = \sum_{i=1}^{n}f(i) \mod 998244353).

sample

5

3