#include<iostream>

#include<cstring>

#define int long long

using namespace std;

const int maxs=(<<)+,maxm=;

int w[],cnt=-,m,n,f[maxs][maxm];

bool vis[];

signed main()

{

    for(cin>>n>>m;n;n/=)

        w[++cnt]=n%;

    f[][]=;

    for(int s=;s<<<cnt+;s++)

    {

        memset(vis,,sizeof(vis));

        for(int i=;i<=cnt;i++)

        {

            if(s==(<<i)&&!w[i])

                break;

            if(!(s&(<<i))||vis[w[i]])

                continue;

            vis[w[i]]=;

            for(int j=;j<m;j++)

                f[s][(j*+w[i])%m]=f[s][(j*+w[i])%m]+f[s^(<<i)][j];

        }

    }

    cout<<f[(<<cnt+)-][]<<endl;

    return ;

}