#include<iostream> #include<cassert> #include<atcoder/modint> using namespace std; using mint=atcoder::modint998244353; long M; mint dp[66][2]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>M; int mb=0; while(M>>mb+1)mb++; long MX=(1LL<<mb+1)-1; mint ans=mint::raw(2).pow(MX+1)-1; ans-=mint::raw(2).pow(MX-M+1)-1; dp[mb+1][0]=mint::raw(1); for(int i=mb;i>=0;i--) { for(int j=0;j<2;j++)if(dp[i+1][j].val()!=0) { for(int a=0;a<2;a++)for(int b=0;b<2;b++) { if(j==0&&(a^b)<(M>>i&1))continue; if(i==mb&&a>b)continue; int nj=j; if((a^b)>(M>>i&1))nj=1; mint coef=mint::raw(1); if(a==1)coef*=mint::raw(2).pow(1L<<i); if(b==0)coef*=mint::raw(2).pow(1L<<i); dp[i][nj]+=dp[i+1][j]*coef; } } } ans-=dp[0][1]+dp[0][0]; cout<<ans.val()<<endl; }