//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define file "o"
#define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
#define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
#define nl "\n"
#define ss " "
//#define pb push_back
#define pb emplace_back
#define fi first
#define se second
#define sz(s) (int)s.size()
#define all(s) (s).begin(), (s).end()
#define ms(a,x) memset(a, x, sizeof (a))
#define cn continue
#define re exit(0)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
const int mod=1e9+7;
const int maxn=3e5+15;
const int maxm=4*maxn+15;
const ll inf=1e17;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll ran(ll l, ll r)
{
return uniform_int_distribution<ll> (l, r)(rng);
}
inline void rf(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
if(fopen(file".inp","r")){
freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
}
}
template<typename T> inline void add(T &x, const T &y)
{
x+=y;
if(x>=mod) x-=mod;
if(x<0) x+=mod;
}
template<typename T> inline bool maxi(T &a, T b)
{
if(a>=b) return 0;
a=b; return 1;
}
template<typename T> inline bool mini(T &a, T b)
{
if(a<=b) return 0;
a=b; return 1;
}
int n;
string s, curxor, lim;
ll f[70][2][2];
string dec(ll x)
{
if(x==0) return "0";
string ans="";
while(x) ans+=char(x%10+48), x/=10;
reverse(all(ans));
return ans;
}
string bin(ll x)
{
if(x==0) return "0";
string ans="";
while(x) ans+=char(x%2+48), x/=2;
while(ans.size()<60) ans+='0';
reverse(all(ans));
return ans;
}
ll cal(int id, bool smaller1, bool smaller2)
{
ll &cur=f[id][smaller1][smaller2];
if(id==n) return cur=1;
if(cur+1) return cur;
cur=0;
int i=curxor[id]-'0';
if(smaller1 || i<=(s[id]-'0')) if(smaller2 || (0<=lim[id]-'0'))
{
cur+=cal(id+1, smaller1 || i<(s[id]-'0'), smaller2 || (0<lim[id]-'0'));
}
i=1-i;
if(smaller1 || i<=(s[id]-'0')) if(smaller2 || (1<=lim[id]-'0'))
{
cur+=cal(id+1, smaller1 || i<(s[id]-'0'), smaller2 || (1<lim[id]-'0'));
}
return cur;
}
signed main()
{
rf();
ll x, l, r, limit; cin>>x>>l>>r>>limit;
curxor=bin(x); lim=bin(limit);
ms(f, -1); s=bin(r); n=sz(s);
ll ans=cal(0, 0, 0);
ms(f, -1); s=bin(l-1); n=sz(s);
ans-=cal(0, 0, 0);
cout<<ans;
re;
}
Ly8jcHJhZ21hIEdDQyBvcHRpbWl6ZSgiT2Zhc3QsdW5yb2xsLWxvb3BzIikKLy8jcHJhZ21hIEdDQyB0YXJnZXQoImF2eDIsdHVuZT1uYXRpdmUiKQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgZmlsZSAibyIKI2RlZmluZSBmZihpLCBhLCBiKSBmb3IoYXV0byBpPShhKTsgaTw9KGIpOyArK2kpCiNkZWZpbmUgZmZyKGksIGIsIGEpIGZvcihhdXRvIGk9KGIpOyBpPj0oYSk7IC0taSkKI2RlZmluZSBubCAiXG4iCiNkZWZpbmUgc3MgIiAiCi8vI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBwYiBlbXBsYWNlX2JhY2sKI2RlZmluZSBmaSBmaXJzdAojZGVmaW5lIHNlIHNlY29uZAojZGVmaW5lIHN6KHMpIChpbnQpcy5zaXplKCkKI2RlZmluZSBhbGwocykgKHMpLmJlZ2luKCksIChzKS5lbmQoKQojZGVmaW5lIG1zKGEseCkgbWVtc2V0KGEsIHgsIHNpemVvZiAoYSkpCiNkZWZpbmUgY24gY29udGludWUKI2RlZmluZSByZSBleGl0KDApCgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIHZlY3RvcjxpbnQ+IHZpOwp0eXBlZGVmIHZlY3RvcjxsbD4gdmxsOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+IHBpaTsKdHlwZWRlZiBwYWlyPGxsLCBsbD4gcGxsOwp0eXBlZGVmIHZlY3RvcjxwaWk+IHZwaWk7CnR5cGVkZWYgdmVjdG9yPHBsbD4gdnBsbDsKCmNvbnN0IGludCBtb2Q9MWU5Kzc7CmNvbnN0IGludCBtYXhuPTNlNSsxNTsKY29uc3QgaW50IG1heG09NCptYXhuKzE1Owpjb25zdCBsbCBpbmY9MWUxNzsKCm10MTk5MzdfNjQgcm5nKGNocm9ubzo6c3RlYWR5X2Nsb2NrOjpub3coKS50aW1lX3NpbmNlX2Vwb2NoKCkuY291bnQoKSk7CmxsIHJhbihsbCBsLCBsbCByKQp7CiAgICByZXR1cm4gdW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPGxsPiAobCwgcikocm5nKTsKfQoKaW5saW5lIHZvaWQgcmYoKXsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShudWxscHRyKTsgY291dC50aWUobnVsbHB0cik7CiAgICBpZihmb3BlbihmaWxlIi5pbnAiLCJyIikpewogICAgICAgIGZyZW9wZW4oZmlsZSIuaW5wIiwiciIsc3RkaW4pOyBmcmVvcGVuKGZpbGUiLm91dCIsInciLHN0ZG91dCk7CiAgICB9Cn0KCnRlbXBsYXRlPHR5cGVuYW1lIFQ+IGlubGluZSB2b2lkIGFkZChUICZ4LCBjb25zdCBUICZ5KQp7CiAgICB4Kz15OwogICAgaWYoeD49bW9kKSB4LT1tb2Q7CiAgICBpZih4PDApIHgrPW1vZDsKfQoKdGVtcGxhdGU8dHlwZW5hbWUgVD4gaW5saW5lIGJvb2wgbWF4aShUICZhLCBUIGIpCnsKICAgIGlmKGE+PWIpIHJldHVybiAwOwogICAgYT1iOyByZXR1cm4gMTsKfQoKdGVtcGxhdGU8dHlwZW5hbWUgVD4gaW5saW5lIGJvb2wgbWluaShUICZhLCBUIGIpCnsKICAgIGlmKGE8PWIpIHJldHVybiAwOwogICAgYT1iOyByZXR1cm4gMTsKfQoKaW50IG47CnN0cmluZyBzLCBjdXJ4b3IsIGxpbTsKbGwgZls3MF1bMl1bMl07CgpzdHJpbmcgZGVjKGxsIHgpCnsKICAgIGlmKHg9PTApIHJldHVybiAiMCI7CiAgICBzdHJpbmcgYW5zPSIiOwogICAgd2hpbGUoeCkgYW5zKz1jaGFyKHglMTArNDgpLCB4Lz0xMDsKICAgIHJldmVyc2UoYWxsKGFucykpOwogICAgcmV0dXJuIGFuczsKfQoKc3RyaW5nIGJpbihsbCB4KQp7CiAgICBpZih4PT0wKSByZXR1cm4gIjAiOwogICAgc3RyaW5nIGFucz0iIjsKICAgIHdoaWxlKHgpIGFucys9Y2hhcih4JTIrNDgpLCB4Lz0yOwogICAgd2hpbGUoYW5zLnNpemUoKTw2MCkgYW5zKz0nMCc7CiAgICByZXZlcnNlKGFsbChhbnMpKTsKICAgIHJldHVybiBhbnM7Cn0KCmxsIGNhbChpbnQgaWQsIGJvb2wgc21hbGxlcjEsIGJvb2wgc21hbGxlcjIpCnsKICAgIGxsICZjdXI9ZltpZF1bc21hbGxlcjFdW3NtYWxsZXIyXTsKICAgIGlmKGlkPT1uKSByZXR1cm4gY3VyPTE7CiAgICBpZihjdXIrMSkgcmV0dXJuIGN1cjsKICAgIGN1cj0wOwogICAgaW50IGk9Y3VyeG9yW2lkXS0nMCc7CiAgICBpZihzbWFsbGVyMSB8fCBpPD0oc1tpZF0tJzAnKSkgaWYoc21hbGxlcjIgfHwgKDA8PWxpbVtpZF0tJzAnKSkKICAgIHsKICAgICAgICBjdXIrPWNhbChpZCsxLCBzbWFsbGVyMSB8fCBpPChzW2lkXS0nMCcpLCBzbWFsbGVyMiB8fCAoMDxsaW1baWRdLScwJykpOwogICAgfQogICAgaT0xLWk7CiAgICBpZihzbWFsbGVyMSB8fCBpPD0oc1tpZF0tJzAnKSkgaWYoc21hbGxlcjIgfHwgKDE8PWxpbVtpZF0tJzAnKSkKICAgIHsKICAgICAgICBjdXIrPWNhbChpZCsxLCBzbWFsbGVyMSB8fCBpPChzW2lkXS0nMCcpLCBzbWFsbGVyMiB8fCAoMTxsaW1baWRdLScwJykpOwogICAgfQogICAgcmV0dXJuIGN1cjsKfQoKc2lnbmVkIG1haW4oKQp7CiAgICByZigpOwogICAgbGwgeCwgbCwgciwgbGltaXQ7IGNpbj4+eD4+bD4+cj4+bGltaXQ7CiAgICBjdXJ4b3I9YmluKHgpOyBsaW09YmluKGxpbWl0KTsKICAgIG1zKGYsIC0xKTsgcz1iaW4ocik7IG49c3oocyk7CiAgICBsbCBhbnM9Y2FsKDAsIDAsIDApOwogICAgbXMoZiwgLTEpOyBzPWJpbihsLTEpOyBuPXN6KHMpOwogICAgYW5zLT1jYWwoMCwgMCwgMCk7CiAgICBjb3V0PDxhbnM7CiAgICByZTsKfQ==