// Create by JJL
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <set>
#include <queue>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;

const int N=2010,mod=1e9+7;
char g[N][N];
int l[N][N],r[N][N],u[N][N],d[N][N],a[N][N];
#define int long long
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int qmi(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=(LL)res*a%mod;
        b>>=1;
        a=(LL)a*a%mod;
    }
    return res;
}
signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>g[i];
    int cnt=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(g[i][j]=='.'){
                 l[i][j]=(j-1>=0?l[i][j-1]:0)+1;
                 cnt++;
            }
            else l[i][j]=0;
        }
        for(int j=m-1;j>=0;--j){
            if(g[i][j]=='.') r[i][j]=(j+1<m?r[i][j+1]:0)+1;
            else r[i][j]=0;
        }
    }
    for(int j=0;j<m;++j){
        for(int i=0;i<n;++i){
            if(g[i][j]=='.') u[i][j]=(i-1>=0?u[i-1][j]:0)+1;
            else u[i][j]=0;
        }
        for(int i=n-1;i>=0;--i){
            if(g[i][j]=='.') d[i][j]=(i+1<n?d[i+1][j]:0)+1;
            else d[i][j]=0;
        }
    }

    int ans=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            if(g[i][j]=='.') a[i][j]=l[i][j]+r[i][j]+u[i][j]+d[i][j]-3;
           // cout<<a[i][j]<<" ";
        }
    }//cout<<"in\n";
    for(int i=0;i<n;++i){
        for(int j=0;j<m;++j){
            ans=(LL)(ans+(LL)(qmi(2,a[i][j])-1)*qmi(2,cnt-a[i][j])%mod)%mod;
        }
    }
    cout<<ans;
    return 0;
}

#include<iostream>
#include<cstring>
#include<cctype>
using namespace std;
const int BUF = 200005;
const int MOD = 1000000007;


int add(int a, int b) {
    return (a + b) % MOD;
}

int mul(int a, int b) {
    return 1LL * a * b % MOD;
}


string N;
int K;

void read() {
    cin >> N >> K;
}


int ch2v(char ch) {
    if (isdigit(ch)) {
        return ch - '0';
    } else {
        return ch - 'A' + 10;
    }
}

int rec(int idx, int nType, bool anyDigitOK, bool addedDigit,
        int dp[BUF][16][2][2], int digit2added[16]) {
    if (nType > K) return 0;
    if (idx == N.size()) return nType == K;
    
    int &ret = dp[idx][nType][anyDigitOK][addedDigit];
    if (ret != -1) return ret;

    ret = 0;
    
    if (!anyDigitOK) {
        int v = ch2v(N[idx]);
        
        // Add same digit as N
        ++digit2added[v];
        ret = add(ret, rec(idx + 1, nType + (digit2added[v] == 1), false, true, dp, digit2added));
        // cout << idx << ' ' << nType << ' ' << rec(idx + 1, nType + (digit2added[v] == 1), false, true, dp, digit2added) << "  aaa" << endl;
        --digit2added[v];

        // Add digit which is less than N
        for (int i = addedDigit ? 0 : 1; i < v; ++i) {
            ++digit2added[i];
            ret = add(ret, rec(idx + 1, nType + (digit2added[i] == 1), true, true, dp, digit2added));
            --digit2added[i];
        }
        
        // Don't add digit
        if (!addedDigit) {
            ret = add(ret, rec(idx + 1, nType, true, false, dp, digit2added));
        }
    } else if (!addedDigit) {
        // Add digit
        for (int i = 1; i < 16; ++i) {
            ++digit2added[i];
            ret = add(ret, rec(idx + 1, nType + (digit2added[i] == 1), true, true, dp, digit2added));
            //cout << idx << ' ' << nType << ' ' << rec(idx + 1, nType + (digit2added[i] == 1), true, true, dp, digit2added) << " bbb" << endl;
            --digit2added[i];
        }
        
        // Don't add digit
        ret = add(ret, rec(idx + 1, nType, true, false, dp, digit2added));
    } else {
        // Add already-added digit
        ret = add(ret, mul(nType, rec(idx + 1, nType, true, true, dp, digit2added)));
        
        // Add not-added digit
        if (nType < 16) {
            ret = add(ret, mul(16 - nType, rec(idx + 1, nType + 1, true, true, dp, digit2added)));
        }
    }

    return ret;
}


void work() {
    static int dp[BUF][16][2][2];
    memset(dp, -1, sizeof(dp));
    int digit2added[16] = {};
    
    cout << rec(0, 0, 0, 0, dp, digit2added) << endl;
}


int main() {
    read();
    work();
    return 0;
}
