首先，既然说这道题是个数列，那肯定这个数列就有规律，我们可以按照题意来用dfs进行打表。

int ans=0;
int d;
void dfs(int a,int b,int c)//now ai and bi
{
	++ans;
	for(int i=a+1;i<=c;i++){
		if((b^i)>b) dfs(i,b^i,c);
	}
}
int main()
{
	for(int i=1;i<=100;i++){
		ans=-1;
		dfs(0,0,i);
		cout<<ans<<' ';
		if(i%10==0)
			cout<<endl;
	}
}

打出前100项的结果

1 3 5 11 17 23 29 59 89 119 
149 179 209 239 269 539 809 1079 1349 1619
1889 2159 2429 2699 2969 3239 3509 3779 4049 4319
4589 9179 13769 18359 22949 27539 32129 36719 41309 45899
50489 55079 59669 64259 68849 73439 78029 82619 87209 91799
96389 100979 105569 110159 114749 119339 123929 128519 133109 137699
142289 146879 151469 302939 454409 605879 757349 908819 1060289 1211759
1363229 1514699 1666169 1817639 1969109 2120579 2272049 2423519 2574989 2726459
2877929 3029399 3180869 3332339 3483809 3635279 3786749 3938219 4089689 4241159
4392629 4544099 4695569 4847039 4998509 5149979 5301449 5452919 5604389 5755859

然后我们可以进行差分，得到下面的结果

1 2 2 6 6 6 6 30 30 30 
30 30 30 30 30 270 270 270 270 270
270 270 270 270 270 270 270 270 270 270
270 4590 4590 4590 4590 4590 4590 4590 4590 4590
4590 4590 4590 4590 4590 4590 4590 4590 4590 4590
4590 4590 4590 4590 4590 4590 4590 4590 4590 4590
4590 4590 4590 151470 151470 151470 151470 151470 151470 151470
151470 151470 151470 151470 151470 151470 151470 151470 151470 151470
151470 151470 151470 151470 151470 151470 151470 151470 151470 151470
151470 151470 151470 151470 151470 151470 151470 151470 151470 151470

然后我们就可以看出，每$2^n$个数就能形成一个 等差数列，然后这个等差数列每$2^n$，差值就会增加$2^n+1$倍，然后我们根据这个结论，就可以推算出结果。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=1e6+10,inf=0x3f3f3f3f;
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n,m;
        scanf("%lld %lld",&n,&m);
        n+=1;
        ll sum=1;
        ll ans=0;
        ll cnt=1;
        for(int i=1;i<=62;i++)
        {
            if(n<sum*2)
            {
                ans+=(((n-(sum))%m)*(cnt%m))%m;
                break;
            }
            else
            {
                ans+=(sum%m)*(cnt%m)%m;
                cnt=((cnt%m)*((sum+1)%m))%m;
                sum*=2;
            }
        }
        cout<<ans%m<<endl;
    }
}