三个袋子

时间限制:1000MS内存限制:256000KB 题目描述 背景
    平平在公园里游玩时捡到了很多小球，而且每个球都不一样。平平找遍了全身只发现了3个一模一样的袋子。他打算把这些小球都装进袋子里（袋子可以为空）。他想知道他总共有多少种放法。
 
题目描述
    将N个不同的球放到3个相同的袋子里，求放球的方案总数M。
    结果可能很大，我们仅要求输出M mod K的结果。
    现在，平平已经统计出了N<=10的所有情况。见下表： N 1 2 3 4 5 6 7 8 9 10 M 1 2 5 14 41 122 365 1094 3281 9842  
  输入 两个整数N,K，N表示球的个数。 输出 输出仅包括一行，一个整数M mod K 。 输入样例复制 11 10000 输出样例复制 9525 说明 数据规模 对于 40%数据,10<=N<=10,000 对于100%数据,10<=N<=1,000,000,000 对于 100%数据，K<=100,000
题解：观察易得出 a[n]=a[n-1]*3-1;
           数学知识待定系数法得a[n]=(3^(n-1)+1)/2
           直接用费马小定理超时
           找到一条神奇公式    (a/b)%m = (a % (b*m))/b
  var   n,kk:int64;   k,xx,yy,pp:longint; function mi(x:int64):int64; var   pp:int64; begin   if x=0 then exit(1);   if x=1 then exit(3);   pp:=mi(x shr 1)mod k;   if odd(x) then mi:=(pp*pp*3) mod k   else mi:=(pp*pp)mod k; end; begin   readln(n,k);   k:=k*2;   kk:=mi(n-1)+1;   writeln((kk div 2)); end.