Loom Motif Crossing Count

A textile inspector is auditing a woven fabric sample for a specific dye motif. The fabric is represented as a grid of dyed threads: m rows (weft threads) by n columns (warp threads), where each cell holds one lowercase letter denoting a thread color. The inspector also has a target motif — a string of lowercase letters representing a sequence of thread colors.

A cell is horizontally woven if it lies within some contiguous run of cells in its row that reads exactly the motif from left to right. A cell is vertically woven if it lies within some contiguous run of cells in its column that reads exactly the motif from top to bottom. A cell is doubly woven if it is both horizontally woven and vertically woven — the horizontal run and the vertical run covering it do not need to share any particular starting position, and occurrences within the same row or column may overlap each other.

Count how many cells of the fabric are doubly woven.

Input format

Line 1: two integers m and n — the number of rows and columns of the fabric grid. Lines 2 to m+1: m strings, each of length n, consisting of lowercase English letters — the fabric grid, row by row. Line m+2: a string — the motif.

Output format

A single integer — the number of doubly woven cells.

Constraints

• 1 <= m, n <= 200
• 1 <= length of motif <= min(m, n)
• all strings consist only of lowercase English letters (a-z).

3 3
aba
bab
aba
ab

4

2 2
ab
cd
xy

0