#include <bits/stdc++.h>
#define ll long long
using namespace std;
void exgcd(ll a,ll b,ll &x,ll &y){
    if (!b) return (void)(x=1,y=0);
    exgcd(b,a%b,x,y);
    ll tmp=x;x=y;y=tmp-a/b*y;
}
ll gcd(ll a,ll b){
    if (b==0) return a;
    return gcd(b,a%b); 
}
inline ll INV(ll a,ll p){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}
inline ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
inline ll mabs(ll x){
    return (x>0?x:-x);
}
inline ll fast_mul(ll a,ll b,ll p){
    ll t=0;a%=p;b%=p;
    while (b){
        if (b&1LL) t=(t+a)%p;
        b>>=1LL;a=(a+a)%p;
    }
    return t;
}
inline ll fast_pow(ll a,ll b,ll p){
    ll t=1;a%=p;
    while (b){
        if (b&1LL) t=(t*a)%p;
        b>>=1LL;a=(a*a)%p;
    }
    return t;
}
inline ll F(ll n,ll P,ll PK){
    if (n==0) return 1;
    ll rou=1;
    ll rem=1;
    for (ll i=1;i<=PK;i++){
        if (i%P) rou=rou*i%PK;
    }
    rou=fast_pow(rou,n/PK,PK);
    for (ll i=PK*(n/PK);i<=n;i++){
        if (i%P) rem=rem*(i%PK)%PK;
    }
    return F(n/P,P,PK)*rou%PK*rem%PK;
}
inline ll G(ll n,ll P){
    if (n<P) return 0;
    return G(n/P,P)+(n/P);
}
inline ll C_PK(ll n,ll m,ll P,ll PK){
    ll fz=F(n,P,PK),fm1=INV(F(m,P,PK),PK),fm2=INV(F(n-m,P,PK),PK);
    ll mi=fast_pow(P,G(n,P)-G(m,P)-G(n-m,P),PK);
    return fz*fm1%PK*fm2%PK*mi%PK;
}
ll A[1001],B[1001];
inline ll exLucas(ll n,ll m,ll P){
    ll ljc=P,tot=0;
    for (ll tmp=2;tmp*tmp<=P;tmp++){
        if (!(ljc%tmp)){
            ll PK=1;
            while (!(ljc%tmp)){
                PK*=tmp;ljc/=tmp;
            }
            A[++tot]=PK;B[tot]=C_PK(n,m,tmp,PK);
        }
    }
    if (ljc!=1){
        A[++tot]=ljc;B[tot]=C_PK(n,m,ljc,ljc);
    }
    ll ans=0;
    for (ll i=1;i<=tot;i++){
        ll M=P/A[i],T=INV(M,A[i]);
        ans=(ans+B[i]*M%P*T%P)%P;
    }
    return ans;
}

ll P,C[1001],D[1001],tot,ph,mm,M[1001],T[1001];
void init (int o, int p)
{
	ph=P=p;
	ll ljc=P;
	tot=0;
    for (ll tmp=2;tmp*tmp<=P;tmp++){
        if (!(ljc%tmp)){
            ll PK=1;
            ph=ph/tmp*(tmp-1);
            while (!(ljc%tmp)){
                PK*=tmp;ljc/=tmp;
            }
            A[++tot]=PK;
            C[tot]=tmp;
            D[tot]=PK;
//			B[tot]=C_PK(n,m,tmp,PK);
        }
    }
    if (ljc!=1){
        A[++tot]=ljc;
        C[tot]=D[tot]=ljc;
        ph=ph/ljc*(ljc-1);
//		B[tot]=C_PK(n,m,ljc,ljc);
    }
    for (ll i=1;i<=tot;i++){
    	M[i]=P/A[i];T[i]=INV(M[i],A[i]);
    }
    mm=fast_pow(4,ph-1,P);
}

#include<map>
map<long long,int> ma;

int ask (long long n)
{
	if(ma[n])return ma[n];
	for(int i=1;i<=tot;i++)B[i]=C_PK(2*n,n,C[i],D[i]);
	ll ans=0;
    for (ll i=1;i<=tot;i++){
        ans=(ans+B[i]*M[i]%P*T[i]%P)%P;
    }
    ans=n%P*ans%P;
    ll h=gcd(n,ph);
    if(h==1)ans=ans*fast_pow(mm,n%ph,P)%P;
    else if(n>=ph)ans=ans*fast_pow(mm,n%ph+ph,P)%P;
    else ans=ans*fast_pow(mm,n,P)%P;
    return ma[n]=ans;
}