#include<bits/stdc++.h>
using namespace std;
#define N 1000009
inline long long read()
{
    register long long x=0;
    register char ch=cin.get();
    register bool op=0;
    while(!isdigit(ch)) {if(ch=='-')op=1;ch=cin.get();}
    while(isdigit(ch)) {(x*=10)+=(ch^48);ch=cin.get();}
    return op? -x:x;
}
long long x,y,p,n,o,T;
int ans;
inline void exgcd(register long long a,register long long b)
{
    if(!b) {x=1,y=0;return;}
    exgcd(b,a%b);
    int nx=x;
    x=y;
    y=nx-a/b*y;
}
long long inv[N];
inline long long INV(register long long k)
{
    if(inv[k]) return inv[k];
    x=0,y=0;
    exgcd(k,p);
    inv[k]=(x%p+p)%p;
    return inv[k];
}
inline void dfs(register long long a,register int cnt,register int w)
{
    if(cnt==n) return ans+=a*abs(w),void();
    for(register int i(1);i<=3;++i) 
    {
        if(i==1) dfs(a*INV(4)%p,cnt+1,w-1);
        if(i==2) dfs(a*INV(2)%p,cnt+1,w);
        if(i==3) dfs(a*INV(4)%p,cnt+1,w+1);
    }
}
void init(int o,int p){ans=0;}
int ask(long long n)
{
    ans=0;
    dfs(1,0,0);
    return ans%p;
}