top++;
if(i==2)
{
i=3;
}else
{
i+=2;
}
}
if(n!=1)
{
xiang[top]=n;
xishu[top]++;
top++;
}
for(i=0,res=1;i<=top-1;i++)
{
t=deal(xiang[i],xishu[i]*m);
res=(res*t)%mod;
}
printf("%I64d\n",res);
}
return 0;
}
__int64 f(__int64 p,__int64 n)
{
__int64 res=1;
p=p%mod;
while(n>1)
{
if(n&1)
{
res=(res*p)%mod;
}
p=(p*p)%mod;
n=n/2;
}
return ((res*p)%mod);
}
__int64 deal(__int64 p,__int64 n)
{
__int64 t;
if(n==0)
{
return 1;
}
if(n%2)
{
t=deal(p,n/2);
return (((1+f(p,n/2+1))%mod)*(t%mod))%mod;
}else
{
t=deal(p,n/2-1);
return ((((1+f(p,n/2+1))%mod)*(t%mod))%mod+f(p,n/2)%mod)%mod;
}
}