/*
TASK: fib
LANG: C++
*/

#include <iostream>
using namespace std;
long long i = 2;
long long s = -1;
long long a[100000];
bool check(long long i2, long long s2)
{
     int br = 0;
     while (a[++br] == a[++s2] && s2 < i2);
     
     if (s2 == i2) return true;
     return false;
}
     
int main()
{
    long long f2, f1 = f2 = 1;
    long long m, n;
    cin >> n >> m;
    
    a[0] = a[1] = 1;
    bool have = true;
    bool brake = true;
    if (n == 1 || n == 0) { cout << 1%m << endl; return 0; } 
    if (m == 1) { cout << 0 << endl; return 0; }
    long long part = 80;   
    while (brake)
    {
          part += 80;
          for (; i < part; i++)
          {
              long long save = f1;
              f1 += f2;
              f2 = save;
        
              a[i] = f1 % m;
        
              if (i - s + 1 == s)
              {
                    if (check(i, s)) 
                    {
                         //for (int j = 0; j <= i; j++)
                          //cout << a[j] << " "; cout << " ---" << s << " " << " " << i << "-- "; 
                         brake = false;
                         break;
                    }
                    else
                    {
                         while (a[++s] != a[0] && s <= i);
                         if (s > i) have = true;
                    }
              }        
              if (a[i] == a[0] && have) {have = false; s = i;}  
        }
        f1 %= m;
        f2 %= m;     
    }
      
    n %= s;
    cout << a[n - 1] << endl;     
    //for (int i = 0; i < s; i++)
     //cout << a[i];
    system("pause");
    return 0;
}
