// Author: wlzhouzhuan
#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define mset(s,t) memset(s,t,sizeof(s))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define SZ(x) ((int)x.size())
#define pb push_back
#define eb emplace_back
#define fir first
#define sec second

template<class T1,class T2>bool ckmax(T1 &a,T2 b){if(a<b)return a=b,1;else return 0;}
template<class T1,class T2>bool ckmin(T1 &a,T2 b){if(a>b)return a=b,1;else return 0;}

inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
    return f?-x:x;
}
template<typename T>void print(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)print(x/10);
    putchar(x%10+'0');
}
template<typename T>void print(T x,char ch){
    print(x),putchar(ch);
}

const int N=1000005;
const int mod=998244353;

int dp[N],n;
int sum[N],coef;

void dfs(int bit,int pre,int i,int zip){
    if(!zip){
        // printf("pre=%d,bit=%d,i=%d\n",pre,bit,i);
        int L=pre<<bit+1,R=L+(1<<bit+1)-1;
        // printf("add range[%d,%d]\n",L,R);
        coef=(coef+1ll*sum[R]+mod-sum[L-1])%mod;
        return;
    }
    if(bit==-1)return;
    int k1=i>>bit&1;
    // 0
    {
        int nzip=zip;
        if(k1&&(nzip&1))nzip^=1;
        dfs(bit-1,2*pre,i,nzip);
    }
    // 1
    {
        int nzip=zip;
        if(!k1){
            if(nzip&2)return;
        }else{
            if(nzip&1)return;
            if(nzip&2)nzip^=2;
        }
        dfs(bit-1,2*pre+1,i,nzip);
    }
}

int main(){
    cin>>n;
    dp[1]=1,sum[1]=1;
    rep(i,2,n){
        dp[i]=sum[i-1]+1;
        // rep(j,1,i-1){
        //     if(j<(j^i)&&(j^i)<i)
        //         // dp[i]=(dp[i]-dp[j]+mod)%mod;
        //         printf("i=%d,j=%d\n",i,j);
        // }
        coef=0;
        dfs(30,0,i,3);
        dp[i]=(dp[i]+mod-coef)%mod;
        sum[i]=(sum[i-1]+dp[i])%mod;
    }
    print(sum[n],'\n');
    return 0;
}