#include <cstdio>

FILE *fin=fopen("ratphu.in","r");
FILE *fout=fopen("ratphu.out","w");

int st[20];
int a[20];
bool ud[20];
long long nr;
int p;

inline int min(int a,int b)
{
    return a<b?a:b;
}

void count(int a, int b)
{
    long long res=1;
    for (int i=a; i<b; i++)
        res*=(i-a+1);
    nr+=res;
}

int valid(int k)
{
    int res=1;
    long long nmr;
    if (ud[st[k]])
        return 0;
    int tp=p;
    int pp=0;
    int dp=0;
    while (!(tp&1))
    {
        tp=tp>>1;
        pp++;
    }
    nmr=0;
    for (int i=k; i>=1; i--)
        nmr=nmr*10+a[st[k]];
    long long tnmr=nmr;
    while (!(tnmr&1))
    {
        tnmr=tnmr>>1;
        if (!tnmr)
        {
            dp=1000;
            break;
        }
        dp++;
    }
    if ((pp>dp)&&(k>dp))
        return 0;
    res*=(1<<(min(min(pp,dp),k)));
    if (!(p%5))
    {
        res*=5;
        if ((a[st[k]])%5)
            return 0;
    }
    if (!(nmr%p))
        return p;
    return res;
}

int main()
{
    long long n;
    int ncf=0;
    int scf=0;
    fscanf(fin,"%lld %d",&n,&p);
    while (n)
    {
        ud[ncf]=0;
        a[ncf++]=n%10;
        scf+=n%10;
        n/=10;
    }
    if ((!(p%9))&&(ncf%9))
    {
        fprintf(fout,"0\n");
        fclose(fin);
        fclose(fout);
        return 0;
    }
    if ((!(p%3))&&(ncf%3))
    {
        fprintf(fout,"0\n");
        fclose(fin);
        fclose(fout);
        return 0;
    }
    while (!(p%3))
        p/=3;
    int k;
    k=1;
    st[k]=-1;
    int tmpp=p;
    if (p==1)
        count(0,ncf);
        else
    while(k)
    {
        int tmp;
        if (st[k]>=0)
            ud[st[k]]=0;
        st[k]++;
        for (;st[k]<ncf; st[k]++)
        {
            if ((tmp=valid(k)))
                break;
        }
        if (st[k]==ncf)
        {
            k--;
            continue;
        }
        ud[st[k]]=1;
        tmpp=p/tmp;
        if (tmpp==1)
        {
            count(k,ncf);
            continue;
        }
        if (k!=ncf)
        {
            k++;
            st[k]=-1;
            continue;
        }
    }
    fprintf(fout,"%lld\n",nr);
    fclose(fin);
    fclose(fout);
    return 0;
}