被虐的体无完肤，
直接给题解地址吧：http://vfleaking.blog.163.com/blog/static/174807634201341721051604/
const maxk=;
type matrix=array[..,..] of int64;
var a:array[..maxk*] of longint;
first,last,b,len:array[..maxk] of longint;
pre:array[..maxk] of longint;
n,k,p,x,y,sum:int64;
i,j:longint;
ans,aa,bb,s:matrix; function ni(x:int64; y:longint):int64;
begin
ni:=;
while y> do
begin
if y mod = then ni:=ni*x mod k;
y:=y div ;
x:=x*x mod k;
end;
end; procedure work;
var i,d,ph:longint;
begin
a[]:=;a[]:=;i:=;
while true do
begin
inc(i);
a[i]:=(a[i-]+a[i-]) mod k;
if first[a[i]]= then first[a[i]]:=i;
if (a[i]=) and (a[i-]=) then break;
end;
d:=k;
ph:=k;
for i:= to trunc(sqrt(k)) do
if d mod i= then
begin
ph:=ph div i*(i-);
while d mod i= do d:=d div i;
end;
if d> then ph:=ph div d*(d-); for i:= to k- do
begin
pre[i]:=ni(i,ph-);
if int64(pre[i])*int64(i) mod k<> then pre[i]:=;
// writeln(pre[i]);
end;
b[]:=;last[]:=;i:=;
while true do
begin
len[i]:=first[pre[b[i]]]-;
if len[i]< then break;
inc(i);
b[i]:=int64(a[len[i-]])*b[i-] mod k;
if last[b[i]]> then break;
last[b[i]]:=i;
end;
aa[,]:=; aa[,]:=; aa[,]:=; aa[,]:=;
bb:=aa; bb[,]:=p-;
end; operator *(a,b:matrix)c:matrix;
var i,j,k:longint;
begin
for i:= to do
for j:= to do
begin
c[i,j]:=;
for k:= to do
c[i,j]:=(c[i,j]+a[i,k]*b[k,j]) mod p;
end;
end; function f(a:matrix;n:int64):matrix;
begin
fillchar(f,sizeof(f),);
f[,]:=;f[,]:=;f[,]:=;
while n> do
begin
if n and = then f:=f*a;
a:=a*a;
n:=n div ;
end;
end; begin
readln(n,k,p);
if n< then
begin
writeln();
exit;
end;
work;
ans[,]:=; ans[,]:=; ans[,]:=;
if n>len[] then
begin
dec(n,len[]+);
ans:=ans*f(aa,len[]-)*bb;
end
else begin
ans:=ans*f(aa,n-);
n:=;
end;
i:=;
while n> do
begin
if (pre[b[i]]=) or (len[i]<) then
begin
ans:=ans*f(aa,n);
n:=;
break;
end;
if last[b[i]]<i then break;
if n>len[i] then
begin
dec(n,len[i]+);
ans:=ans*f(aa,len[i])*bb;
end
else begin
ans:=ans*f(aa,n);
n:=;
end;
inc(i);
end;
if n<> then
begin
j:=i;
sum:=;
fillchar(s,sizeof(s),);
s[,]:=; s[,]:=; s[,]:=;
for i:=last[b[j]] to j- do
begin
inc(sum,len[i]+);
s:=s*f(aa,len[i])*bb;
end;
ans:=ans*f(s,n div sum);
n:=n mod sum;
i:=last[b[j]];
while n> do
begin
if n>len[i] then
begin
ans:=ans*f(aa,len[i])*bb;
dec(n,len[i]+);
end
else begin
ans:=ans*f(aa,n);
n:=;
end;
inc(i);
end;
end;
writeln((ans[,]+ans[,]+ans[,]) mod p);
end.
