#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
class TaroCoins {
public:
    long long getNumber(long long);
    map<pair<ll,ll>,ll > dp;

    ll solve(ll n, ll maxpow){
        if(n==0) return 1LL;
        if(maxpow<0) return 0LL;
        if( (1LL<<(maxpow+2)) < n) return 0LL;
        ll& ref = dp[make_pair(n,maxpow)];
        if(ref == 0){
            ll subs = (1LL<<maxpow);
            if(n-subs>=0) ref+=solve(n-subs, maxpow-1);
            if(n-subs-subs>=0) ref+=solve(n-subs-subs, maxpow-1);
            ref+=solve(n, maxpow-1);
        }
        return ref;
    }
};

long long TaroCoins::getNumber(long long N) {
    ll startWithMe = 1;
    ll pow2 = 0;
    while(true) {
        if(startWithMe*2 > N) break;
        startWithMe *= 2;
        ++pow2;
    }
    return solve(N,pow2);
}