MOD = 998244353 class Modint: def __init__(self, x): self.x = x % MOD if x >= 0 else (x % MOD + MOD) % MOD def __add__(self, other): return Modint((self.x + other.x) % MOD) def __sub__(self, other): return Modint((self.x - other.x) % MOD) def __mul__(self, other): return Modint((self.x * other.x) % MOD) def __pow__(self, exp): result = 1 base = self.x while exp > 0: if exp & 1: result = (result * base) % MOD base = (base * base) % MOD exp >>= 1 return Modint(result) def __truediv__(self, other): return self * other.__pow__(MOD - 2) def __str__(self): return str(self.x) def solve(): n = int(input()) x = 0 if n == 1: print(1) return while (1 << x) < n: x += 1 x -= 1 m = 1 << x t = Modint(2) ** (m - 1) * m times = [0] * (x + 2) for i in range(x + 1): k = Modint(2) ** (1 << i) times[i] = (k + 1 / k) / 2 n -= 1 ans = Modint(0) tt = Modint(1) for i in range(x - 1, -1, -1): if (n >> i) & 1: t2 = tt for j in range(i - 1, -1, -1): t2 *= 1 + times[j] ans += t2 * t tt *= times[i] ans += t * tt ans += (2 ** m - 1) ans += (2 ** m - 1) ans -= (2 ** (2 * m - n - 1) - 1) print(ans) if __name__ == "__main__": solve()