## CHECKMEET - March Of The King

The white king George lives all alone in a chessboard (A standard chessboard consists of

Wandering all alone with no purpose and literally bored to death, King George invented a new game to keep him occupied. King George has a

After completing his tour (the tour can be stopped anytime), George concatenates all the characters in the order of his travel to form a word. Since he has nothing better to do, the white king wants to know how many different ways he can complete the tour so that the secret word is formed afterward.

Two ways are considered different if a different square is visited at any moment. Note that the order in which the squares are visited also matters. As a consequence, for example the path

Formally the problem is as follows:

Let

**8**rows and columns). He lives alone because the evil black king Andrew killed all the other pieces in frustration after George beat him in a game of chess.Wandering all alone with no purpose and literally bored to death, King George invented a new game to keep him occupied. King George has a

*secret word*in his mind. It is the word he used to shout instead of the usual*checkmate*after beating the black king in a chess game. King George loves to march, so he decided to take a tour through the chessboard. He assigns a single lowercase letter to each square of the chessboard first. He can then start his tour from any square on the chessboard. From a square, the king can move to any neighboring square inside the board as in the game of chess . However, it is not allowed to move to the same square twice during the journey. In other words, all the squares visited by the king must be**distinct**.After completing his tour (the tour can be stopped anytime), George concatenates all the characters in the order of his travel to form a word. Since he has nothing better to do, the white king wants to know how many different ways he can complete the tour so that the secret word is formed afterward.

Two ways are considered different if a different square is visited at any moment. Note that the order in which the squares are visited also matters. As a consequence, for example the path

**(1, 2) -> (2, 1)**and**(2, 1) -> (1, 2)**are considered different.Formally the problem is as follows:

Let

**B(X, Y)**be the lowercase letter assigned to square**(X, Y)**. Also, let the*secret word*be**S**. Your task is to find the number of possible_{1}S_{2}... S_{K}*King's tours*. A King's tour is a sequence of coordinates**(X**satisfying:_{1}, Y_{1}), (X_{2}, Y_{2}), ... , (X_{K}, Y_{K})1 ≤ X _{i}, Y

_{i}≤ 8

B(X _{i}, Y

_{i}) = S

_{i}for all 1 ≤ i ≤ K

(X _{i}, Y

_{i}) ≠ (X

_{j}, Y

_{j}) for all 1 ≤ i < j ≤ K

max(|X _{i}- X

_{i + 1}|, |Y

_{i}- Y

_{i + 1}|) = 1 for all 1 ≤ i < K

### Input

The first line of input consists of a single integer**K**denoting the length of the secret word. The next line contains the secret word consisting of**K**lowercase letters. The next**8**lines each contain**8**characters describing the lowercase letters assigned to the chessboard in row-major order.### Constraints

1 ≤ K ≤ 11 ### Output

Print a single line containing a single integer denoting the number of different tours forming the secret word.### Sample Input

2 aa aabbbbbb aabbbbbb bbbbbbbb bbbbbbbb bbbbbbbb bbbbbbbb bbbbbbbb bbbbbbbb

### Sample Output

12

### Sample Input

9 checkmate checkmat checkmee checkmat checkmee checkmat checkmee checkmat checkmee

### Sample Output

7698

### Reference

HackerRank - March Of The KingAdded by: | sgtlaugh |

Date: | 2020-02-25 |

Time limit: | 3s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Own Problem, Used in HackerRank |