#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)
#define int ll

using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 2000+5;
const int mod = 2147483647;
const int inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

int n, s, d[N][N];
vector<int> q[105];
vector<ii> adj[N];

void floyd() 
{
	for (int i = 1; i <= n; i++) 
	{
		for (int j = 1; j <= n; j++) 
		{
			for (int k = 1; k <= n; k++) 
			{
				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
			}
		}
	}
}

int dist[N];

void process(int s) 
{
	for (int i = 1; i <= n; i++) 
	{
		dist[i] = d[s][i];
		if (dist[i] <= 100) q[dist[i]].pb(i);
	}
	for (int i = 0; i <= 100; i++) 
	{
		while (q[i].size())
		{
			int u = q[i].back();
			q[i].pop_back();
			if (dist[u] < i) continue;
			for (auto j : adj[u]) 
			{
				int w = j.fi, v = j.se;
				if (dist[u] + w > 100) break;
				if (dist[u] + w < dist[v]) 
				{
					dist[v] = i + w;
					q[i+w].pb(v);
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) d[s][i] = dist[i];
}

void solve()
{
	cin>>n>>s;
	for (int i = 1; i <= n; i++) 
	{
		for (int j = 1; j <= n; j++) 
		{
			if (i != j) 
			{
				d[i][j] = s % 1000;
				adj[i].pb({d[i][j], j});
				s = (s * 16807) % mod;
			}
		}
	}
	if (n <= 500) floyd();
	else {
		for (int i = 1; i <= n; i++) sort(all(adj[i]));
		// for (int i = 1; i <= n; i++) {
		// 	for (auto j : adj[i]) cout<<j.fi<<" ";
		// 	cout<<endl;
		// }
		for (int i = 1; i <= n; i++) process(i);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) 
	{
		for (int j = 1; j <= n; j++) ans = (ans * 16807 + d[i][j]) % mod;
	}
	cout<<ans;
}

signed main()
{
	bruh
	freopen("floyd.in","r",stdin);
	freopen("floyd.out","w",stdout);
	int t = 1;
	// cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}