48分 求改。

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
#define MIN_LONGLONG -9223372036854775808
#define MAX_LONGLONG 9223372036854775807
#define MAX_UNSIGNEDLONGLONG 18446744073709551615
#define uint unsigned long long
#define int long long
#define re register


/*
#define LOCAL
namespace ly{
    namespace IO{
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr{
            template<typename type>
            inline type read(type &x){
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x){
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;
*/


#define LOCAL
namespace ly{
    namespace IO{
        #ifndef LOCAL
            constexpr auto maxn = 1 << 20;
            char in[maxn], out[maxn], *p1 = in, *p2 = in, *p3 = out;
            #define getchar() (p1 == p2 && (p2 = (p1 = in) + fread(in, 1, maxn, stdin), p1 == p2) ? EOF : *p1++)
            #define flush() (fwrite(out, 1, p3-out, stdout))
            #define putchar(x) (p3 == out + maxn && (flush(), p3 = out), *p3++ = (x))
            class Flush {public : ~Flush() { flush(); } }_;
        #endif
        namespace usr{
            template <typename type>
            inline type read(type &x){
                x = 0;
				bool flag(0);
				char ch = getchar();
                while(!isdigit(ch)) flag ^= ch == '-', ch = getchar();
                while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
                return flag ? x = -x : x;
            }
            template<typename type>
            inline void write(type x){
                x < 0 ? x = -x, putchar('-') : 0;
                static short Stack[50], top(0);
                do Stack[++top] = x % 10, x /= 10;
				while(x);
                while(top) putchar(Stack[top--] | 48);
            }
            inline char read(char &x){ do x = getchar(); while(isspace(x)); return x; }
            inline char write(const char &x){ return putchar(x); }
            inline void read(char *x){ static char ch; read(ch); do *(x++) = ch; while(!isspace(ch = getchar()) && ~ch); }
            template <typename type>
			inline void write(type *x){ while(*x) putchar(*(x++)); }
            inline void read(string &x){ static char ch; read(ch), x.clear(); do x += ch; while(!isspace(ch = getchar()) && ~ch); }
            inline void write(const string &x){ for(int i = 0, len = x.length(); i < len; ++i) putchar(x[i]); }
            template <typename type, typename...T>
			inline void read(type &x, T&...y){ read(x), read(y...); }
            template <typename type, typename...T>
            inline void write(const type &x, const T&...y){ write(x), putchar(' '), write(y...), sizeof...(y) ^ 1 ? 0 : putchar('\n'); }
            template <typename type>
            inline void put(const type &x, bool flag = 1){ write(x), flag ? putchar('\n') : putchar(' '); }
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }
    using namespace IO :: usr;
}
using namespace ly :: IO :: usr;


inline void merge(vector<int>& v, int left, int mid, int right){
	vector<int> temp = v;
	int i = left, j = mid + 1;
	int index = left;
	while(i <= mid || j <= right){
		if(i > mid){
			v[index++] = temp[j];
			j++;
		}
		else if(j > right){
			v[index++] = temp[i];
			i++;
		}
		else if(temp[i] < temp[j]){
			v[index++] = temp[i];
			i++;
		}
		else{
			v[index++] = temp[j];
			j++;
		}
	}
}
inline void merge_Sort(vector<int>& v, int left, int right){
	if(left >= right) return;
	int mid = (left + right) / 2;
	merge_Sort(v, left, mid);
	merge_Sort(v, mid + 1, right);
	if(v[mid] > v[mid + 1]){
		merge(v, left, mid, right);
	}
}
inline void mergeSort(vector<int>& v){
	int n = v.size();
	merge_Sort(v, 0, n - 1);
}


inline void quick_Sort(vector<int>& v, int left, int right){
	if(left >= right) return;
	int i = left, j = right, base = v[left];
	while(i < j){
		while(v[j] >= base && i < j){
			j--;
		}
		while(v[i] <= base && i < j){
			i++;
		}
		if(i < j){
			swap(v[i], v[j]);
		}
	}
	v[left] = v[i];
	v[i] = base;
	quick_Sort(v, left, i - 1);
	quick_Sort(v, i + 1, right);
}
inline void quickSort(vector<int>& v){
	int n = v.size();
	quick_Sort(v, 0, n - 1);
}


inline void max_heapify(vector<int>& arr, int start, int end) {
	int dad = start;
	int son = dad * 2 + 1;
	while (son <= end) {
	    if (son + 1 <= end && arr[son] < arr[son + 1])
	        son++;
	    if (arr[dad] > arr[son])
		    return;
		else {
		    swap(arr[dad], arr[son]);
		    dad = son;
		    son = dad * 2 + 1;
		}
	}
}
inline void heap_sort(vector<int>& arr, int len) {
	for (int i = len / 2 - 1; i >= 0; i--)
	    max_heapify(arr, i, len - 1);
	for (int i = len - 1; i > 0; i--) {
		swap(arr[0], arr[i]);
		max_heapify(arr, 0, i - 1);
	}
}


inline int maxbit(vector <int>& data, int n){
	int maxData = data[0];
	for (int i = 1; i < n; ++i){
	    if (maxData < data[i])maxData = data[i];
	}
	int d = 1;
	int p = 10;
	while (maxData >= p){
		//p *= 10;
		maxData /= 10;
		++d;
	}
	return d;
/*    int d = 1;
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
	    {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
inline void radixsort(vector <int>& data, int n){
	int d = maxbit(data, n);
	int *tmp = new int[n];
	int *count = new int[10];
	int i, j, k;
	int radix = 1;
	for(i = 1; i <= d; i++) {
		for(j = 0; j < 10; j++)
		    count[j] = 0;
		for(j = 0; j < n; j++){
		    k = (data[j] / radix) % 10;
		    count[k]++;
		}
		for(j = 1; j < 10; j++)count[j] = count[j - 1] + count[j];
		for(j = n - 1; j >= 0; j--){
		    k = (data[j] / radix) % 10;
		    tmp[count[k] - 1] = data[j];
		    count[k]--;
		}
		for(j = 0; j < n; j++) data[j] = tmp[j];
		radix = radix * 10;
	}
	delete []tmp;
	delete []count;
}


/*
vector <int> tmp;
inline int winner(int pos1, int pos2, int n) {
  	int u = pos1 >= n ? pos1 : tmp[pos1];
  	int v = pos2 >= n ? pos2 : tmp[pos2];
  	if (tmp[u] <= tmp[v]) return u;
  	return v;
}
inline void creat_tree(int &value, vector <int>& a, int n) {
  	for (int i = 0; i < n; i++) tmp[n + i] = a[i];
  	for (int i = 2 * n - 1; i > 1; i -= 2) {
    	int k = i / 2;
    	int j = i - 1;
    	tmp[k] = winner(i, j, n);
  	}
  	value = tmp[tmp[1]];
  	tmp[tmp[1]] = 0x7fffffff;
}
inline void recreat(int &value, int n) {
  	int i = tmp[1];
  	while (i > 1) {
    	int j, k = i / 2;
    	if (i % 2 == 0 && i < 2 * n - 1)
    	j = i + 1;
    	else
    	j = i - 1;
    	tmp[k] = winner(i, j, n);
    	i = k;
  	}
  	value = tmp[tmp[1]];
  	tmp[tmp[1]] = 0x7fffffff;
}
inline void tournament_sort(vector <int>& a, int n) {
  	int value = 0;
  	creat_tree(value, a, n);
  	for (int i = 1; i <= n; i++) {
    	a[i] = value;
    	recreat(value, n);
  	}
}
*/


const int RUN = 64;
inline void insertionSort(vector <int>& arr, int left, int right) {
	for (int i = left + 1; i <= right; i++) {
		int temp = arr[i];
		int j = i - 1;
		while (j >= left && arr[j] > temp) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = temp;
	}
}
inline void Merge(vector <int>& arr, int l, int m, int r) {
	int len1 = m - l + 1, len2 = r - m;
	int left[len1], right[len2];
	for (int i = 0; i < len1; i++)
		left[i] = arr[l + i];
	for (int i = 0; i < len2; i++)
		right[i] = arr[m + 1 + i];
	int i = 0;
	int j = 0;
	int k = l;
	while (i < len1 && j < len2) {
		if (left[i] <= right[j]) {
			arr[k] = left[i];
			i++;
		}
		else {
			arr[k] = right[j];
			j++;
		}
		k++;
	}
	while (i < len1) {
		arr[k] = left[i];
		k++;
		i++;
	}
	while (j < len2) {
		arr[k] = right[j];
		k++;
		j++;
	}
}
inline void timSort(vector <int>& arr, int n) {
	for (int i = 0; i < n; i += RUN) {
		insertionSort(arr, i, min((i + RUN - 1), (n - 1)));
		for (int size = RUN; size < n; size = 2 * size) {
			for (int left = 0; left < n; left += 2 * size) {
				int mid = left + size - 1;
				int right = min((left + 2 * size - 1), (n - 1));
				if (mid < right)
				Merge(arr, left, mid, right);
			}
		}
	}
}


inline void CocktailSort(vector <int>& vec){
    int length = vec.size();
    if(length <= 1){
        return ;
    }
    else{
        bool isSorted = true;
        int frontSortBorder = 0;
        int backSortBorder = length - 1;
        int lastExchangeIndex = 0;
        while(frontSortBorder < backSortBorder){
            for(int i = frontSortBorder; i < backSortBorder; ++i){
                if(vec[i] > vec[i + 1]){
                    swap(vec[i], vec[i + 1]);
                    lastExchangeIndex = i;
                    isSorted = false;
                }
            }
            if(isSorted){
                break;
            }
            else{
                backSortBorder = lastExchangeIndex;
            }
            isSorted = true;
            for(int i = backSortBorder; i > frontSortBorder; --i){
                if(vec[i] < vec[i - 1]){
                    swap(vec[i], vec[i - 1]);
                    lastExchangeIndex = i;
                    isSorted = false;
                }
            }
            if(isSorted){
                break;
            }
            else{
                frontSortBorder = lastExchangeIndex;
            }
        }
    }
    return ;
}


inline void slove(vector <int>& v, int len){
	if(len <= 50005){
		quickSort(v);
	}
	else if(len > 50005 && len <= 100005){
		radixsort(v, len);
	}
	else if(len > 100005 && len <= 500005){
		mergeSort(v);
	}
	else if(len > 500005 && len <= 1000005){
		heap_sort(v, len);
	}
	else {
		//timSort(v, len);
		CocktailSort(v);
	}
}


int l, r, p;
int MOD;
const int sz = 200;


struct Matrix{
	int G[sz][sz];
	Matrix(){ memset(G, 0, sizeof G); }
	Matrix operator+(const Matrix& T) const{
		Matrix res;
		for(int i = 1; i <= l; i++){
			for(int j = 1; j <= r; j++){
				res.G[i][j] = G[i][j] + T.G[i][j];
			}
		}
		return res;
	}
	Matrix operator-(const Matrix& T) const{
		Matrix res;
		for(int i = 1; i <= l; i++){
			for(int j = 1; j <= r; j++){
				res.G[i][j] = G[i][j] - T.G[i][j];
			}
		}
		return res;
	}
	Matrix operator*(const Matrix& T) const{
		Matrix res;
		for(int i = 1; i <= l; i++){
			for(int j = 1; j <= p; j++){
				for(int k = 1; k <= r; k++){
					res.G[i][j] += T.G[k][j] * G[i][k];
				}
			}
		}
		return res;
	}
	Matrix operator/(const Matrix& T) const{
		Matrix res;
		for(int i = 1; i <= l; i++){
			for(int j = 1; j <= r; j++){
				res.G[i][j] = G[i][j] / T.G[i][j];
			}
		}
		return res;
	}
	Matrix operator^(int x) const{
		Matrix res, base;
		for(int i = 1; i <= l; i++) res.G[i][1] = 1;
		for(int i = 1; i <= l; i++){
			for(int j = 1; j <= r; j++){
				base.G[i][j] = G[i][j];
			}
		}
		while(x){
			if(x & 1)res = res * base;
			base = base * base;
			x >>= 1;
		}
		return res;
	}
};
inline void Print(const Matrix& T){
	for(int i = 1; i <= l; i++){
		for(int j = 1; j <= r/*p*/; j++){
			write(T.G[i][j]);
			printf(" ");
		}
		printf("\n");
	}
	return ;
}


namespace NEW_CMATH{
	inline int fast_gcd(int a, int b){
		if(a == 0)return b;
		if(b == 0)return a;
		if(!(a & 1) && !(b & 1))return fast_gcd(a >> 1, b >> 1) << 1;
		else if(!(b & 1))return fast_gcd(a, b >> 1);
		else if(!(a & 1))return fast_gcd(a >> 1, b);
		else return fast_gcd(abs(a - b), min(a, b));
	}
	inline int quickPower(int a, int b){
		int ans = 1, base = a;
		while(b > 0){
			if(b & 1)ans *= base;
	        base *= base;
			b >>= 1;
		}
		return ans;
	}
	inline bool isPrime(int num){
	    if(num == 1 || num == 4)return 0;
	    if(num == 2 || num == 3)return 1;
	    if(num % 6 != 1 && num % 6 != 5)return 0;
	    int tmp = sqrt(num);
	    for(int i = 5; i <= tmp; i += 6)if(num % i == 0 || num % (i + 2) == 0)return 0;
	    return 1;
	}
	inline int fibonacci(int x){
		l = r = p = 2;
		if(x <= 2)return 1;
		else {
			Matrix a;
			a.G[1][2] = a.G[2][1] = a.G[2][2] = 1;
			a = a ^ x;	
			return a.G[2][2];
		}
	}
}
using namespace NEW_CMATH;


signed main(){
	int n, m;
	read(n, m);
	n = fast_gcd(n, m);
	write(fibonacci(n));
	return 0;
}