In the world of k-dimension, there's a large hypersphere made by mysterious metal. People in the world of k-dimension are performing a ceremony to worship the goddess
of dimension. They are melting the large hypersphere into metal flow, and then they will cast the metal flow into unit hyperspheres. An unit hypersphere is a hypersphere which radius is 1.

The mysterious metal in k-dimension world has a miraculous property: if k unit hyperspheres made by the mysterious metal are constructed, all of these k unit
hyperspheres will be sacrificed to goddess of dimension and disappear from the k-dimension world immediately.

After the ceremony, there will be some unit hyperspheres and a little metal flow left, and people in the world of k-dimension want to know the number of unit hyperspheres left.

You might want to know that how the large hypersphere was constructed. At first, people in the world created a long ruler which length is l. And then, they drew a rectangle
with length l - 1 and width l. Using some mysterious method, they changed the rectangle into a square but didn't change the area. After that, they extended the ruler's length by the length of the square's side. After successfully made
the ruler, people started using magic to construct the large hypersphere. The magic could make a hypersphere become more and more larger. Started with a hypersphere of zero radius, the magic will be continuously used until the radius reached the ruler's length.

Input

There will be several test cases. Each test case contains two integers k (3 ≤ k ≤ 1000000000) and l (2 ≤ l ≤ 1000000000), which are the same
meanings as in the description part.

Output

For each test case, please output the number of unit hyperspheres people will get in one line.

Sample Input

3 3
5 6

Sample Output

2
1

/*
    2*l
K1=(   )
     2
*/

/*
   2*l   -l
F=(        )
	1     0
*/

/****
	*@Polo-shen
	*
	*/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
//#include <algorithm>
#include <cmath>
//#include <iomanip>
//#include <fstream>
//#include <cstdlib>
#include <vector>
//#include <list>
//#include <set>
//#include <map>

using namespace std;
typedef long long int64;

#define DBG 0
#define ShowLine DBG && cout<<__LINE__<<">>| "
#define dout DBG && cout<<__LINE__<<">>| "
#define write(x) #x" = "<<(x)<<" "
#define awrite(array,num) #array"["<<num<<"]="<<array[num]<<" "

#ifndef min
#define min(x,y) ((x) < (y) ? (x) : (y))
#endif

#ifndef max
#define max(x,y) ((x) > (y) ? (x) : (y))
#endif


const int MAXN = 3;
const int MAXM = 2;
/***
	*Title:
	*
	*/
struct Matrax{
	int n,m;
	int64 mat[MAXN][MAXM];
	Matrax():n(-1),m(-1){}
	Matrax(int _n,int _m):n(_n),m(_m){
		memset(mat,0,sizeof(mat));
	}
	void Unit(int _s){
		n=_s;m=_s;
		for (int i=0;i<n;i++){
			for (int j=0;j<n;j++){
				mat[i][j]=(i==j)?1:0;
			}
		}
	}
	void print(){
		cout<<write(n)<<write(m)<<endl;
		for (int i=0;i<n;i++){
			for (int j=0;j<m;j++){
				cout<<" "<<mat[i][j];
			}
			cout<<endl;
		}
	}
};

Matrax add_mod(const Matrax& a,const Matrax& b,const int64 mod){
	Matrax ans(a.n,a.m);
	for (int i=0;i<a.n;i++){
		for (int j=0;j<a.m;j++){
			ans.mat[i][j]=(a.mat[i][j]+b.mat[i][j])%mod;
		}
	}
	return ans;
}

Matrax mul(const Matrax& a,const Matrax& b){
	Matrax ans(a.n,b.m);
	for (int i=0;i<a.n;i++){
		for (int j=0;j<b.m;j++){
			int64 tmp=0;
			for (int k=0;k<a.m;k++){
				int64 res=a.mat[i][k]*b.mat[k][j];
				tmp+=res;
			}
			ans.mat[i][j]=tmp;
		}
	}
	return ans;
}

Matrax mul_mod(const Matrax& a,const Matrax& b,const int64 mod){
	Matrax ans(a.n,b.m);
	for (int i=0;i<a.n;i++){
		for (int j=0;j<b.m;j++){
			int64 tmp=0;
			for (int k=0;k<a.m;k++){
				tmp+=(a.mat[i][k]*b.mat[k][j])%mod;
			}
			ans.mat[i][j]=tmp%mod;
		}
	}
	return ans;
}

Matrax pow_mod(const Matrax& a,int64 k,int64 mod){
	Matrax p(a.n,a.m),ans(a.n,a.m);
	p=a;ans=a;
	ans.Unit(a.n);
	if (k==0){
		return ans;
	}
	else if (k==1){
		return a;
	}
	else {
		while (k){
			if (k&1){
				ans=mul_mod(ans,p,mod);
				k--;
			}
			else {
				k/=2;
				p=mul_mod(p,p,mod);
			}
		}
		return ans;
	}
}

void solve(int64 k,int64 l){
	/*
	   2*l   -l
	F=(        )
		1     0
	*/
	Matrax F(2,2);
	F.mat[0][0]=2*l;F.mat[0][1]=-l;
	F.mat[1][0]=1;F.mat[1][1]=0;
	//F.print();
	/*
		2*l
	K1=(   )
		 2
	*/
	Matrax K1(2,1);
	K1.mat[0][0]=2*l;
	K1.mat[1][0]=2;
	//K1.print();
	/*
		 Sn
	Kn=(    )
		Sn-1
	*/
	Matrax Kn(2,1);
	Matrax tmp(2,2);
	tmp=pow_mod(F,k-1,k);
	//tmp.print();
	Kn=mul_mod(tmp,K1,k);
	//cout<<"Kn";Kn.print();
	int64 ans=(Kn.mat[0][0]-1+k);
	cout<<(ans%k)<<endl;
	return;
}

int main(){
	int64 k,l;
	while (cin>>k>>l){
		solve(k,l);
	}
    return 0;
}