#include <iostream>
#include <string>
using namespace std;
#define stmax (1 << 19)
#define pmax 21
#define nmax 19

char buff[nmax*2], C[nmax];
int N, P;
long long A[stmax][pmax];

int NR(char x) {
    return x - '0';
}

int main() {
    FILE *f1=fopen("ratphu.in", "r"), *f2=fopen("ratphu.out", "w");
    int i, j, p, q, rr;

    fgets(buff, sizeof(buff), f1);
    i = 0;
    while(buff[i] != ' ') {
         C[i+1] = buff[i];
         i++;
    }
    i++;
    while(buff[i] != '\n') {
         P = P*10 + NR( buff[i] );
         i++;
    }
    N = strlen(C+1);

    for(i=0; i<P; i++) {
         A[0][i] = 1;
    }

    for(i=1; i<(1 << N); i++) {
         p = i;
         int ok = 0;
         for(j=1; j<=N; j++) {
              if(p % 2) {
                   ok++;
                   q = j;
              }
              p = p/2;
         }
         if(ok == 1) {
              A[i][NR(C[q]) % P] = 1;
              continue;
         }
         p = i;
         for(j=1; j<=N; j++) {
              if(p % 2) {
                   q = i - (1 << (j-1));
                   for(rr=0; rr<P; rr++) {
                        A[i][(rr*10 + NR(C[j])) % P] += A[q][rr];
                   }
              }
              p = p/2;
         }
    }

    fprintf(f2, "%lld\n", A[(1 << N) - 1][0]);
    fclose(f1); fclose(f2);
    return 0;
}