Problem: A grid of r × c is given.
Numbers from 1 to 8 are written on some squares on the grid.


<image>

It is necessary to connect the squares with numbers and the squares with other numbers with a line.
For the squares with numbers written on them, it is necessary to connect lines with other squares as many as the number written on that square.
However, the lines can be connected only in the vertical and horizontal directions, and up to two lines can be connected in one direction.
<image>

It cannot be connected by a line across other numbers.
<image>

In addition, it is not possible to tie them so that they intersect as follows.
<image>

Since the grid is given as input, please count how many ways there are ways to correctly connect all the squares with numbers.



Input

The input is given in the following format.


r c
grid1
..
..
..
gridr-1


gridi is a string of length c, consisting of numbers from 1 to 8 or ".".

Input meets the following constraints
1 ≤ r, c ≤ 10

Output

Divide the answer value by 100,000,007 and output the remainder on one line

Examples

Input

3 3
.1.
1.1
.1.


Output

0


Input

1 3
1.1


Output

1


Input

3 3
4.2
...
2..


Output

1


Input

7 7
2.3.1.1
.......
2......
.......
..3.3..
.......
2.2.4.3


Output

10

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;


const int mod = 100000007;
struct Mod {
public:
	int num;
	Mod() : Mod(0) { ; }
	Mod(long long int n) : num((n % mod + mod) % mod) {
		static_assert(mod<INT_MAX / 2, "mod is too big, please make num 'long long int' from 'int'");
	}
	Mod(int n) : Mod(static_cast<long long int>(n)) { ; }
	operator int() { return num; }
};

Mod operator+(const Mod a, const Mod b) { return Mod((a.num + b.num) % mod); }
Mod operator+(const long long int a, const Mod b) { return Mod(a) + b; }
Mod operator+(const Mod a, const long long int  b) { return b + a; }
Mod operator++(Mod &a) { return a + Mod(1); }
Mod operator-(const Mod a, const Mod b) { return Mod((mod + a.num - b.num) % mod); }
Mod operator-(const long long int a, const Mod b) { return Mod(a) - b; }
Mod operator--(Mod &a) { return a - Mod(1); }
Mod operator*(const Mod a, const Mod b) { return Mod(((long long)a.num * b.num) % mod); }
Mod operator*(const long long int a, const Mod b) { return Mod(a)*b; }
Mod operator*(const Mod a, const long long int b) { return Mod(b)*a; }
Mod operator*(const Mod a, const int b) { return Mod(b)*a; }
Mod operator+=(Mod &a, const Mod b) { return a = a + b; }
Mod operator+=(long long int &a, const Mod b) { return a = a + b; }
Mod operator-=(Mod &a, const Mod b) { return a = a - b; }
Mod operator-=(long long int &a, const Mod b) { return a = a - b; }
Mod operator*=(Mod &a, const Mod b) { return a = a * b; }
Mod operator*=(long long int &a, const Mod b) { return a = a * b; }
Mod operator*=(Mod& a, const long long int &b) { return a = a * b; }
Mod operator^(const Mod a, const int n) {
	if (n == 0) return Mod(1);
	Mod res = (a * a) ^ (n / 2);
	if (n % 2) res = res * a;
	return res;
}
Mod mod_pow(const Mod a, const long long  int n) {
	if (n == 0) return Mod(1);
	Mod res = mod_pow((a * a), (n / 2));
	if (n % 2) res = res * a;
	return res;
}
Mod inv(const Mod a) { return a ^ (mod - 2); }
Mod operator/(const Mod a, const Mod b) {
	assert(b.num != 0);
	return a * inv(b);
}
Mod operator/(const long long int a, const Mod b) {
	return Mod(a) / b;
}
Mod operator/=(Mod &a, const Mod b) {
	return a = a / b;
}


long long int getid(int x, int y, const vector<int>&v, int l) {
	long long int id = 0;
	id += x;
	id *= 15;
	id += y;
	for (int i = 0; i < v.size(); ++i) {
		assert(v[i] >= 0 && v[i] <= 2);
		id *= 31;
		id += v[i];
	}
	id *= 31;
	id += l;
	return id;
}
map<long long int, Mod>memo;
int R, C;
vector<vector<int>>field;
Mod getans(int x, int y, const vector<int>&v,int l) {
	assert(x < C);
	assert(R != y || !x);
	const  long long int id = getid(x, y, v, l);
	if (memo.find(id) != memo.end()) {
		return memo[id];
	}
	else {
		if (y == R) {
			bool ok = true;
			if (l)ok = false;
			if (!all_of(v.begin(), v.end(), [](const int n) {return n == 0; }))ok = false;
			return memo[id] = ok;
		}
		else {
			if (x == 0) {
				if (l)return memo[id] = 0;
			}
			if (field[y][x]) {
				Mod ans = 0;
				for (int lnum = 0; lnum <= 2;lnum++) {
					int dnum = field[y][x] - l - v[x]-lnum;
					if (dnum < 0 || dnum>= 3)ans += 0;
					else {
						int nexty = y, nextx = x + 1;
						vector<int>nextv(v);
						if (nextx == C) {
							nextx = 0;
							nexty++;
						}
						nextv[x] = dnum;
						ans += getans(nextx, nexty, nextv, lnum);
					}
				}
				return memo[id] = ans;
			}
			else {
				if (l&&v[x])return memo[id] = 0;
				else {
					int nexty = y, nextx = x + 1;
					vector<int>nextv(v);
					if (nextx == C) {
						nextx = 0;
						nexty++;
					}
					return memo[id]=getans(nextx, nexty,v, l);
				}
			}
		}
	}
	assert(false);
	return memo[id];
}
int main() {
	cin >> R >> C;
	field = vector<vector<int>>(R, vector<int>(C));
	for (int i = 0; i < R; ++i) {
		string st; cin >> st;
		for (int j = 0; j < C; ++j) {
			if (st[j] == '.')field[i][j] = 0;
			else field[i][j] = st[j] - '0';
		}
	}
	vector<int>v(C);
	Mod ans = getans(0, 0, v, 0);
	cout << ans << endl;
	return 0;
}