A mosaic is a grid of lowercase letters with R rows and C columns. A trace of a word starts at some cell and steps repeatedly to a horizontally or vertically adjacent cell, spelling the word letter by letter, and never revisiting a cell within that trace.
Two traces are distinct if their sequences of visited cells differ. Count how many distinct traces spell the given target word.
Input format
Line 1: two integers R and C.
Next R lines: each a string of exactly C lowercase letters (one grid row).
Last line: the target word.
Output format
A single integer: the number of distinct traces that spell the word.
Constraints
- 1 <= R, C <= 4
- 1 <= length of the target word <= 8
- All letters are lowercase English letters.