#include<cstdio>#include<algorithm>#include<cstring>#include<sstream>#include<iostream>#include<cmath>#include<vector>const int MAXN = 5;typedef long long LL;using namespace std;LL mod = 1;LL l,k;struct matrix{int n,m;LL t[MAXN +10][MAXN +10];void init(){n = 0; m = 0; memset(t,0,sizeof(t));};void init_max(){memset(t,0x3f,sizeof(t));} void init_e(){init(); for(int i = 0;i < MAXN;i++) t[i][i] = 1;}matrix operator * (matrix a){matrix c;c.init();c.n = n;c.m = a.m;for(int i = 0;i < n;i++)for(int j = 0;j < a.n;j++)for(int k = 0;k < a.m;k++)c.t[i][k] = (c.t[i][k] + t[i][j] * a.t[j][k]) % mod;return c;}};matrix pow(matrix a,int k){matrix ans;ans.init_e();ans.n = a.n;ans.m = a.m;while(k){if(k & 1)ans = ans * a;a = a * a;k >>= 1;}return ans;}int main(){while(cin >> k >> l){mod = k;matrix x,ans;x.init();ans.init();ans.n = 1; ans.m = 2;ans.t[0][0] = 2 % k;ans.t[0][1] = 2*l % k;x.n = x.m = 2;x.t[0][1] = -l;x.t[1][0] = 1; x.t[1][1] = 2*l;ans = ans * pow(x,k);cout << (ans.t[0][0] - 1 + k) % k << endl;}}
