就是以那个ai为分水岭，左边和右边都分别是单调增或单调减如图
就这四种情况，其中头两种总共就是两个序列，也就是从头到尾递增和从头到尾递减。
后两种方式就是把序列中德数分为左右两派，分完以后左右两边各自内部的排法就已经确定了，至于ai早就确定了（不是全局最大就是全局最小），而除了ai的每一个数都有选择在左或是在右两种选择，所以是2^(n-1),总共就是2^n,而这里包括了前两种的方案，所以要-4，最终应有2^n-2种。
看数据范围就知道要用快速幂，不过可惜如果只用快速幂会错，应为n和p的范围都是10^18,快速幂里在还没有模p之前的乘法都有可能超出long long int。所以想到用加法，a*b就是b个a相加，每一步都模p，8个a相加 ＝c c＋c ＝ 16个a 相加， 和快速幂一个道理。 然后用快速幂的原理不断二分，这就是所谓的快速乘法。
还有就是特殊数据，当n输入为1的时候情况数不是0而是1，当然不像BC上说的那样结果就是1，而是1MODp。
//
// main.cpp
// hdu5187
//
// Created by opas on 15/3/18.
// Copyright (c) 2015年 opas. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
typedef long long LL;
LL modj(LL a, LL b, LL m){
LL ans=;
while(b){
if(b&) ans=(ans+a)%m;
b>>=;
a=(a+a)%m;
}
return ans;
}
LL modx(LL a, LL b, LL m){
LL ans=;
while(b){
if(b&)ans=modj(ans,a,m);
b>>=;
a = modj(a,a,m);
}
return ans;
}
int main(int argc, const char * argv[]) {
LL n,p;
while(scanf("%lld%lld",&n,&p)==){
if(n==){
printf("%d\n",p>?:); continue;
}
printf("%lld\n",( modx( , n, p ) -+p)%p );
}
return ;
}