{
 Author:wzx961008
 Problem:HNOI 2011-homework
 Verdict:Accepted
 Language:PASCAL
 Run Time:0.17s
 AC Date:17.07.11
}
type matrix=array[1..3,1..3]of int64;
var tmt,mt,ans,temp:matrix;
    n,time,pw:int64;
    i,m,dt:longint;
function digit(n:int64):longint;
var tn:int64;
    i:longint;
begin
 i:=0; tn:=n;
 while tn>0 do begin
  tn:=tn div 10;
  i:=i+1;
 end;
 exit(i);
end;
procedure mul(m1,m2:matrix; var ret:matrix);
var i,j,k:longint;
    sum:int64;
begin
 for i:=1 to 3 do
  for j:=1 to 3 do begin
   sum:=0;
   for k:=1 to 3 do sum:=(sum mod m+((m1[i,k] mod m)*(m2[k,j] mod m)) mod m) mod m;
   ret[i,j]:=sum;
  end;
end;
procedure mmxp(n:int64; var ret:matrix);
var tn:int64;
    i:longint;
begin
 tn:=n;
 fillchar(ret,sizeof(ret),0);
 for i:=1 to 3 do ret[i,i]:=1;
 while tn>0 do begin
  if tn and 1=1 then mul(ret,tmt,ret);
  mul(tmt,tmt,tmt); tn:=tn>>1;
 end;
end;
begin
 readln(n,m);
 for i:=1 to 3 do ans[i,i]:=1;
 dt:=digit(n); pw:=1;
 for i:=1 to dt do begin
  mt[1,1]:=pw*10; mt[1,2]:=0; mt[1,3]:=0;
  mt[2,1]:=1; mt[2,2]:=1; mt[2,3]:=0;
  mt[3,1]:=1; mt[3,2]:=1; mt[3,3]:=1;
  tmt:=mt;
  if i<>dt then time:=9*pw
           else time:=n-pw+1;
  mmxp(time,temp);
  mul(ans,temp,ans);
  pw:=pw*10;
 end;
 writeln(ans[3,1]);
end.

ewogQXV0aG9yOnd6eDk2MTAwOAogUHJvYmxlbTpITk9JIDIwMTEtaG9tZXdvcmsKIFZlcmRpY3Q6QWNjZXB0ZWQKIExhbmd1YWdlOlBBU0NBTAogUnVuIFRpbWU6MC4xN3MKIEFDIERhdGU6MTcuMDcuMTEKfQp0eXBlIG1hdHJpeD1hcnJheVsxLi4zLDEuLjNdb2YgaW50NjQ7CnZhciB0bXQsbXQsYW5zLHRlbXA6bWF0cml4OwogICAgbix0aW1lLHB3OmludDY0OwogICAgaSxtLGR0OmxvbmdpbnQ7CmZ1bmN0aW9uIGRpZ2l0KG46aW50NjQpOmxvbmdpbnQ7CnZhciB0bjppbnQ2NDsKICAgIGk6bG9uZ2ludDsKYmVnaW4KIGk6PTA7IHRuOj1uOwogd2hpbGUgdG4+MCBkbyBiZWdpbgogIHRuOj10biBkaXYgMTA7CiAgaTo9aSsxOwogZW5kOwogZXhpdChpKTsKZW5kOwpwcm9jZWR1cmUgbXVsKG0xLG0yOm1hdHJpeDsgdmFyIHJldDptYXRyaXgpOwp2YXIgaSxqLGs6bG9uZ2ludDsKICAgIHN1bTppbnQ2NDsKYmVnaW4KIGZvciBpOj0xIHRvIDMgZG8KICBmb3Igajo9MSB0byAzIGRvIGJlZ2luCiAgIHN1bTo9MDsKICAgZm9yIGs6PTEgdG8gMyBkbyBzdW06PShzdW0gbW9kIG0rKChtMVtpLGtdIG1vZCBtKSoobTJbayxqXSBtb2QgbSkpIG1vZCBtKSBtb2QgbTsKICAgcmV0W2ksal06PXN1bTsKICBlbmQ7CmVuZDsKcHJvY2VkdXJlIG1teHAobjppbnQ2NDsgdmFyIHJldDptYXRyaXgpOwp2YXIgdG46aW50NjQ7CiAgICBpOmxvbmdpbnQ7CmJlZ2luCiB0bjo9bjsKIGZpbGxjaGFyKHJldCxzaXplb2YocmV0KSwwKTsKIGZvciBpOj0xIHRvIDMgZG8gcmV0W2ksaV06PTE7CiB3aGlsZSB0bj4wIGRvIGJlZ2luCiAgaWYgdG4gYW5kIDE9MSB0aGVuIG11bChyZXQsdG10LHJldCk7CiAgbXVsKHRtdCx0bXQsdG10KTsgdG46PXRuPj4xOwogZW5kOwplbmQ7CmJlZ2luCiByZWFkbG4obixtKTsKIGZvciBpOj0xIHRvIDMgZG8gYW5zW2ksaV06PTE7CiBkdDo9ZGlnaXQobik7IHB3Oj0xOwogZm9yIGk6PTEgdG8gZHQgZG8gYmVnaW4KICBtdFsxLDFdOj1wdyoxMDsgbXRbMSwyXTo9MDsgbXRbMSwzXTo9MDsKICBtdFsyLDFdOj0xOyBtdFsyLDJdOj0xOyBtdFsyLDNdOj0wOwogIG10WzMsMV06PTE7IG10WzMsMl06PTE7IG10WzMsM106PTE7CiAgdG10Oj1tdDsKICBpZiBpPD5kdCB0aGVuIHRpbWU6PTkqcHcKICAgICAgICAgICBlbHNlIHRpbWU6PW4tcHcrMTsKICBtbXhwKHRpbWUsdGVtcCk7CiAgbXVsKGFucyx0ZW1wLGFucyk7CiAgcHc6PXB3KjEwOwogZW5kOwogd3JpdGVsbihhbnNbMywxXSk7CmVuZC4=

MTMgMTM=

13 13