// Hareesh Nagarajan <hareesh AT symonds.net>

#include <iostream>
#include <string>
#include <vector>
#include <cstring>
#include <cassert>
#define ROW_MAX		50
#define COL_MAX		50
#define PATH_STR_MAX 	(1<<10)
#define INF		100000000
using namespace std;

typedef struct { int i, j; } point;

static inline void get_neighbors(const char grid[ROW_MAX][COL_MAX], const int i, const int j,
				 const int rows, const int cols, vector<point> &vp)
{
	point p;
	bool i_minus_1, i_plus_1, j_minus_1, j_plus_1;
	int sub_i, add_i, sub_j, add_j;

	i_minus_1 = i_plus_1 = j_minus_1 = j_plus_1= false;
	sub_i = i - 1;
	add_i = i + 1;
	sub_j = j - 1;
	add_j = j + 1;
	
	if(sub_i >= 0) i_minus_1 = true;
	if(add_i < rows) i_plus_1 = true;

	if(sub_j >= 0) {
		j_minus_1 = true; p.i = i; p.j = sub_j; vp.push_back(p);	//i, j-1
	}
	
	if(add_j < cols) {
		j_plus_1 = true; p.i = i; p.j = add_j; vp.push_back(p);		//i, j+1
	}
	
	if(i_minus_1) {
		p.i = sub_i; p.j = j; vp.push_back(p); 				//i-1, j
		if(j_minus_1) { p.j = sub_j; vp.push_back(p); } 		//i-1, j-1
		if(j_plus_1) { p.j = add_j; vp.push_back(p); } 			//i-1, j+1
	}
	
	if(i_plus_1) {
		p.i = add_i; p.j = j; vp.push_back(p); 				//i+1, j
		if(j_minus_1) { p.j = j - 1; vp.push_back(p); } 		//i+1, j-1
		if(j_plus_1) { p.j = j + 1; vp.push_back(p); } 			//i+1, j+1
	}
}

	

int compute(const char grid[ROW_MAX][COL_MAX], const char path[PATH_STR_MAX],
	    int &count, int i, int j, int rows, int cols, int path_iter, const int path_sz,
	    vector<point> vec[ROW_MAX * COL_MAX])
{
	if(path_iter >= path_sz) { count++; return 0; }
        if(count > INF) return -1;

	vector<point>::iterator iter;

	for(iter = vec[(rows * i) + j].begin(); iter < vec[(rows * i) + j].end(); iter++) {
		if(grid[iter->i][iter->j] == path[path_iter])
			compute(grid, path, count, iter->i, iter->j, rows, cols, path_iter + 1, path_sz,
				vec);
	}

	return 1;
}

int search_paths(const char grid[ROW_MAX][COL_MAX], const char path[PATH_STR_MAX],
		 int rows, int cols, const int path_sz, vector<point> vec[ROW_MAX * COL_MAX])
{
	int i, j, count;
	count = 0;

	for(i = 0; i < rows; i++) {
		for(j = 0; j < cols; j++) {
			if(grid[i][j] == path[0]) {
				if(compute(grid, path, count, i, j, rows, cols, 1, path_sz,
					   vec) < 0)
					return -1;
			}
		}
	}
	return count;
}

main()
{
	char path[PATH_STR_MAX];
	int rows, cols, path_sz, i, j;

	char grid[ROW_MAX][COL_MAX] = {
		{'A','A','A','A','A'},
		{'A','A','A','A','A'},
		{'A','A','A','A','A'},
		{'A','A','A','A','A'},
		{'A','A','A','A','A'}
	};
	strcpy(path, "AAAAAAAAAAA");

	rows = 5;
	cols = 5;
	path_sz = strlen(path);

	assert(rows < ROW_MAX);
	assert(cols < COL_MAX);
	assert(path_sz < PATH_STR_MAX);

        // Compute all neighbors
        vector<point> vec[ROW_MAX * COL_MAX];
	for(i = 0; i < rows; i++) {
		for(j = 0; j < cols; j++) {
			get_neighbors(grid, i, j, rows, cols, vec[(rows * i) + j]);			
		}
	}
	
	cout << search_paths(grid, path, rows, cols, path_sz, vec) << endl;
}