var l,ans,n,m,q,ost,q1:int64;
i,j,t,p,x:longint;
s:string;
ok:boolean;
a,qq:array [0..300000,0..101] of int64;
aa,kol:array [0..200] of longint;
begin
read(q1,m);
str(q1,s);
l:=length(s);
for i:=1 to l do
begin
val(s[i],aa[i],p);
inc(kol[aa[i]]);
end;
for i:=1 to l do
if aa[i]>0 then a[1 shl (i-1),aa[i] mod m]:=1;
q:=(1 shl (l))-1;
for i:=1 to q do
begin
for j:=1 to l do
begin
if ((1 shl (j-1)) and i=0) then begin
ok:=true;
for x:=1 to j-1 do
if (aa[j]=aa[x]) and ((1 shl (x-1)) and i=0) then begin ok:=false; break; end;
for x:=j+1 to l do
if (aa[j]=aa[x]) and ((1 shl (x-1)) and i>0) then begin ok:=false; break; end;
if not(ok) then continue;
inc(qq[i,0]);
qq[i,qq[i,0]]:=j;
end;
end;
end;
for i:=1 to q do
begin
for j:=0 to m-1 do
begin
if a[i,j]=0 then continue;
for t:=1 to qq[i,0] do
begin
ost:=(j*10+aa[qq[i][t]]) mod m;
inc(a[i+(1 shl (qq[i][t]-1)),ost],a[i][j]);
end;
end;
end;
writeln(a[q][0]);
end.
dmFyIGwsYW5zLG4sbSxxLG9zdCxxMTppbnQ2NDsKICBpLGosdCxwLHg6bG9uZ2ludDsKICBzOnN0cmluZzsKICBvazpib29sZWFuOwogICAgYSxxcTphcnJheSBbMC4uMzAwMDAwLDAuLjEwMV0gb2YgaW50NjQ7CiAgICBhYSxrb2w6YXJyYXkgWzAuLjIwMF0gb2YgbG9uZ2ludDsKICAgYmVnaW4KICAgICByZWFkKHExLG0pOwogICAgIHN0cihxMSxzKTsKICAgICBsOj1sZW5ndGgocyk7CiAgICAgZm9yIGk6PTEgdG8gbCBkbwogICAgICAgYmVnaW4KICAgICAgICAgdmFsKHNbaV0sYWFbaV0scCk7CiAgICAgICAgIGluYyhrb2xbYWFbaV1dKTsKICAgICAgIGVuZDsKICAgICBmb3IgaTo9MSB0byBsIGRvCiAgICAgIGlmIGFhW2ldPjAgdGhlbiBhWzEgc2hsIChpLTEpLGFhW2ldIG1vZCBtXTo9MTsKICAgICBxOj0oMSBzaGwgKGwpKS0xOwogICAgIGZvciBpOj0xIHRvIHEgZG8KICAgICAgYmVnaW4KICAgICAgICBmb3Igajo9MSB0byBsIGRvCiAgICAgICAgIGJlZ2luCiAgICAgICAgICAgaWYgKCgxIHNobCAoai0xKSkgYW5kIGk9MCkgdGhlbiBiZWdpbgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgb2s6PXRydWU7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvciB4Oj0xIHRvIGotMSBkbwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGFhW2pdPWFhW3hdKSBhbmQgKCgxIHNobCAoeC0xKSkgYW5kIGk9MCkgdGhlbiBiZWdpbiBvazo9ZmFsc2U7IGJyZWFrOyBlbmQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGZvciB4Oj1qKzEgdG8gbCBkbwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGFhW2pdPWFhW3hdKSBhbmQgKCgxIHNobCAoeC0xKSkgYW5kIGk+MCkgdGhlbiBiZWdpbiBvazo9ZmFsc2U7IGJyZWFrOyBlbmQ7CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpZiBub3Qob2spIHRoZW4gY29udGludWU7CgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5jKHFxW2ksMF0pOwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcXFbaSxxcVtpLDBdXTo9ajsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGVuZDsKICAgICAgICAgZW5kOwogICAgICBlbmQ7CgogICAgIGZvciBpOj0xIHRvIHEgZG8KICAgICAgYmVnaW4KICAgICAgICBmb3Igajo9MCB0byBtLTEgZG8KICAgICAgICAgICBiZWdpbgogICAgICAgICAgICAgaWYgYVtpLGpdPTAgdGhlbiBjb250aW51ZTsKICAgICAgICAgICAgIGZvciB0Oj0xIHRvIHFxW2ksMF0gZG8KICAgICAgICAgICAgICBiZWdpbgogICAgICAgICAgICAgICAgb3N0Oj0oaioxMCthYVtxcVtpXVt0XV0pIG1vZCBtOwogICAgICAgICAgICAgICAgaW5jKGFbaSsoMSBzaGwgKHFxW2ldW3RdLTEpKSxvc3RdLGFbaV1bal0pOwogICAgICAgICAgICAgICAgZW5kOwogICAgICAgICAgIGVuZDsKICAgICAgZW5kOwogICAgICAgd3JpdGVsbihhW3FdWzBdKTsKICAgZW5kLg==