记录编号	417513	评测结果	AAAAAAAAAA
题目名称	选拔队员	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2017-06-25 20:50:49	内存使用	0.41 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

namespace IO{
	inline char getc(void);
	inline int in(void);
	inline void write(int x);
	inline void write_all(void);
	
	char ip[1 << 18], *ips, *ipt;
	char ops[1 << 18], *opt = ops, *const opt_end = ops + (1 << 18);
	char num[14], *p = num;
	
	inline char getc(void){
		return (ips == ipt && (ipt = (ips = ip) + fread(ip, 1, 1 << 18, stdin)), ips == ipt) ? EOF : *ips++;
	}
	
	inline int in(void){
		register int res = 0;
		register char tmp = getc();
		while(!isdigit(tmp)) tmp = getc();
		while(isdigit(tmp))
			res = (res + (res << 2) << 1) + (tmp ^ 48),
			tmp = getc();
		return res;
	}
	
	inline void write(int x){
		do{
			*(++p) = (x % 10) | 0x30;
			x /= 10;
		}while(x);
		
		while(*p){
			*(opt++) = *(p--);
			if(opt == opt_end) write_all();
		}
		*(opt++) = '\n';
		if(opt == opt_end) write_all();
		return ;
	}
	
	inline void write_all(void){
		fwrite(ops, 1, opt - ops, stdout);
		return ;
	}
}

using IO::in;
using IO::write;
using IO::write_all;

#ifndef LOCAL
void *in_file = freopen("seata.in", "r", stdin);
void *out_file = freopen("seata.out", "w", stdout);
#else
void *test_file = freopen("test.in", "r", stdin);
#endif

const int T = in(), MOD = in();

struct Jz{
	int m, n;
	int s[2][2];
	
	Jz(){;}
	Jz(int x, int y){
		m = x, n = y;
		memset(s, 0x00, sizeof(s));
	}
	
	Jz operator * (const Jz &a) const {
		register Jz b(m, a.n);
		for(int i = 0; i < m; ++i){
			for(int j = 0; j < a.n; ++j){
				for(int k = 0; k < n; ++k){
					b.s[i][j] = (b.s[i][j] + s[i][k] * a.s[k][j]) % MOD;
				}
			}
		}
		return b;
	}
};

inline Jz Pow(Jz x, int n);

int n;
Jz a, ans;

int main(){
	for(int lllll = 1; lllll <= T; ++lllll){
		n = in();
		a = Jz(2, 2);
		ans = Jz(1, 2);
		a.s[0][1] = 1;
		a.s[1][0] = 1;
		a.s[1][1] = 1;
		ans.s[0][0] = 2;
		ans.s[0][1] = 3;
		a = Pow(a, n - 1);
		ans = ans * a;
		write(ans.s[0][0]);
	}
	write_all();
	return 0;
}

inline Jz Pow(Jz x, int n){
	Jz res(2, 2);
	res.s[0][0] = res.s[1][1] = 1;
	
	while(n){
		if(n & 1) res = res * x;
		x = x * x;
		n >>= 1;
	}
	
	return res;
}