HDU 2855 Fibonacci Check-up

/*
*  [题意]
*   F(0) = 0; F(1) = 1; F(n) = F(n-1)+F(n-2); （斐波那契数列）
*   设C[i][j]为组合数i种元素中取j种元素的方法
*   给出n、m，求( C[n][0]*F(0)+C[n][1]*F(1)+...+C[n][k]*F(k) ) % m;
*  [解题方法]
*   设矩阵 A  =  |1 1|
*               |1 0|
*   设矩阵 B = (A^n)
*   则B[0][0] = F(n-1); B[0][1] = B[1][0] = F(n); B[1][1] = F(n-1);
*       { 注：上述为斐波那契矩阵的性质 }
*   令D = ( C[n][0]*(A^0) + C[n][1]*(A^1) +...+ C[n][k]*(A^k) ) % m
*       = ( (A + E)^n ) % m   (E为单位阵)
*       { 类比二次多项式(x+1)^n = C[n][0]+C[n][0]*x+...+C[n][k]*(x^k) }
*   则D[1][0]或D[0][1]即为所求
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define M 2
#define LL long long
#define FF(i, n) for(int i = 0; i < n; i++)

int ret[M][M], mod;
int init[M][M];
int ss[M][M] = {2, 1, 1, 1};

void ini(int n)
{
    FF(i, n) FF(j, n) init[i][j] = ss[i][j];
}

void matmul(int a[][M], int b[][M], int n)
{
    int tp[M][M] = {0};
    FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j])
        tp[i][j] = (tp[i][j] + (LL)a[i][k]*b[k][j]) % mod;
    FF(i, n) FF(j, n) a[i][j] = tp[i][j];
}

void qmod(int n, int b)
{
    FF(i, n) FF(j, n) ret[i][j] = (i==j);
    for( ; b; b >>= 1)
    {
        if (b & 1) matmul(ret, init, n);
        matmul(init, init, n);
    }
}

int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &mod);
        ini(M);
        qmod(M, n);
        printf("%d\n", ret[0][1]);
    }
    return 0;
}