//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll mod(ll a){
  return a % MOD;
}

ll lcm(ll a,ll b){
  return a/gcd(a,b) * b;
}


vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}



int main(){
  ll h,w; cin >> h >> w;

  vector<vector<char>> table(h,vector<char>(w));

  rep(i,h){
    rep(j,w) cin >> table[i][j];
  }

  vvl cnttable(h,vl(w));
  vvl hsum(h,vl(w));
  vvl wsum(h,vl(w));
  vvl dsum(h,vl(w));

  ll now = 2; 

  rep(i,w){
    if(table[0][i] == '.'){
      if(i == 0 or i == 1){
        cnttable[0][i] = 1;
        hsum[0][i] = 1;
        dsum[0][i] = 1;
      }
      else{
        cnttable[0][i] = now;
        hsum[0][i] = now;
        dsum[0][i] = now;
        now *= 2;
        now = mod(now);
      }
    }
    else break;
  }

  now = 2;

  rep(j,h){
    if(table[j][0] == '.'){
      if(j == 0 or j == 1){
        cnttable[j][0] = 1;
        wsum[j][0] = 1;
        dsum[j][0] = 1;
      }
      else{
        cnttable[j][0] = now;
        wsum[j][0] = now;
        dsum[j][0] = now;
        now *= 2;
        now = mod(now);
      }
    }
    else break;
  }


  for(ll i=1; i < h; i++){
    for(ll j=1; j < w; j++){
      if(table[i][j] == '#') continue;

      cnttable[i][j] = hsum[i-1][j] + dsum[i-1][j-1] + wsum[i][j-1];
      cnttable[i][j] = mod(cnttable[i][j]);
      
      hsum[i][j] = hsum[i-1][j] + cnttable[i][j];
      wsum[i][j] = wsum[i][j-1] + cnttable[i][j];
      dsum[i][j] = dsum[i-1][j-1] + cnttable[i][j];

      hsum[i][j] = mod(hsum[i][j]); wsum[i][j] = mod(wsum[i][j]);
      dsum[i][j] = mod(dsum[i][j]);

      /*if(i == 2 and j == 1){
        cout << hsum[i-1][j] << dsum[i-1][j-1] << wsum[i][j-1] << hsum[i-1][j] + dsum[i-1][j-1] + wsum[i][w-1] << endl;
      }*/
    }
  }

  /*for(auto array : cnttable){
    for(ll x : array) cout << x;
    cout << endl;
  }
  
  cout << endl;

  for(auto array : hsum){
    for(ll x : array) cout << x;
    cout << endl;
  }
  
  cout << endl;
  
  for(auto array : wsum){
    for(ll x : array) cout << x;
    cout << endl;
  }

  cout << endl;

  for(auto array : dsum){
    for(ll x : array) cout << x;
    cout << endl;
  }*/

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


}



#include <bits/stdc++.h>

using namespace std;
#define ll int64_t

void solve()
{

    int n, m;
    cin >> n >> m;
    vector<int> f(n);
    for (int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        v--, u--;
        f[v] |= (1 << u);
        f[u] |= (1 << v);
    }
    for (int i = 0; i < n; i++)
        f[i] |= (1 << i);
    int st = 1 << n;
    vector<int> flag(1 << n);
    for (int i = 0; i < st; i++)
    {
        int o = 0;
        vector<int> tmp;
        for (int j = 0; j < n; j++)
        {
            if ((i >> j) & 1)
                o |= (1 << j), tmp.push_back(j);
        }
        int ok = 1;
        for (int j : tmp)
        {
            if ((f[j] & o) != o)
                ok = 0;
        }
        if (ok)
        {
             flag[i] = 1;
            
        }
           
    }
    vector<int> dp((1<<n), n);
    dp[0] = 0;
    for (int i = 1; i < st; i++)
    {
        for (int j = i; j; j = (j - 1) & i)
        {
            if (flag[j])
            {
                dp[i] = min(dp[j^i] + 1, dp[i]);
            }
        }
        
    }
    cout << dp.back() << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;

    while (T--)
    {
        solve();
    }
}