Fibonacci

#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <queue>
#include <set>
#include <map>
using namespace std;

int MOD;
typedef long long ll;

ll gcd(ll a, ll b)
{
    return b?gcd(b,a%b):a;
}

map<ll,ll> phiMP;
ll phi(ll n)
{
    if(!phiMP.count(n))
    {
        ll res=1;
        ll t=n;
        for(ll i=2;i*i<=t;i++)
        {
            if(t%i==0)
            {
                res*=i-1;
                t/=i;
                while(t%i==0)
                {
                    t/=i;
                    res*=i;
                }
            }
        }
        if(t!=1) res*=t-1;
        phiMP[n]=res;
    }
    return phiMP[n];
}

template<typename T>
T qpowmod(T a, ll b, ll mod)
{
    T res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

struct Ratio
{
    ll a, b;
    Ratio(ll a=0, ll b=0):a(a),b(b)
    {
    }
    Ratio operator+(const Ratio& y) const
    {
        return Ratio(a+y.a, b+y.b);
    }
    Ratio operator-(const Ratio& y) const
    {
        return Ratio(a-y.a, b-y.b);
    }
    Ratio operator*(const Ratio& y) const
    {
        return Ratio(a*y.a+5*b*y.b, a*y.b+b*y.a);
    }
    Ratio operator%(ll mod) const
    {
        return Ratio(a%mod, b%mod);
    }
    ll Re() const
    {
        return a;
    }
    ll Im() const
    {
        return b;
    }
};

ll revmod(ll a, ll MOD)
{
    return qpowmod(a,phi(MOD)-1,MOD);
}

ll fib(ll n)
{
    return (qpowmod<Ratio>(Ratio(1,1)*revmod(2,MOD),n,MOD)).Im()*2%MOD;
}

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