/*
TASK:fib
LANG:C
*/
#include<stdio.h>
int main()
{
  unsigned long long a=1, b=2, m, n, d, i;
  scanf("%lu", &m);
  scanf("%lu", &n);
  if(n==1 || n==2) printf("%lu\n", a%m);
  else
  if(n==3) printf("%lu\n", b%m);
  else
  {
    for(i=4; i<=n || (a==1 && b==1); i++)
    {
      a=(a+b)%m;
      d=a;
      a=b;
      b=d;
    }
    if(i<n)
    {
      n%=(i-2);
      for(i=2; i<=n; i++)
      {
	a=(a+b)%m;
	d=a;
	a=b;
	b=d;
      }
    }
  printf("%lu\n", b);
  }
  return 0;
}
