反正N<=10^9肯定是矩阵乘法
反正p<=10肯定是状压dp
首先有一个非常重要的性质是任意连续P个站，必须保证K辆车必须停在其中的一个站
我们设f[i,S]表示到第i个站搞定了后，这K辆公交车停靠的站的状态集合为S的方案数
由于公交车之间是等价的，因此我们只要知道这K辆公交车离当前站的距离（∈[0,p-1])
显然这有一辆肯定距离当前站距离为0，剩下的k-1辆的距离显然在[1,p-1]中组合
可知状态数为C(k-1,p-1)，不难发现状态数最多是C(5,9)=126
由此可以得到f[i,s]=∑f[i-1,s']
显然我们可以弄出转移矩阵然后矩乘加速
const mo=; var w:array[..,..] of boolean;
v:array[..] of boolean;
a,b,c,d:array[..,..] of longint;
ch,m,n,k,p,i,j,h,ans:longint; procedure mul;
var i,j,k:longint;
begin
for i:= to m do
for j:= to m do
begin
c[i,j]:=;
for k:= to m do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod mo;
end;
end; procedure dfs(x,t:longint);
var i:longint;
begin
if (p-x<k-t) then exit;
if t=k+ then
begin
inc(m);
w[m]:=v;
end;
for i:=x to p do
begin
v[i]:=true;
dfs(i+,t+);
v[i]:=false;
end;
end; procedure quick(n:longint);
var t,i,x:longint;
begin
x:=n;
t:=;
while x<> do
begin
inc(t);
x:=x shr ;
end;
for i:=t- downto do
begin
a:=c;
b:=c;
mul;
if ( shl i) and n<> then
begin
a:=c;
b:=d;
mul;
end;
end;
end; begin
readln(n,k,p);
v[]:=true;
dfs(,); //搜出所有状态
for i:= to m do
for j:= to m do
begin
ch:=;
for h:= to p do
if w[i,h] and not w[j,h+] then //有一辆有停靠在当前站
begin
dec(ch);
if ch< then break;
end;
if ch= then d[j,i]:=;
end; n:=n-k;
for i:= to m do
c[i,i]:=;
quick(n);
writeln(c[,] mod mo);
end.