/*
  Copyright 2011 Marek "p2004a" Rusinowski
  nth element of Fibonacci sequence (logarithmic)
*/
#include <cstdio>

typedef unsigned long long int llu;

llu *multiply(llu *l, llu *r, llu *res, llu c) {
  res[0] = ((l[1] * r[2]) % c + (l[0] * r[0]) % c) % c;
  res[1] = ((l[1] * r[3]) % c + (l[0] * r[1]) % c) % c;
  res[2] = ((l[3] * r[2]) % c + (l[2] * r[0]) % c) % c;
  res[3] = ((l[3] * r[3]) % c + (l[2] * r[1]) % c) % c;
  return res;
}

int fib(int n, int c) {
  llu *d = new llu [4], *res = new llu [4], *tmp1 = new llu [4], *tmp2;
  d[0] = 1; d[1] = 1;
  d[2] = 1; d[3] = 0;
  res[0] = 1; res[1] = 0;
  res[2] = 0; res[3] = 1;
  while (n) {
    if (n & 1) {
      tmp2 = res;
      res = multiply(res, d, tmp1, c);
      tmp1 = tmp2;
    }
    tmp2 = d;
    d = multiply(d, d, tmp1, c);
    tmp1 = tmp2;
    n >>= 1;
  }
  llu out = res[0];
  delete d;
  delete res;
  delete tmp1;
  return out;
}

int main() {
  int a, c;
  scanf("%d %d", &a, &c);
  printf("%d\n", fib(a, c));
  return 0;
}