裸的矩阵乘法，我却调了一上午……弱到爆啊……
不过最终辛苦没有白费，我终于彻底搞懂了
要注意几点：
一、必须构造出前几项
二、用矩阵乘法算法之后还要手工算答案，利用首先算好的前几项
三、想好自己构造的矩阵是横着的还是竖着的
四、要用一个单位矩阵存储最后的结果
代码：（不容易啊）
type matrix=array[..,..] of int64;
var i,n,k,j:longint;
ans:int64;
a,b:matrix;
f:array[..] of int64;
function mo(x:int64):int64;
begin
mo:=x mod ;
end;
procedure mul(var x,y,z:matrix);
var i,j,l:longint;
t:matrix;
begin
fillchar(t,sizeof(t),);
for i:= to k do
for j:= to k do
for l:= to k do
t[i,j]:=mo(t[i,j]+x[i,l]*y[l,j]);
z:=t;
end;
procedure ksm(times:longint);
begin
while times<> do
begin
if times and = then mul(a,b,b);
times:=times>>;
mul(a,a,a);
end;
end;
procedure init;
begin
readln(k);readln(n);
fillchar(a,sizeof(a),);
fillchar(b,sizeof(b),);
for i:= to k do a[,i]:=;
for i:= to k do a[i,i-]:=;
for i:= to k do b[i,i]:=;
f[]:=;f[]:=;
for i:= to k do
for j:= to i- do
f[i]:=mo(f[i]+f[j]);
if n<=k then begin writeln(f[n]);halt;end;
end;
procedure main;
begin
ksm(n-k);
ans:=;
for i:= to k do ans:=mo(ans+b[,i]*f[k+-i]);
writeln(ans);
end;
begin
init;
main;
end.