首先不难得出递推式f[i]=(f[i-1]*10^k+i) mod m;
f[i]表示接到第i个数时的余数，k表示i的位数
不难想到先按位数穷举位数，然后对于确定的位数，构造矩阵解决
易得出：
f[i] 10^k 1 1 f[i-1]
i = 0 1 1 * i-1
1 0 0 1 1
矩阵乘法优化的特点就是有一维特别的大，且这一阶段的值只和上一阶段有关
var a,b,w,c:array[..,..] of int64;
f,p:array[..] of int64;
d:array[..] of longint;
e:array[..] of int64;
j,i,l,m:longint;
x,n:int64; procedure mul1;
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 m) mod m;
end;
end; procedure mul2;
var i,k:longint;
begin
for i:= to do
begin
f[i]:=;
for k:= to do
f[i]:=(f[i]+c[i,k]*p[k] mod m) mod m;
end;
end; procedure quick(x:int64);
var i,j:longint;
begin
j:=;
while x> do
begin
inc(j);
d[j]:=x mod ;
x:=x div ;
end;
fillchar(c,sizeof(c),);
for i:= to do
c[i,i]:=;
for i:=j downto do
begin
a:=c;
b:=c;
mul1;
if d[i]= then
begin
a:=c;
b:=w;
mul1;
end;
end;
end; begin
readln(n,m);
e[]:=;
l:=;
for i:= to do
begin
e[i]:=e[i-]*;
if e[i]>n then
begin
l:=i;
break;
end;
end;
e[]:=e[] mod m* mod m;
x:=;
w[,]:=e[] mod m; w[,]:=; w[,]:=;
w[,]:=; w[,]:=; w[,]:=;
w[,]:=; w[,]:=; w[,]:=;
f[]:=; f[]:=; f[]:=;
if l<> then x:=
else x:=n-;
p:=f;
quick(x);
mul2;
x:=;
for i:= to l do
begin
p:=f;
if i<>l then x:=x*
else x:=n-e[i-]+; //防止爆int64的
w[,]:=e[i] mod m;
quick(x);
mul2;
end;
writeln(f[]);
end.