#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//#define ENVIRONMENT_LINKED_ACL

#ifdef ENVIRONMENT_LINKED_ACL
#include <atcoder/convolution>
#include <atcoder/lazysegtree>
#include <atcoder/segtree.hpp>
#endif

//#define ENVIRONMENT_LINKED_BOOST

#ifdef ENVIRONMENT_LINKED_BOOST
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#endif

using namespace std;
using uint = unsigned int;
using ll   = long long;
using ull  = unsigned long long;
#define REP(i, a, b)    for (ll i = a; i < b; ++i)
#define REPREV(i, a, b) for (ll i = a; i > b; --i)

const int _ = []() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    return 0;
}();

template <typename value_t>
void resize(value_t& v, const value_t& val) { v = val; }
template <typename vec_t, typename value_t, typename... arg_t>
void resize(std::vector<vec_t>& v, const value_t& val, int size, arg_t... arg) {
    v.resize(size);
    for (auto& c : v) resize(c, val, arg...);
}

template <typename A, typename B>
void chmin(A& a, const B& b) {
    a = min(a, static_cast<A>(b));
};
template <typename A, typename B>
void chmax(A& a, const B& b) {
    a = max(a, static_cast<A>(b));
};

template <typename T>
T modpow(T r, T n, T mod) {
    T ans = 1;
    T tmp = r % mod;
    while (n > 0) {
        if ((n & 1) > 0) {
            ans = ans * tmp % mod;
        }
        tmp = tmp * tmp % mod;
        n >>= 1;
    }
    return ans;
}
int main() {
    ll N, P;
    cin >> N >> P;
    constexpr ll mod = 1e9 + 7;
    ll ans           = (P - 1) * modpow<ll>(P - 2, N - 1, mod) % mod;
    cout << ans << endl;
    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;
using ll = long long;
const int N = 200005, P = 1e9 + 7;

char s[N];
int n, k;
ll f[N][17];

int to_num(char c)
{
    if ('0' <= c && c <= '9')
        return c ^ '0';
    return 10 + c - 'A';
}

void init()
{
    f[0][k] = 1;
    for (int i = 1; i < n; ++i)
        for (int j = k; ~j; --j)
            f[i][j] = (j * f[i - 1][j] + (16 - j) * f[i - 1][j + 1]) % P;
}

ll dp(char s[])
{
    ll res = 0;
    int i = 0, cnt = 0;
    bool st[16];
    memset(st, 0, sizeof st);
    for (int j = 1; j < n; ++j)
        res = (res + f[j][0] - f[j - 1][1]) % P;
    while (i < n)
    {
        int c = to_num(s[i]), l = n - i - 1;
        for (int j = 0; j < c; ++j)
            if (st[j])
                res = (res + f[l][cnt]) % P;
            else if (i || j)
                res = (res + f[l][cnt + 1] % P);
        if (!st[c])
            ++cnt, st[c] = true;
        if (++i == n && k == cnt)
            ++res;
    }
    return res;
}

int main()
{
    scanf("%s%d", s, &k);
    n = strlen(s);
    init();
    cout << dp(s) << endl;
}
