p02938 AtCoder Beginner Contest 138 - Coincidence_32045
Given are integers L and R. Find the number, modulo 10^9 + 7, of pairs of integers (x, y) (L \leq x \leq y \leq R) such that the remainder when y is divided by x is equal to y \mbox{ XOR } x.

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

* When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

* 1 \leq L \leq R \leq 10^{18}

Input

Input is given from Standard Input in the following format:


L R


Output

Print the number of pairs of integers (x, y) (L \leq x \leq y \leq R) satisfying the condition, modulo 10^9 + 7.

Examples

Input

2 3


Output

3


Input

10 100


Output

604


Input

1 1000000000000000000


Output

68038601
#include<bits/stdc++.h>

#define ll long long
using namespace std; 
ll f[64][2][2][2][2];ll l,r;ll ans1=0;int l1[64],r1[64];ll mod=1e9+7;
ll dfs(int pos,int tl,int tr,int ts,int th){
	if(pos<0) return 1;ll &ans=f[pos][tl][tr][ts][th];
	if(ans) return ans;
	
	for(int i=0;i<=1;i++){
		for(int j=0;j<=1;j++){int fs=ts,fl=tl,fr=tr,fh=th;
			if(!th&&i)if(i!=j)continue;
			if((j&i)!=j) continue;
			if(!tl&&l1[pos]>j) continue;
			if(!tr&&r1[pos]<i) continue;
			if(!ts&&j>i) continue;
			if(j<i) fs=1;if(j>l1[pos])fl=1;if(i<r1[pos])fr=1;if(j) fh=1;
			ans+=dfs(pos-1,fl,fr,fs,fh);
		}
	}ans%=mod;
	return ans;
}
int main(){
	cin>>l>>r;
	for(int i=63;i>=0;i--)
	{
		l1[i]=(bool)((1ll<<i)&l);r1[i]=(bool((1ll<<i)&r));
	}
cout<<dfs(63,0,0,0,0);
}