## 【状压DP】排列 – 阿里2020秋季校招

n < 1e15
m < 100

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 16, M = 110;
ll n, m;
ll f[1 << N][M];
vector<int> v;
bool vis[10];
int ze = 0;

int main()
{
// time_t startt = clock();

cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
int T;
T = 1;
while(T--)
{
cin >> n >> m;
while(n) v.push_back(n % 10), n /= 10;
sort(v.begin(), v.end());
for(int i = 0; i < v.size(); i++) if(v[i] == 0) ze++;

f[0][0] = 1;
for(int i = 0; i < 1 << v.size(); i++)
{
memset(vis, 0, sizeof vis);
for(int j = 0; j < v.size(); j++)
{
if(i & (1 << j)) continue;
if(vis[v[j]]) continue;
int mask = i | (1 << j);
if(mask < (1 << ze)) continue;
vis[v[j]] = 1;
for(int k = 0; k < m; k++)
{
f[mask][(k * 10 + v[j]) % m] += f[i][k];
}
}
}
cout << f[(1 << v.size()) - 1][0] << endl;
}
// cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
// cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}