class BMBM:
    """
    Berlekamp-Massey 法 + Bostan-Mori 法
    https://atcoder.jp/contests/tdpc/submissions/75993697
    
    与えられた数列の最初の数項から線形漸化式を自動で推測し、
    その漸化式に従う N 項目を推測する Black Box ライブラリ。
    引数 use_ntt=True を指定することで O(K log K log N) の NTT 乗算に切り替え可能。
    """
    
    @staticmethod
    def convolution(a: list[int], b: list[int], mod: int = 998244353) -> list[int]:
        """
        mod 998244353 における高速フーリエ変換 (NTT) を用いた多項式乗算
        """
        if not a or not b:
            return []
            
        # NTTは 998244353 専用。それ以外のmodの場合は愚直O(K^2)にフォールバック
        if mod != 998244353:
            res = [0] * (len(a) + len(b) - 1)
            for i, va in enumerate(a):
                for j, vb in enumerate(b):
                    res[i+j] = (res[i+j] + va * vb) % mod
            return res

        n = 1
        while n < len(a) + len(b) - 1:
            n <<= 1
            
        A = a + [0] * (n - len(a))
        B = b + [0] * (n - len(b))
        
        def ntt(arr: list[int], inv: bool):
            j = 0
            for i in range(1, n):
                bit = n >> 1
                while j & bit:
                    j ^= bit
                    bit >>= 1
                j ^= bit
                if i < j:
                    arr[i], arr[j] = arr[j], arr[i]
                    
            step = 1
            while step < n:
                zeta = pow(3, (mod - 1) // (2 * step), mod)
                if inv:
                    zeta = pow(zeta, mod - 2, mod)
                
                w = [1] * step
                for i in range(1, step):
                    w[i] = (w[i-1] * zeta) % mod
                    
                for i in range(0, n, 2 * step):
                    for j in range(step):
                        u = arr[i + j]
                        v = (arr[i + j + step] * w[j]) % mod
                        arr[i + j] = (u + v) % mod
                        arr[i + j + step] = (u - v) % mod
                step <<= 1
                
            if inv:
                inv_n = pow(n, mod - 2, mod)
                for i in range(n):
                    arr[i] = (arr[i] * inv_n) % mod

        ntt(A, False)
        ntt(B, False)
        C = [(x * y) % mod for x, y in zip(A, B)]
        ntt(C, True)
        
        return C[:len(a) + len(b) - 1]

    @staticmethod
    def berlekamp_massey(a: list[int], mod: int) -> list[int]:
        """
        数列 a から最短の線形漸化式(分母多項式 Q)を復元する
        """
        c = [1]
        b = [1]
        L = 0
        m = 1
        b_val = 1
        for i in range(len(a)):
            d = 0
            for j in range(L + 1):
                d = (d + c[j] * a[i - j]) % mod
            if d == 0:
                m += 1
            else:
                tmp = c[:]
                c_val = (d * pow(b_val, mod - 2, mod)) % mod
                while len(c) <= len(b) + m:
                    c.append(0)
                for j in range(len(b)):
                    c[j + m] = (c[j + m] - c_val * b[j]) % mod
                if 2 * L <= i:
                    L = i + 1 - L
                    b = tmp
                    b_val = d
                    m = 1
                else:
                    m += 1
        return c[:L + 1]

    @staticmethod
    def bostan_mori(p: list[int], q: list[int], n: int, mod: int, use_ntt: bool = False) -> int:
        """
        母関数 P(x)/Q(x) の N 次の係数を求める
        """
        while n > 0:
            q_neg = [v if i % 2 == 0 else -v for i, v in enumerate(q)]
            
            if use_ntt and mod == 998244353:
                u = BMBM.convolution(p, q_neg, mod)
                v = BMBM.convolution(q, q_neg, mod)
            else:
                # 愚直 O(K^2)
                u = [0] * (len(p) + len(q) - 1)
                for i in range(len(p)):
                    pi = p[i]
                    if not pi: continue
                    for j in range(len(q)):
                        u[i + j] = (u[i + j] + pi * q_neg[j]) % mod
                        
                v = [0] * (len(q) + len(q) - 1)
                for i in range(len(q)):
                    qi = q[i]
                    if not qi: continue
                    for j in range(len(q)):
                        v[i + j] = (v[i + j] + qi * q_neg[j]) % mod
                    
            if n % 2 == 1:
                p = [u[i] for i in range(1, len(u), 2)]
            else:
                p = [u[i] for i in range(0, len(u), 2)]
                
            q = [v[i] for i in range(0, len(v), 2)]
            n //= 2
            
        return p[0] if len(p) > 0 else 0

    @classmethod
    def guess_kth_term(cls, seq: list[int], k: int, mod: int = 998244353, use_ntt: bool = False) -> int:
        """
        数列 seq の k 項目 (0-indexed) を推測して返す
        use_ntt=True で O(K log K log N) に切り替え可能
        """
        # 1. 漸化式(分母多項式 Q)を特定
        q = cls.berlekamp_massey(seq, mod)
        
        # 2. 分子多項式 P(x) = (seq(x) * Q(x)) mod x^{len(Q)-1} を計算
        if use_ntt and mod == 998244353:
            p_full = cls.convolution(seq[:len(q)-1], q, mod)
            p = p_full[:len(q)-1]
        else:
            p = [0] * (len(q) - 1)
            for i in range(len(p)):
                val = 0
                for j in range(i + 1):
                    if j < len(q) and i - j < len(seq):
                        val = (val + seq[i - j] * q[j]) % mod
                p[i] = val
            
        # 3. Bostan-Mori で k 項目へ一気に飛ぶ
        return cls.bostan_mori(p, q, k, mod, use_ntt)

from collections import deque
MOD = 998244353
N = int(input())

L = 3 * 10**5
def naive(n):
    q = deque([(0,0)])
    INF = 10**18
    dist = [INF] * (n+1)
    while(q):
        v,now = q.popleft()

        if(dist[now] <= v):continue
        dist[now] = v

        if(0 <= now+1 <= n):q.append((v+1,now+1))
        if(0 <= now-1 <= n):q.append((v+1,now-1))
        if(0 <= now*2 <= n):q.append((v+1,now*2))
    
    for i in range(n-1):
        dist[i+1] += dist[i]
    return dist

nai = naive(10**6)

if(N <= L):
    print(nai[N])
else:
    print(BMBM.guess_kth_term(nai[L:], N-L, MOD, use_ntt=True))