#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<cstdlib>using namespace std;struct bign { int len, s[105]; void subtract() { for(int i=0; i<len; i++) { if(s[i] > 0) { s[i] --; break; } s[i] = 9; } if(s[len-1] == 0) len --; } void divide() { bool flag = 0; for(int i=len-1; i>=0; i--) { if(s[i] & 1 == 1) { s[i] = ((flag==1?10:0) + s[i]) >> 1; flag = 1; } else { s[i] = ((flag==1?10:0) + s[i]) >> 1; flag = 0; } } if(s[len-1] == 0) len --; } void printit() { for(int i=len-1; i>=0; i--) { printf("%d", s[i]); } printf("n"); }};struct Matrix { int m[32][32]; Matrix() {memset(m, 0, sizeof(m));}} sol;inline bool judge(int a1, int a2, int a3, int a4) { return (a1 == (a2 >> 1) && a1 == a3 && a1 == (a4 >> 1));}char op[105];int m, mod, t;bign n;int A[32][32], M[32][32], w[32][32];void init() { for(int i=0; i<t; i++) { for(int j=0; j<t; j++) { int flag = 1; for(int k=0; k<m-1; k++) { if(judge(i&(1<<k), i&(1<<(k+1)), j&(1<<k), j&(1<<(k+1)))) { flag = 0; break; } } w[i][j] = flag; } }}void solve() { for(int i=0; i<t; i++) { for(int j=0; j<t; j++) { M[i][j] = w[i][j]; } } while (n.len) { if (n.s[0] & 1) { memset(A, 0, sizeof(A)); for (int k = 0; k < t; k ++) for (int i = 0; i < t; i ++) for (int j = 0; j < t; j ++) A[i][j] = (A[i][j] + M[i][k] * w[k][j]) % mod; for (int i = 0; i < t; i ++) for (int j = 0; j < t; j ++) M[i][j] = A[i][j]; } memset(A, 0, sizeof(A)); for (int k = 0; k < t; k ++) for (int i = 0; i < t; i ++) for (int j = 0; j < t; j ++) A[i][j] = (A[i][j] + w[i][k] * w[k][j]) % mod; for (int i = 0; i < t; i ++) for (int j = 0; j < t; j ++) w[i][j] = A[i][j]; n.divide(); } long long answer = 0; for(int i=0; i<(1<<m); i++) { for(int j=0; j<(1<<m); j++) { answer += M[i][j]; answer %= mod; } } cout << answer << endl;}int main(){ int T; scanf("%d", &T); while(T--) { scanf("%s%d%d", op, &m, &mod); n.len = strlen(op); for(int i=n.len-1; i>=0; i--) { n.s[n.len-1-i] = op[i] - '0'; } if(n.len == 1 && n.s[0] == 1) { printf("%dn", (1<<m) % mod); } else { n.subtract(); n.subtract(); t = 1 << m; init(); solve(); } if(T >= 1) cout << endl; } return 0;}
