#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> fill(int r, int c, const T& t){ return v2<T>(r, vector<T>(c, t)); }

const int MOD = 1e9+7;

void solve(){
    int h, w;
    cin >> h >> w;
    v2<char> grid = fill(h, w, '?');
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            cin >> grid[i][j];
        }
    }

    v2<int> dp = fill(h, w, -1), horiz, vert, diag;
    horiz = vert = diag = dp;
    
    dp[0][0] = horiz[0][0] = vert[0][0] = diag[0][0] = 1;
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(!i&&!j) continue;
            if(grid[i][j] == '#'){
                dp[i][j] = horiz[i][j] = vert[i][j] = diag[i][j] = 0;
            }
            else{
                int h = (j-1>=0) ? horiz[i][j-1] : 0;
                int v = (i-1>=0) ? vert[i-1][j] : 0;
                int d = (i-1>=0 && j-1>=0) ? diag[i-1][j-1] : 0;

                dp[i][j] = ((ll)h+v+d)%MOD;
                horiz[i][j] = (dp[i][j] + h)%MOD;
                vert[i][j] = (dp[i][j] + v)%MOD;
                diag[i][j] = (dp[i][j] + d)%MOD;
            }
        }
    }

    cout << dp[h-1][w-1] << "\n";
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

#define PI 3.14159265359

int main() {
  int N;
  int64_t W;
  cin >> N >> W;
  vector<vector<int>> T(N, vector<int>(N));
  vector<int> v;
  for (int i = 0; i < N; i++){
    v.push_back(i);
    for (int j = 0; j < N; j++){
      cin >> T[i][j];
    }
  }
  v.erase(remove(v.begin(), v.end(), 0), v.end());
  int ans = 0;
  do {
    int64_t dist = 0;
    for (int i = 0; i < N - 2; i++) dist += T[v[i]][v[i + 1]];
    dist += T[0][v[0]] + T[v[N - 2]][0];
    if (dist == W) ans++;
  } while(next_permutation(v.begin(), v.end()));
  cout << ans << endl;
}
