#include using namespace std; const long long MOD = 998244353; const long long HALF = 499122177; int main(){ long long M; cin >> M; if (M == 1){ cout << 1 << endl; } else { int p = 64 - __builtin_clzll(M - 1); vector POW(p + 1); vector POW_HALF(p + 1); POW[0] = 2; POW_HALF[0] = HALF; for (int i = 0; i < p; i++){ POW[i + 1] = POW[i] * POW[i] % MOD; POW_HALF[i + 1] = POW_HALF[i] * POW_HALF[i] % MOD; } long long ans = POW[p]; long long tmp = 1; for (int i = 0; i < p; i++){ if (((((long long) 1 << p) - M) >> i & 1) == 1){ tmp *= POW[i]; tmp %= MOD; } } ans += MOD - tmp; vector> dp(p + 1, vector(4, 0)); dp[p][0] = POW[p] * HALF % MOD; for (int i = p - 1; i >= 0; i--){ for (int j = 0; j < 4; j++){ for (int c = 0; c < 2; c++){ for (int d = 0; d < 2; d++){ bool ok = true; int j2 = j; if ((j & 1) == 0 && c == 1 && d == 0){ ok = false; } if (c == 0 && d == 1){ j2 |= 1; } if ((j & 2) == 0 && ((M - 1) >> i & 1) == 1 && c == d){ ok = false; } if (((M - 1) >> i & 1) == 0 && c != d){ j2 |= 2; } if (ok){ if (c == d){ dp[i][j2] += dp[i + 1][j]; } if (c == 1 && d == 0){ dp[i][j2] += dp[i + 1][j] * POW[i]; } if (c == 0 && d == 1){ dp[i][j2] += dp[i + 1][j] * POW_HALF[i]; } dp[i][j2] %= MOD; } } } } } ans += MOD - dp[0][2]; ans += MOD - dp[0][3]; ans %= MOD; cout << ans << endl; } }