John Corner demands to generate words from his alphabet table. Each word is composed by traveling of alphabets in four directions (← left, ↑ up, → right, and ↓ down), starting from first alphabet (‘i’) until last alphabet (‘r’). When all words have been created, he would like to know how many words he has. Of course, it is possible to have some duplicated words and he also needs to know how many unique words he got. Please help him to finish these funny tasks.
Moving step explanation:
From the Figure above presented alphabet table that has the 3 row x 4 column.
Case: word length = 1,
Regarding to the alphabet table, take each alphabet starting from ‘i’ (top-left) to ‘r’ (right-down), then there are 12 result words (i c p c h i j k a c m r). Length =1, one alphabet means one word. In this case, there is no traveling in four directions (← ↑ → ↓) since the word is ended by the length (length = 1).
Case: word length = 2,
Take ‘i’ (top-left corner) from the alphabet table. ‘i’ cannot move left or up since there is no adjacent alphabets. ‘i’ can only move right and move down. Then, let move ‘i' to the right, the word will be “ic”. Let move ‘i’ down, the word will be “ih”.
Next step, take another adjacent alphabet ‘c’. ‘c’ can move in ordered left, right and down. The words will be “ci, cp, ci”. He repeats these steps until reaching the last alphabet (‘r’).
Case: word length = 3,
Use the previous travel steps. Thus, let move ‘i’ to the right, the word will be “ic”. (length = 2).
Then, continue to move for the word with length = 3
Then, all summarized words starting from the first alphabet will be “ici”, “icp”, “ici”, .... , then, repeat until reaching the last alphabet (‘r’)
Alphabet traveling restriction:
John has been participated ACM ICPC Thailand and he loves it very much. Therefore, he prefers to define “acm” as THREE forbidden alphabets. Any word contains any forbidden alphabets (‘a’ OR ‘c’ OR ‘m’ LOWERCASE only) will be discarded (examples: ici, ahi, and mrk will be rejected)
Remark: When he moves an alphabet to another alphabet, it can be moved back to a previous selected alphabet if it still satisfies the policy (moving four directions, word lengths and forbidden alphabets).
The first line of input contains three unsigned integers: the row “R” (0 < R < 11), the column “C” (0 < C < 11) of the alphabet table and the word length “L” (0 < L < 7) consecutively.
The following R lines represent the alphabet table. Each line is a row containing C characters without space. All given characters are smaller letters.
The first line is an integer calculated from the number of generated words with the length of L, and the second line is an integer calculated from the number of unique words of all words generated.