5988562.cpp

ll dp(int mask, int rem, bool first) { // first for not using the first digit as zero 
    if (!mask) {
        return rem ? 0 : 1;
    }
    ll &x = sv[mask][rem]; // memorization 
    if(x != -1)
        return x;
    x = 0;
    int m = mask;
    int used = 0;
    while (m) {
        int ind = (m & -m); // jumping on the 1's in the mask 
        m -= ind ;
        int i = pos[ind]; // get the index of the 2's power ( 4 -> 2 , 8 -> 3 , 16 -> 4)
        /*
        if you choosing the first number that shouldn't be zero
        if you choose a digit in that position don't use it again 
        */
        if ((first && s[i] == '0') || (used & (1 << (s[i] - '0'))))
            continue;
        int nm = mask & (~(1 << i)); // remove the cur digit from the mask
        // calculate the reminder of the mode
        int r = rem;
        r *= 10;
        int c = (s[i] - '0');
        r += c;
        used = used | (1 << c);
        r %= mod;
        x += dp(nm, r, 0);
    }
    return x;
}