每个长度为p的区间都必须出现k次1，数据又很小，我们使用状压。
dp[i][j]->dp[i+1][j'],dp[i][j]表示当前考虑到了第i个车站，包括第i个其后的p个的状态（有车停或没车停），其中j'为j中某一个车动一次到达的状态，为了防止复杂度爆炸，先dfs求一遍有用的状态。
然后矩阵转移。。
另外提一下初末状态，注意到起始站的限制，初末状态都应是p个里前k个都是1。（在代码实现中就正好对应了第一个dfs的状态）
这也是开始B.t[1][1]赋值1和最后输出B.t[1][1]的原因
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=,mod=;
struct matr{
int t[maxn][maxn],n,m;
matr operator*(matr &a){
matr c;
for(int i=;i<=n;++i)
for(int j=;j<=a.m;++j){
c.t[i][j]=;
for(int k=;k<=n;++k)
c.t[i][j]=(c.t[i][j]+t[i][k]*a.t[k][j])%mod;
}
c.n=n;c.m=a.m;
return c;
}
}A,B;
int n,k,p,q[maxn];
void dfs(int pos,int num,int cnt){
if(cnt==k){q[++q[]]=num;return;}
for(int i=pos-;i>=;--i)
dfs(i,num+(<<i),cnt+);
}
int check(int x,int y){
int tmp=x-(<<(p-));
tmp<<=;tmp^=y;
if(tmp==(tmp&(-tmp)))return ;
return ;
}
int main(){
cin>>n>>k>>p;
dfs(p-,(<<(p-)),);
A.n=A.m=B.n=B.m=q[];
for(int i=;i<=q[];++i)B.t[i][i]=;
for(int i=;i<=q[];++i)
for(int j=;j<=q[];++j){
if(check(q[i],q[j]))A.t[i][j]=;
}
/*for(int i=1;i<=q[0];++i){
for(int j=1;j<=q[0];++j)
cout<<A.t[i][j]<<' ';
cout<<endl;
}*/
int cc=n-k;
while(cc){
if(cc&)B=B*A;
cc>>=;A=A*A;
}
cout<<B.t[][]<<endl;
//system("pause");
return ;
}