看着正确率还不错的一道题，然后就后悔了。。。

找了个题解看看，然后就什么都不知道写了程序~~~

题目： http://www.lydsy.com/JudgeOnline/problem.php?id=1009

那啥，DP，一开始以为数学题的，但是样例怎么都算不出~~~怪我咯

KMP+DP乱搞，你当我知道怎么做啊←_←

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

string s;
int n,m,mod,ans;
int p[30],f[30][30],a[30][30],b[30][30];

void doing(int xx)
{
	if (xx>3) doing(xx/2);
	if (xx==1) return;
	memset(a,0,sizeof(a));
	for (int i=0;i<m;++i)
	for (int j=0;j<m;++j)
	for (int k=0;k<m;++k)
	a[i][j]=(a[i][j]+f[i][k]*f[k][j])%mod;
	memcpy(f,a,sizeof(a));
	if (xx%2==1)
	{
		memset(a,0,sizeof(a));
		for (int i=0;i<m;++i)
		for (int j=0;j<m;++j)
		for (int k=0;k<m;++k)
		a[i][j]=(a[i][j]+f[i][k]*b[k][j])%mod;
		memcpy(f,a,sizeof(f));
	}
	return;
}

int main()
{
	scanf("%d%d%d",&n,&m,&mod);
	memset(p,0,sizeof(p));
	memset(f,0,sizeof(f));
	memset(b,0,sizeof(b));
	cin>>s;
	s=" "+s;
	for (int i=2;i<s.length();i++)
	{
		int xx=p[i-1];
		while (s[i]!=s[xx+1]&&xx!=0) xx=p[xx];
		if (s[i]==s[xx+1]) p[i]=xx+1;
	}
	for (int i=0;i<s.length()-1;++i)
	{
		for (int j=0;j<=9;++j)
		{
			int xx=i;
			while (xx!=0&&j!=s[xx+1]-'0') xx=p[xx];
			if (j==s[xx+1]-'0') f[i][xx+1]++;
			else f[i][0]++;
		}
	}
	memcpy(b,f,sizeof(f));
	doing(n);
	ans=0;
	for(int i=0;i<m;++i) ans=(ans+f[0][i])%mod;
	printf("%d\n",ans%mod);
	return 0;
}