E2. Minibuses on Venus (medium version)（卷积加速dp）

数的范围是在k进制下的n位数
一个数是lucky的当且仅当在k进制下，存在一个数位上的数，等于其他数位上的数在模k意义下的和。

利用减法原理
假设一个数的数位和为s，如果存在一个数，那么有
s-x%k=x%k -> s%k=2x%k
那么我们找到这样的x，就是说在计算和为s的方案数是不能使用这些x

类似于dp的做法，我们可以将它看作是一个卷积，然后利用快速幂加速即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const int S=1e5+5;
const ll inf=1ll<<60;
ll n,k,mo,ans;
void add(ll &x,ll y){
	x=(x+y)%mo;
}
vector<ll> mul(vector<ll> &a, vector<ll> &b){
	vector<ll> c(k);
	fo(i,0,k-1) fo(j,0,k-1) {
		add(c[(i+j)%k], a[i]*b[j]%mo);
	}
	return c;
}
void calc(vector<ll> &y,ll s,ll b){
	vector<ll> t(k);
	t[0]=1;
	while (b) {
		if (b&1) t=mul(t,y);
		y=mul(y,y);
		b/=2;
	}
//	printf("%lld\n",y[s]);
	ans=(ans-t[s])%mo;
}
ll power(ll a,ll b){
	ll t=1,y=a%mo;
	while (b) {
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
int main()
{
//	freopen("data.in","r",stdin);
	scanf("%lld %lld %lld",&n,&k,&mo);
	
	ans=power(k,n);
//	printf("%lld",ans);
//	return 0;

	fo(s,0,k-1) {
		vector<ll> b(k,1);
		fo(x,0,k-1) 
			if (2*x%k==s%k) b[x]=0;
		
//		fo(x,0,k-1) printf("%lld ",b[x]);
		calc(b,s,n);
//		printf("\n");
//		fo(x,0,k-1) printf("%lld ",b[x]);
	}
	
//	return 0;
	ans=(ans%mo+mo)%mo;
	printf("%lld",ans);

	return 0;
}