#include <set>
#include <iostream>
using namespace std;

constexpr int M = 1000000007;

long long modexp(int x, long long e, int m) {
    long long ans = 1, p = x % m;
    while (e > 0) {
        if (e % 2 != 0) ans = (ans * p) % m;
        p = (p * p) % m;
        e >>= 1;
    }
    return ans;
}

class ModComb {
    long long *fact, *facti;
    const int mod;
public:
    explicit ModComb(int n, int m) : mod(m) {
        fact = new long long[n+1];
        facti = new long long[n+1];
        fact[0] = 1; facti[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = (fact[i-1] * i) % m;
        // calc 1/n!
        long long &inv = facti[n], pw = fact[n];
        inv = 1;
        for (int e = mod-2; e > 0; e /= 2) {
            if (e&1) inv = inv * pw % mod;
            pw = pw * pw % mod;
        }
        for (int i = n-1; i > 0; i--) facti[i] = (facti[i+1] * (i+1)) % m;
    }

    ~ModComb() {
        if (fact) delete[] fact;
        if (facti) delete[] facti;
    }

    long long getFact(int n) const {
        return fact[n];
    }

    long long getFactInv(int n) const {
        return facti[n];
    }

    long long getComb(int n, int k) const {
        if (n < 0 || k < 0 || k > n) return 0;
        return fact[n] * facti[k] % mod * facti[n-k] % mod;
    }

    long long getPerm(int n, int k) const {
        if (n < 0 || k < 0 || k > n) return 0;
        return fact[n] * facti[n-k] % mod;
    }
};

ModComb mc(20, M);

long long f(int a, int b, int n) {
    long long ans = 0;
    for (int i = 0, s = (a % 2 == 0 ? 1 : -1); i <= a; i++, s = -s)
        ans += s * mc.getComb(a, i) * modexp(i+b, n, M) % M;
    // cerr << a << ' ' << b << ' ' << n << ' ' << ans << endl;
    return (ans % M + M) % M;
}

long long modinv(long long a, long long m) {
    long long x = m, y = a, p = 1, q = 0, r = 0, s = 1;
    while (y != 0) {
        long long u = x / y;
        long long x0 = y; y = x - y * u; x = x0;
        long long r0 = p - r * u, s0 = q - s * u;
        p = r; r = r0; q = s; s = s0;
    }
    return q < 0 ? q + m : q;
}

long long g(int k, int n) {
    long long c1 = f(k, 0, n) * mc.getComb(15, k) % M;
    long long c2 = f(k, 0, n) * mc.getComb(15, k-1) % M;
    long long c3 = c2 * (k - 1) % M * modinv(k, M) % M;
    return (c1 + c3) % M;
}

int bruteforce(string s, int k) {
    int n = 0;
    for (int i = 0; i < s.size(); i++) {
        const int v = isdigit(s[i]) ? s[i] - '0' : s[i] - 'A' + 10;
        n = n * 16 + v;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        string t;
        for (int j = i; j > 0; j /= 16) {
            int v = j % 16;
            t = string(1, v < 10 ? '0' + v : 'A' + v - 10) + t;
        }
        set<int> tmp(t.begin(), t.end());
        if (tmp.size() == k) ans++;
    }
    return ans;
}

int main() {
    string s; cin >> s;
    const int n = s.size();
    int k; cin >> k;
    int used = 0;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        const int v = isdigit(s[i]) ? s[i] - '0' : s[i] - 'A' + 10;
        for (int d = 0; d < v; d++) {
            if (i == 0 && d == 0) {
                for (int l = 1; l < n; l++) ans += g(k, l);
            } else {
                int b = __builtin_popcount(used);
                if ((used >> d & 1) == 0) b++;
                if (b > k) continue;
                // cerr << d << ' ' << b << endl;
                ans += f(k - b, b, n - i - 1) * mc.getComb(16 - b, k - b) % M;
            }
        }
        // cerr << v << ' ' << ans << endl;
        used |= 1 << v;
        if (__builtin_popcount(used) > k) break;
    }
    if (__builtin_popcount(used) == k) ans++;
    ans %= M;
    cout << ans << endl;

    // long long ans2 = bruteforce(s, k);
    // if (ans != ans2)
    //     cerr << "input " << s << ' ' << k << endl
    //          << "expect " << ans2 << ", got " << ans << endl;
}

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace std;
 
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx2")
 
#define sync ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
#define unq(a) sort(all(a));a.resize(unique(all(a)) - a.begin())
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
//#define endl '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937 rng(0);
using pii = pair<int , int>;
 
int inline max(const int x, const int y){return (x > y ? x : y);}
int inline min(const int x, const int y){return (x < y ? x : y);}
int inline abs(const int x){return (x < 0 ? -x : x);}

const int mod = 1e9 + 7;
ll pwr(ll x, ll y){
  ll r = 1;
  while(y > 0){
    if (y & 1){
      r = (r * x) % mod;
    }
    y >>= 1;
    x = (x * x) % mod;
  }
  return r;
}

int main(){
 
    #ifndef ONLINE_JUDGE 
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    sync

    int t = 1;
    //cin >> t;
    while(t--){
      ll n, p;
      cin >> n >> p;
      cout << ((p - 1) * pwr(p - 2, n - 1)) % mod << endl;
    }
    cerr << "processor time: " << clock() / (double) CLOCKS_PER_SEC << "s    ";
    return 0;
}