// ＵＴＦ−８

#include<bits/stdc++.h>

using namespace std;
using ll = long long int;
using lc = complex<ll>;

/* #include<atcoder/all> */
/* using namespace atcoder; */

template<class T>bool chmax(T &a, const T &b) { return (a<b ? (a=b,1) : 0); }
template<class T>bool chmin(T &a, const T &b) { return (a>b ? (a=b,1) : 0); }

int main(void) {
    constexpr ll MOD = 1 ? 1e9+7 : 998244353;
    const double PI = acos(-1);
    constexpr double eps = 1e-10;
    cout << fixed << setprecision(32);
    cin.tie(0); ios::sync_with_stdio(false);

    auto f = [&](char x) {
        if('0' <= x && x <= '9')
            return x - '0';
        return x - 'A' + 10;
    };

    if(1) {
        string n;
        ll k;
        cin >> n >> k;
        ll s = n.size();

        vector<vector<ll>> dq(s, vector<ll>(16+1)); // dp ぴったし, dq 未満
        dq[0][0] = 1;
        dq[0][1] = n[0] == '1' ? 0 : (f(n[0]) - 1);

        set<ll> v;
        v.insert(f(n[0]));
        for(ll i=1; i<s; i++) {
                (dq[i][0] += (dq[i-1][0])) %= MOD;
            for(ll j=0; j<=16; j++) {
                (dq[i][j] += (j * dq[i-1][j])) %= MOD;
                if(j == 0)
                    (dq[i][j+1] += ((15-j) * dq[i-1][j])) %= MOD;
                else if(j < 16)
                    (dq[i][j+1] += ((16-j) * dq[i-1][j])) %= MOD;
            }
            for(ll j=0; j<f(n[i]); j++) {
                (dq[i][v.size() + !v.count(j)] += 1) %= MOD;
            }
            v.insert(f(n[i]));
        }
        ll r = dq[s-1][k] + (v.size() == k);
        cout << (r % MOD) << endl;
    }

    return 0;
}


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pl = pair<ll, ll>;
const ll INF = ll(1e18);
const ll mod = ll(998244353);
const double pi = acos(-1);
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) <= (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n); (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define rnfor(i,a,b) for(ll (i) = (b) - 1; (i) >= (a); --(i))
#define pf(x) cout << (x) << endl
#define all(x) (x).begin(),(x).end()
#define yes pf("Yes")
#define no pf("No")
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

int multipf(vector<string>& s){
    cout << s[0];
    rep1(i, s.size() - 1)cout << " " << s[i];
    cout << endl;
    return 0;
}

int multipf(vector<ll>& n){
    cout << n[0];
    rep1(i, n.size() - 1)cout << " " << n[i];
    cout << endl;
    return 0;
}

ll gcd(ll a,ll b){
    if(a < b)swap(a, b);
    if(b == 0) return a;
    return gcd(b,a%b);
}
 
ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll factorial(ll n){
    ll ans = 1;
    rep1(i, n){
        ans *= i;
        ans %= mod;
    }
    return ans;
}

ll power(ll a, ll b, ll m){
    ll ans = 1;
    while(b) {
        if(b & 1LL) ans = ans * a % m;
        ans %= m;
        a = a * a;
        a %= m;
        b >>= 1;
    }
    return ans % m;
}

int main() {
  ll h,w;
  cin >> h >> w;
  vvl g(h,vl(w,0));
  rep0(i,h)rep0(j,w){
    char c;
    cin >> c;
    if(c=='#')g[i][j] = 1;
  }
  ll ans = 0;
  rep0(i,h-1)rep0(j,w-1){
    ll c = g[i][j]+g[i+1][j]+g[i][j+1]+g[i+1][j+1];
    if(c  == 1|| c == 3)ans++;
  }
  pf(ans);
  return 0;
}

