ACM

#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
 
#define LL long long
int n , m = 8;
bool maze[11][9];
 
const int HashSize = 300007;
struct HashMap {
	int HashChart[HashSize] , sz;
	int MSK[HashSize];
	bool A[HashSize];
	bool B[HashSize];
	LL dp[HashSize];
	int next[HashSize];
	void clear() {
		sz = 0;
		memset(HashChart, -1, sizeof(int) * HashSize);
	}
	inline void push(int msk, bool a, bool b,LL val) {
		int x = (msk * 4 + a * 2 + b) % HashSize;
		for (int it = HashChart[x] ; it != -1 ; it = next[it]) {
			if (MSK[it] == msk && A[it] == a && B[it] == b) {
				dp[it] += val;
				return ;
			}
		}
		MSK[sz] = msk;
		dp[sz] = val;
		A[sz] = a;
		B[sz] = b;
		next[sz] = HashChart[x];
		HashChart[x] = sz ++;
	}
} HM[2];
HashMap *src = HM;
HashMap *des = HM + 1;
 
LL plugDP() {
	src->clear();
	src->push(0,0,0,1);
	for (int i = 0 ; i < n ; i ++) {
		for (int j = 0 ; j < m ; j ++) {
			des->clear();
			for (int k = 0 ; k < src->sz ; k ++) {
				int msk = src->MSK[k];
				LL val = src->dp[k];
				bool a = src->A[k];
				bool b = src->B[k];
				//printf("%d %d %d %d {",i,j,a,b);
				//for (int it = 0 ; it < 15 ; it ++) {
				//	printf("%d ",(msk >> it) & 1);
				//}
				//puts("}");
				if (j & 1) {
					bool p = ((msk >> (j*2)) & 1);
					bool q = (j == m - 1) ? false : ((msk >> (j*2+1)) & 1);
					int cnt = 0;
					if (p) cnt ++;
					if (q) cnt ++;
					if (a) cnt ++;
					if (b) cnt ++;
					if (maze[i][j] == true) {
						if (cnt == 0) {
							msk &= ~(1 << (j*2));
							msk &= ~(1 << (j*2+1));
							des->push(msk , false , false , val);
						}
						continue;
					}
					if (cnt > 2) continue;
					if (cnt == 2) {
						msk &= ~(1 << (j*2));
						msk &= ~(1 << (j*2+1));
						des->push(msk , false , false , val);
					} else if (cnt == 1) {
						//1
						int nmsk = msk;
						if (i != n - 1 && !maze[i+1][j]) {
			//				if (b && ((msk>>(j*2-1)) & 1))continue;//length 3
							nmsk |= (1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							des->push(nmsk , false , false , val);
						}
						//2
						if (j != m - 1 && !maze[i][j+1]) {
			//				if (q && ((msk>>(j*2+2)) & 1)) continue;//length 3
							msk &= ~(1 << (j*2));
							msk |= (1 << (j*2+1));
							des->push(msk , false , false , val);
						}
					} else if (cnt == 0) {
						if (j != m - 1 && i != n - 1 && !maze[i+1][j] && !maze[i][j+1]) {
							msk |= (1 << (j*2));
							msk |= (1 << (j*2+1));
							des->push(msk , false , false , val);
						}
					}
				} else {
					bool p = (j == 0) ? 0 : ((msk >> (j*2-1)) & 1);
					bool q = ((msk >> (j*2)) & 1);
					a = ((msk >> (j*2+1)) & 1);
					if (maze[i][j]) {
						if (!p && !q) {
							b = false;
							msk &= ~(1 << (j*2));
							msk &= ~(1 << (j*2+1));
							if (j) msk &= ~(1 << (j*2-1));
							des->push(msk , a , b , val);
						}
						continue;
					}
					if (p && q) {
						b = false;
						msk &= ~(1 << (j*2));
						msk &= ~(1 << (j*2+1));
						if (j) msk &= ~(1 << (j*2-1));
						des->push(msk,a,b,val);
					} else if (p || q) {
						//1
						int nmsk = msk;
						if (!maze[i][j+1]) {
			//				if (q && a) continue; //length 3
							b = true;
							nmsk &= ~(1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						if (i == n - 1) continue;
						//2
						if (!maze[i+1][j]) {
							nmsk = msk;
							b = false;
							nmsk |= (1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//3
						if (!maze[i+1][j+1]) {
							nmsk = msk;
							b = false;
							nmsk &= ~(1 << (j*2));
							nmsk |= (1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//4
						if (j && !maze[i+1][j-1]) {
			//				if (p && ((msk >> (j*2-2)) & 1)) continue;//length 3
							nmsk = msk;
							b = false;
							nmsk |= (1 << (j*2-1));
							nmsk &= ~(1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							des->push(nmsk , a , b , val);
						}
					} else {
						if (i == n - 1) continue;
						//1
						int nmsk = msk;
						if (!maze[i][j+1] && !maze[i+1][j]) {
							b = true;
							nmsk |= (1 << (j*2));
							nmsk &= ~(1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//2
						if (!maze[i+1][j+1] && !maze[i+1][j]) {
							nmsk = msk;
							b = false;
							nmsk |= (1 << (j*2));
							nmsk |= (1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						//3
						if (!maze[i+1][j+1] && !maze[i][j+1]) {
							nmsk = msk;
							b = true;
							nmsk &= ~(1 << (j*2));
							nmsk |= (1 << (j*2+1));
							if (j) nmsk &= ~(1 << (j*2-1));
							des->push(nmsk , a , b , val);
						}
						if (j && !maze[i+1][j-1]) {
							//4
							if (!maze[i][j+1]) {
								nmsk = msk;
								b = true;
								nmsk &= ~(1 << (j*2));
								nmsk &= ~(1 << (j*2+1));
								nmsk |= (1 << (j*2-1));
								des->push(nmsk , a , b , val);
							}
							//5
							if (!maze[i+1][j]) {
								nmsk = msk;
								b = false;
								nmsk |= (1 << (j*2));
								nmsk &= ~(1 << (j*2+1));
								nmsk |= (1 << (j*2-1));
								des->push(nmsk , a , b , val);
							}
							//6
							if (!maze[i+1][j+1]) {
								nmsk = msk;
								b = false;
								nmsk &= ~(1 << (j*2));
								nmsk |= (1 << (j*2+1));
								nmsk |= (1 << (j*2-1));
								des->push(nmsk , a , b , val);
							}
						}
					}
				}
			}
			swap(src,des);
		}
	}
	for (int i =0 ; i < src->sz ; i ++) {
		if (src->MSK[i] == 0 && src->A[i] == false && src->B[i] == false) return src->dp[i];
	}
	return 0;
}
int main() {
	int m;
	while (~scanf("%d%d",&n,&m)) {
		memset(maze , false , sizeof(maze));
		for (int i = 0 ; i < m ; i ++) {
			char str[3];
			scanf("%s",str);
			maze[ str[0] - 'A' ][ str[1] - 'A' ] = true;
		}
		printf("%lld\n",plugDP());
	}
	return 0;
}
/*
2 12
AC BC
AD BD
AE BE
AF BF
AG BG
AH BH
2 13
AB
AC BC
AD BD
AE BE
AF BF
AG BG
AH BH
3 7
BB AD BD CD BF AH CG
3 15
AA BA CA
AB BB CB
AC BC CC
AD BD CD 
BF AH CG
3 16
BB 
AD BD CD
AE BE CE
AF BF CF
AG BG CG
AH BH CH
*/