/*
TASK:fib
LANG:C++
*/
#include <iostream>
using namespace std;
int fib[12000000],m,last;
long long n;
bool isCyclic(int a,int b)
{
     for(int i=a;i<=b;i++)
             if(fib[i-a+1]!=fib[i]) return false;
     return true;
}
bool generateNext(int a)
{
     for(int i=a;;i++)
     {
             fib[i]=fib[i-1]+fib[i-2];
             fib[i]%=m;
             if(fib[i]==0) {last=i;break;}
     }
     if(!isCyclic(a,last)) return true;
     else
     {
         last=a-1;
         return false;
     }
}
int main()
{
    cin>>n>>m;
    if(m==1) {cout<<0<<endl;return 0;}
    fib[0]=0;
    fib[1]=fib[2]=1;
    for(int i=3;;i++)
    {
            fib[i]=fib[i-1]+fib[i-2];
            fib[i]%=m;
            if(fib[i]==0) {last=i;break;}
    }
    while(generateNext(last+1));
    
    cout<<fib[n%last]<<endl;
    return 0;
}
