#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <ctime>
#include <random>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
#define pli pair<ll, int>
//#define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
#include <ext/pb_ds/assoc_container.hpp>
typedef double db;
typedef long double ldb;
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;
using namespace __gnu_pbds;
bool Mbe;

//char buf[1<<20],*p1,*p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
int read() {
	int s = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
	return f ? s : -s;
}
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(x>y)x=y;}

const int N=1000055,B=45;
ll seed,Ans,tot,val[N];
int n,s[N],sz[N*B],tr[N*B][2],pos[N],kmp[N],tmp[60],ans[60];

bool Med;
signed main() {
	fprintf(stderr,"%.3lfMb\n",(&Mbe-&Med)/1024./1024.);
	n=read(),seed=read();
	rep(i,1,n)s[i]=(seed=(seed*13331+23333)%1000000007)&1;
	per(i,n,1){
		ll now=0;
		rep(j,i,i+B-1){
			now=now<<1|s[j];
		}
		val[i]=now;
	}
	per(i,n,1){
		memset(ans,0,sizeof ans);
		int lim=min(n-i+1,B),now=0;
		int t=0;
		rep(j,i,i+lim-1)tmp[++t]=s[j];
		kmp[1]=0;
		for(int j=2,k=0;j<=t;j++){
			while(k&&s[i+k]!=s[i+j-1])k=kmp[k];
			kmp[j]=(k+=(s[i+k]==s[i+j-1]));
		}
		rep(j,i,i+lim-1){
			if(!tr[now][s[j]])tr[now][s[j]]=++tot;
			now=tr[now][s[j]];
			pos[j]=now;
			ans[j-i+1]+=sz[now];
			if(kmp[j-i+1])ans[kmp[j-i+1]]-=sz[now];
		}
		rep(j,i,i+lim-1)sz[pos[j]]++;
		rep(j,1,lim)Ans+=(ll)j*ans[j];
	}
	printf("%lld\n",Ans);
	return 0;
}