#include #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto& (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)< P; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; typedef vector vd; typedef vector

vp; typedef vector vs; const int MAX_N = 100005; ll dp[20][2][2][2]; ll keta(vi& s) { dp[0][0][0][0] = 1; rep(i,len(s)){ //まだ最上位ビットが出てこない if(s[i]){ dp[i+1][0][0][1] = (dp[i][0][0][0] + dp[i][0][0][1]) % MOD; }else{ dp[i+1][0][0][0] = dp[i][0][0][0]; dp[i+1][0][0][1] = dp[i][0][0][1]; } //最上位ビットが今でた dp[i+1][1][0][1] = (dp[i+1][1][0][1] + dp[i][0][0][1]) % MOD; if(s[i]){ dp[i+1][1][0][0] = (dp[i+1][1][0][0] + dp[i][0][0][0]) % MOD; } //1ビットまだ重なっていない dp[i+1][1][0][1] = (dp[i+1][1][0][1] + 3*dp[i][1][0][1]) % MOD; if(s[i]){ dp[i+1][1][0][0] = (dp[i+1][1][0][0] + dp[i][1][0][0]) % MOD; dp[i+1][1][0][1] = (dp[i+1][1][0][1] + 2*dp[i][1][0][0]) % MOD; }else{ dp[i+1][1][0][0] = (dp[i+1][1][0][0] + 2*dp[i][1][0][0]) % MOD; } //今1ビット重なった dp[i+1][1][1][1] = (dp[i+1][1][1][1] + dp[i][1][0][1]) % MOD; if(s[i]){ dp[i+1][1][1][0] = (dp[i+1][1][1][0] + dp[i][1][0][0]) % MOD; } //確定 dp[i+1][1][1][0] = (dp[i+1][1][1][0] + 2*dp[i][1][1][0]) % MOD; dp[i+1][1][1][1] = (dp[i+1][1][1][1] + 4*dp[i][1][1][1]) % MOD; if(s[i]){ dp[i+1][1][1][1] = (dp[i+1][1][1][1] + 2*dp[i][1][1][0]) % MOD; } } return dp[len(s)][1][1][0] + dp[len(s)][1][1][1]; } int main() { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; vi s; while(n){ s.pb(n&1); n /= 2; } reverse(all(s)); cout << keta(s) << "\n"; return 0; }