题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5187 如果n为1的话答案是1%p，否则答案是2^n-2-2、 仔细思考，除去递增和递减两种顺序外，要想达到这个状态只能是中间的数是最大的或者最小
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5187
如果n为1的话答案是1%p，否则答案是2^n-2-2、
仔细思考，除去递增和递减两种顺序外，要想达到这个状态只能是中间的数是最大的或者最小的。当确定了中心，我们再想，如果确立了两边的个数，和两边分别有哪些数，就能确立唯一的一种排法，所以这种就是C(1,n-1)+C(2,n-1)+C(3,n-1)+……C(n-2,n-1) = 2^(n-1)-2，中心有两种，所以答案就是2*(2^(n-1)-2)+2 = 2^n+2.
typedef long long LL;
LL mul(LL a, LL b, LL c)
{
LL ans = 0;
while(b)
{
if(b&1) ans = (ans + a)%c;
a = (a+a)%c;
b >>= 1;
}
return ans;
}
LL Power_mod(LL a,LL b,LL c)
{
LL ans = 1;
while(b)
{
if(b&1) ans = mul(ans, a, c);
a = mul(a, a, c);
b >>= 1;
}
return ans;
}
int main()
{
LL n,p;
while(scanf("%I64d%I64d", &n, &p) !=EOF)
{
if(n == 1) printf("%I64d\n", 1%p);
else printf("%I64d\n", (Power_mod(2,n,p)+p-2)%p);
}
}