主题链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5187

题意：

从1~n，有多少种排列

使得 a1~ai 满足单调递增或者单调递减。

ai~an 满足单调递增或者递减。

非常明显的组合问题

从n个数种选出i个数 剩下的数要满足单调递增或者递减或者递减的规律那么方式唯一

ans = （C(N,0)+C(N,1)+......+C(N,N)） =2^N;

可是这样的情况下 单调递增和单调递减算了两遍  因此要减2

ans = 2^n - 2;

注意n = 1的情况 ，因为n比較大 ，要注意乘法溢出的情况

代码例如以下：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long LL;

LL multi(LL a,LL b, LL c)

{

    LL ans = 0;

    while(b){

        if(b&1){

            ans= (ans+a)%c;

            b--;

        }

        b>>=1;

        a=(a+a)%c;

    }

    return ans;

}

LL quick_mod(LL a,LL b,LL c)

{

    LL ans = 1;

    while(b){

        if(b&1){

            ans = multi(ans,a,c);

            b--;

        }

        b>>=1;

        a=multi(a,a,c);

    }

    return ans ;

}

int main()

{

    LL n,p;

    while(~scanf("%lld%lld",&n,&p)){

        if(n==1){

            printf("%d\n",1%p);

            continue;

        }

        LL ans = 2;

        ans = quick_mod(ans,n,p);

        ans =(ans - 2 + p)%p;

        printf("%I64d\n",ans);

    }

    return 0;

}