记录编号	141566	评测结果	AAAAAAAAAA
题目名称	[HNOI 2008]GT考试	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2014-12-02 23:46:31	内存使用	0.30 MiB

#include <cctype>
#include <cstdio>
using namespace std;
template<typename T>inline void getd(T &x){
	char c = getchar(); bool minus = 0;
	while(!isdigit(c) && c != '-')c = getchar();
	if(c == '-')minus = 1, c = getchar();
	x = c - '0';
	while(isdigit(c = getchar()))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*========================================================*/
const int maxm = 23;
int N, M, K, p[maxm][maxm], tmp[maxm][maxm];
char St[maxm];
inline int bitcnt(int x){
	x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
	x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
	x = ((x >> 4) & 0x0f0f0f0f) + (x & 0x0f0f0f0f);
	x = ((x >> 8) & 0x00ff00ff) + (x & 0x00ff00ff);
	x = ((x >> 16) & 0x0000ffff) + (x & 0x0000ffff);
	return x;
}
struct Mat{
	int A[maxm][maxm];
	void operator *= (const Mat &x){
		int i, j, k;
		for(i = 0;i < M;++i)for(j = 0;j < M;++j){
			tmp[i][j] = 0;
			for(k = 0;k < M;++k)
				tmp[i][j] = (tmp[i][j] + A[i][k] * x.A[k][j]) % K;
		}
		for(i = 0;i < M;++i)for(j = 0;j < M;++j)
			A[i][j] = tmp[i][j];
	}
}Ans, Per;
inline void init(){
	getd(N), getd(M), getd(K);
	int i, j, k, t, next[maxm];
	while(!isdigit(St[1] = getchar())); St[1] -= '0';
	for(i = 2;i <= M;++i)
		St[i] = getchar() - '0';
	next[0] = next[1] = 0;
	for(i = 1;i < M;++i){
		j = next[i]; k = (1 << 10) - 1;
		p[i][i+1] = 1; k ^= (1 << St[i+1]);
		while(j && St[j+1] != St[i+1]){
			t = 1 << St[j+1];
			if(k & t)p[i][j+1] = 1, k ^= t;
			j = next[j];
		}
		if(St[j+1] != St[i+1]){
			next[i+1] = 0;
			t = 1 << St[1];
			if(k & t)p[i][1] = 1, k ^= t;
		}
		else{
			next[i+1] = j+1;
			while(j){
				j = next[j];
				if(St[j+1] != St[i+1]){
					t = 1 << St[j+1];
					if(k & t)p[i][j+1] = 1, k ^= t;
				}
			}
		}
		p[i][0] = bitcnt(k);
	}
	p[0][0] = 9, p[0][1] = 1;
	for(i = 0;i < M;++i)for(j = 0;j < M;++j)
		Ans.A[i][j] = Per.A[i][j] = p[i][j];
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("bzoj_1009.in", "r", stdin);
	freopen("bzoj_1009.out", "w", stdout);
	#endif
	init();
	if(!N){printf("0\n");return 0;}
	N -= 1;
	while(N){
		if(N & 1)Ans *= Per;
		Per *= Per;
		N >>= 1;
	}
	**tmp = 0;
	while(M--)
		**tmp = (**tmp + Ans.A[0][M]) % K;
	printf("%d\n", **tmp);
	
	return 0;
}