EIGHT - Eight Directions Crossword

What is an Eight Directions Crossword? It's a filled crossword in which all the words are hidden in eight directions (up, down, left and right and also up-left, down-right etc.) You have to find these hidden words in each crossword.

Ðuro has made an N x N eight-directions-crossword. His crossword is a bit strange: you are given only one word and you have to find it in a crossword. To make things more difficult, you can skip some letters in the crossword while looking for the given word. More precisely, the given word is the subsequence of not necessarily consecutive letters in a row, column or a diagonal of the crossword in one of the eight directions.

Now you discover that, under these conditions, you can read the given word in the crossword in multiple ways. How many?

Input

In the first line of the input there is an integer N (2 = N = 1000), the crossword dimension, followed by space and the given word you are to find. This word has 2-10 letters.

N lines follow, representing the crossword. All letters in the crossword and in the given word are small letters of the English alphabet.

Output

Print the required number of ways. (This number will fit into int64 in Pascal or long long in C/C++.)

Example

input
2 aa
aa
aa

 

output

12
input
3 aa
aaa
aaa
aaa

 

output

56
input
8 silba
siolobba
oooaoooo
oooboooo
aooooooo
oboloooo
oolooooo
oooioooo
ooossooo

 

output

4

Added by:Adrian Satja Kurdija
Date:2011-10-30
Time limit:0.107s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:that would be me

hide comments
2016-07-06 14:52:54
Yeah, it can pass
2015-01-30 15:16:05 jkelava6
Does 8 * N^2 * L pass, or gets TLE?
L is length of the word!
2014-04-24 22:52:09 Marko Ljubisavljevic
third too
2014-04-09 13:34:30 Adrian Satja Kurdija
@Roman: No, you cannot use a letter twice or change direction while reading the word. It's 0.
2014-04-08 09:54:25 Roman
Can the word in the crossword use same letter more than one time?
i.e. What is the answer for test
2 aba
ab
cd
1 or 0?
2014-04-02 17:32:23 Adrian Satja Kurdija
@Jovan: read the second paragraph carefully.
2014-04-01 21:09:51 Jovan
I think that the second and third case have wrong output.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.