J. Return of Puzzle Boy
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Puzzle Boy is back for more! Ben's favorite hobby is puzzles (which is why he's referred to as Puzzle Boy). After he easily solved Nic's previous puzzle, Nic wants to give him a different kind of challenge. Nic has devised a word game played with a starting dictionary. In this game, Ben and Nic take turns writing new words in the dictionary, with Ben starting first. The person who can't think of a word to add to the dictionary on their turn loses the game.

The original set of rules for words in the dictionary is as follows:

  • All of the words in the dictionary must be $$$m$$$ letters long.
  • Each word will only use the first $$$c$$$ letters of the English alphabet.
  • The words in the dictionary may not be distinct.

A newly added word $$$w$$$ also has to follow these additional rules:

  • The new word should be related to some word already in the dictionary. Therefore, there must exist some index $$$i$$$ and word $$$d$$$ that is already in the dictionary such that $$$w_i=d_i$$$.
  • The new word must be novel and unique. Therefore, there must exist some index $$$i$$$ where the letter $$$w_i$$$ is not used at index $$$i$$$ for any other word already in the dictionary.

Ben and Nic played a few rounds of the game with different starting dictionaries. At first, Ben would lose most of the time. But after saying "I understand it now," Ben started winning the majority of the games. To test whether Puzzle Boy truly solved the puzzle, Nic has challenged him to determine the number of different words he can add in the first turn of the game and win the game. Assume both Ben and Nic play optimally.

Input

The first line of input will consist of three integers $$$n$$$, $$$m$$$ $$$(2 \le n,m \le 10^3)$$$, and $$$c$$$ $$$(2 \le c \le 26)$$$ — the number of words in the dictionary, the length of each word, and the number of letters in the English alphabet that can be used.

The following $$$n$$$ lines will each consist of a single string of $$$m$$$ lowercase letters using only the first $$$c$$$ letters of the English alphabet.

It is guaranteed that Ben can add a word to the dictionary at the beginning of the game.

Output

Output a single integer: the number of starting words that Ben can add to the dictionary on his first turn and win the game. Since this number can be large, output it modulo $$$998244353$$$.

Examples
Input
2 3 2
aaa
aba
Output
2
Input
2 2 2
aa
aa
Output
0