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 <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <cassert>
using namespace std;
inline int toInt(string s) {int v; istringstream sin(s); sin>>v; return v;}
template<class T> inline string toString(T x) {ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define EACH(t,i,c) for(t::iterator i=(c).begin(); i!=(c).end(); ++i)
const double EPS = 1e-10;
const double PI = acos(-1.0);

const int MAX_MASK=59049;
int dp[11][10][MAX_MASK][3]={};
int mask_size=0;

int getbit(int b,int p){
	REP(i,p){
		b/=3;
	}
	return b%3;
}

int substMask(int mask,int p){
	int minus=getbit(mask,p);
	REP(i,p){
		minus*=3;
	}
	return mask-minus;
}
int addMask(int mask,int p,int v){
	REP(i,p){
		v*=3;
	}
	return mask+v;
}
int getNewMask(int mask,int p,int v){
	return addMask(substMask(mask,p),p,v);
}

const int MOD=100000007;

int main(){
	int r,c;
	cin>>r>>c;
	vs grid(r);
	REP(i,r){
		cin>>grid[i];
	}
	mask_size=pow(3,c);
	dp[0][0][0][0]=1;
	REP(y,r)REP(x,c){
		if(grid[y][x]!='.'){
			REP(mask,mask_size)REP(lmask,3){
				int remain=grid[y][x]-'0';
				remain-=getbit(mask,x);
				remain-=lmask;
				if(remain>=0&&remain<=4){
					if(x<c-1){
						REP(i,remain+1){
							int right=(remain-i);
							if(i>=0&&i<=2&&right>=0&&right<=2){
								int nm=getNewMask(mask,x,i);
								dp[y][x+1][nm][right]+=dp[y][x][mask][lmask];
								dp[y][x+1][nm][right]%=MOD;
							}
						} 
					}else{
						if(remain>=0&&remain<=2){
							dp[y+1][0][getNewMask(mask,x,remain)][0]+=dp[y][x][mask][lmask];
							dp[y+1][0][getNewMask(mask,x,remain)][0]%=MOD;
						}
					}
				}
			}
		}else{
			REP(mask,mask_size){
				if(x<c-1){
					REP(lmask,3){
						if(getbit(mask,x)&&lmask){
							continue;
						}
						dp[y][x+1][mask][lmask]=dp[y][x][mask][lmask];
					}
				}else{
					dp[y+1][0][mask][0]=dp[y][x][mask][0];
				}
			}
		}
	}

	//REP(k,pow(3,3)){
	//	REP(i,r){
	//		REP(j,c){
	//			cerr<<dp[i][j][k][0]<<dp[i][j][k][1]<<dp[i][j][k][2]<<" ";
	//		}
	//		cerr<<endl;
	//	}
	//	cerr<<endl;
	//}
	cout<<dp[r][0][0][0]<<endl;
}