#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  REP(i, SZ(v)) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << "(" << p.first << " " << p.second << ")";
}

template<class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template<class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;


template<int m>
struct mint {
  int x;

  mint(ll x = 0) : x(((x % m) + m) % m) {}

  mint operator-() const { return x ? m - x : 0; }

  mint &operator+=(mint r) {
    if ((x += r.x) >= m) x -= m;
    return *this;
  }

  mint &operator-=(mint r) {
    if ((x -= r.x) < 0) x += m;
    return *this;
  }

  mint &operator*=(mint r) {
    x = ((ll) x * r.x) % m;
    return *this;
  }

  mint inv() const { return pow(m - 2); }

  mint &operator/=(mint r) { return *this *= r.inv(); }

  friend mint operator+(mint l, mint r) { return l += r; }

  friend mint operator-(mint l, mint r) { return l -= r; }

  friend mint operator*(mint l, mint r) { return l *= r; }

  friend mint operator/(mint l, mint r) { return l /= r; }

  mint pow(ll n) const {
    mint ret = 1, tmp = *this;
    while (n) {
      if (n & 1) ret *= tmp;
      tmp *= tmp, n >>= 1;
    }
    return ret;
  }

  friend bool operator==(mint l, mint r) { return l.x == r.x; }

  friend bool operator!=(mint l, mint r) { return l.x != r.x; }

  friend ostream &operator<<(ostream &os, mint a) {
    return os << a.x;
  }

  friend istream &operator>>(istream &is, mint &a) {
    ll x;
    is >> x;
    a = x;
    return is;
  }
};

using Int = mint<MOD>;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int h, w; cin >> h >> w;
  vector<vector<bool>> v(h, vector<bool>(w));
  REP(i, h) {
    string s; cin >> s;
    REP(j, w) {
      v[i][j] = s[j] == '.';
    }
  }

  vector<vector<Int>> dp(h, vector<Int>(w, 0));
  dp[0][0] = 1;

  // 右移動
  vector<vector<Int>> su1(h+1, vector<Int>(w+1));
  // 下移動
  vector<vector<Int>> su2(h+1, vector<Int>(w+1));
  // 右下移動
  vector<vector<Int>> su3(h+1, vector<Int>(w+1));

  su1[1][1] = 1;
  su2[1][1] = 1;
  su3[1][1] = 1;

  REP(i, h) {
    REP(j, w) {
      if(i == 0 && j == 0) continue;
      if(!v[i][j]) continue;
      dp[i][j] = su1[i+1][j] + su2[i][j+1] + su3[i][j];
      su1[i+1][j+1] = su1[i+1][j] + dp[i][j];
      su2[i+1][j+1] = su2[i][j+1] + dp[i][j];
      su3[i+1][j+1] = su3[i][j] + dp[i][j];
    }
  }


  cout << dp[h-1][w-1] << endl;

  return 0;
}




























































#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int) 2e5 + 7;
const int A = 18;
const int M = (int) 1e9 + 7;

int add(int a, int b) {
  a += b;
  if (a >= M) return a - M;
  if (a < 0) return a + M;
  return a;
}

int mul(int a, int b) {
  return a * (ll) b % M;
}

int n, k, dig[N], f[A], pre, dp[A][N][A];
string s;

void compute_dp() {
  for (int bef = 0; bef <= 16; bef++) {
    dp[bef][0][bef] = 1;
    for (int i = 0; i <= n; i++) {
      for (int c = bef; c <= 16; c++) {
        dp[bef][i + 1][c] = add(dp[bef][i + 1][c], mul(c, dp[bef][i][c]));
        dp[bef][i + 1][c + 1] = add(dp[bef][i + 1][c + 1], mul(16 - c, dp[bef][i][c]));
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  ///freopen ("input", "r", stdin);
  cin >> s >> k;
  n = (int) s.size();
  for (int i = 1; i <= n; i++) {
    char c = s[i - 1];
    if ('0' <= c && c <= '9') dig[i] = c - '0';
    else dig[i] = 10 + c - 'A';
  }
  compute_dp();
  int ret = 0;
  for (int dim = 1; dim < n; dim++) {
    int init = ret;
    ret = add(ret, dp[1][dim - 1][k]);
  }
  ret = mul(ret, 15);
  for (int dif = 1; dif <= n; dif++) {
    if (dif - 1 >= 1) {
      f[dig[dif - 1]]++;
      pre += (f[dig[dif - 1]] == 1);
    }
    int start = 0;
    if (dif == 1) {
      start = 1;
    }
    int init = ret;
    for (int x = start; x < dig[dif]; x++) {
      int before = pre + (f[x] == 0);
      ret = add(ret, dp[before][n - dif][k]);
    }
  }
  int cntdif = 1;
  sort(s.begin(), s.end());
  for (int i = 1; i < n; i++) cntdif += (s[i] != s[i - 1]);
  ret = add(ret, (cntdif == k));
  cout << ret << "\n";
}
