。。。题意在这里。
http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=571&pid=1002

我找出来的规律为 ai+1=ai +2,然后我就用矩阵快速幂。。两个数相乘的时候爆掉范围。。
所以要把乘法变成加法快速幂。。
在矩阵快速幂的基础上再加法快速幂。
代码。

//author: CHC
//First Edit Time: 2015-03-14 19:37
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef unsigned long long ULL;
//typedef unsigned __int64 LL;
const int MAXN=2;
ULL MOD;
ULL quickadd(ULL a,ULL b){
ULL ans=0;
while(a>0){
if(a&1)ans=(ans+b)%MOD;
a>>=1;
b=(b+b)%MOD;
}
return ans;
}
//C=A*B
void mul(ULL A[][MAXN],ULL B[][MAXN],ULL C[][MAXN]){
ULL tmp[MAXN][MAXN];
memset(tmp,0,sizeof(tmp));
for(int i=0;i<MAXN;i++){
for(int j=0;j<MAXN;j++){
for(int k=0;k<MAXN;k++){
//tmp[i][j]+=(A[i][k]*B[k][j])%MOD;
tmp[i][j]+=quickadd(A[i][k],B[k][j])%MOD;
tmp[i][j]%=MOD;
}
}
}
for(int i=0;i<MAXN;i++){
for(int j=0;j<MAXN;j++){
C[i][j]=(tmp[i][j]+MOD)%MOD;
}
}
}
ULL quickpow(ULL n){
if(n==1ULL)return 1ULL%MOD;
if(n==2ULL)return 2ULL%MOD;
if(n==3ULL)return 6ULL%MOD;
ULL ans[][MAXN]={{2ULL,2ULL},{0ULL,0ULL}};
ULL base[][MAXN]={{2ULL,0ULL},{1ULL,1ULL}};
n-=2ULL;
while(n>0){
//printf("here\n");
if((n&1ULL)==1ULL)mul(ans,base,ans);
mul(base,base,base);
n>>=1;
}
return ans[0][0]%MOD;
}
int main()
{
ULL n;
while(~scanf("%I64u%I64u",&n,&MOD)){
printf("%I64u\n",quickpow(n));
}
//MOD=1e+9 +7;
//while(~scanf("%llu",&n)){
//printf("%llu\n",quickpow(n));
//}
return 0;
}