#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 4000000000000000000 //オーバーフローに注意
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




#define SIZE 2005

ll H,W;
ll tate[SIZE][SIZE],yoko[SIZE][SIZE],naname[SIZE][SIZE],dp[SIZE][SIZE];
char base_map[SIZE][SIZE];
char work[SIZE][SIZE];

int main(){

	scanf("%lld %lld",&H,&W);

	for(int row = 0; row < H; row++){
		scanf("%s",base_map[row]);
		for(int col = 0; col < W; col++){

			work[row+1][col+1] = base_map[row][col];
		}
	}

	for(ll row = 0; row <= H; row++){
		for(ll col = 0; col <= W; col++){

			tate[row][col] = 0;
			yoko[row][col] = 0;
			naname[row][col] = 0;
			dp[row][col] = 0;
		}
	}

	tate[1][1] = 1;
	yoko[1][1] = 1;
	naname[1][1] = 1;
	dp[1][1] = 1;

	//1行目
	for(ll col = 2; col <= W; col++){
		if(work[1][col] == '#')continue;

		dp[1][col] = yoko[1][col-1];
		yoko[1][col] = (dp[1][col]+yoko[1][col-1])%MOD;
		tate[1][col] = dp[1][col];
		naname[1][col] = dp[1][col];
	}

	for(ll row = 2; row <= H; row++){
		for(ll col = 1; col <= W; col++){
			if(work[row][col] == '#')continue;

			dp[row][col] = (yoko[row][col-1]+tate[row-1][col]+naname[row-1][col-1])%MOD;
			yoko[row][col] = (dp[row][col]+yoko[row][col-1])%MOD;
			tate[row][col] = (dp[row][col]+tate[row-1][col])%MOD;
			naname[row][col] = (dp[row][col]+naname[row-1][col-1])%MOD;
		}
	}

	printf("%lld\n",dp[H][W]);

	return 0;
}

#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...)name
#define _rep(i,n)repi(i,0,n)
#define repi(i,a,b)for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; using ll = long long; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int main() {
    int N, M;
    cin >> N >> M;
    vv<bool> graph = vvec(N, N, false);
    rep(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a][b] = true;
    }

    vector<bool> is_perfect(1 << N, true);
    rep(s, 1 << N) {
        rep(i, N - 1) rep(j, i + 1, N) {
            if ((s >> i & 1) == 0 || (s >> j & 1) == 0) continue;
            if (!graph[i][j]) is_perfect[s] = false;
        }
    }

    vector<int> dp(1 << N, INF);
    dp[0] = 0;
    rep(s, 1, 1 << N) {
        if (is_perfect[s]) {
            dp[s] = 1;
            continue;
        }
        for (int t = s; t > 0; --t) {
            t &= s;
            dp[s] = min(dp[s], dp[t] + dp[s ^ t]);
        }
    }

    write(dp[(1 << N) - 1]);
}
