First solution

From the given words we can build a trie, also known as a prefix tree. Imagine that we are in the root of the tree and can see $M$ subtrees. In each subtree, the words begin with the same letter, and that letter is different for all $M$ subtrees: we need to first choose all words from one of the subtrees, then all words from another subtree, and so on. Therefore, we can reduce the problem to $M$ separate subproblems which can be solved recursively.

If we have determined, for the $k^{\text{th}}$ subtree (using recursion), that words of that subtree can be ordered in $A_k$ ways, then the total number of orderings of all subtrees is the product of those numbers ($A_1\times A_2\times \cdots \times A_M$). However, we also need to include the number of orderings of the subtrees themselves, which is $M!$ and must be included in the product.

The prefix tree must be implemented carefully in order to be fast enough and not use up too much memory.

Second solution

Based on a similar idea, but simpler to implement (without prefix trees). We sort the words alphabetically. Next, we look at the first letter of all words and find $M$ blocks such that all words in a block have the same first letter. As in the first solution, the result is $M!$ times the product of solutions for individual blocks.

In the recursion, we need to find subblocks for each of the blocks. However, now we can ignore the first letter, since we know it is equal for all words in a block, so we can consider only the second letter. Analogously, in the deeper levels of recursion, we only need to consider the letters in positions corresponding to the current level. We conclude that the total complexity of the recursion is proportional to the total number of letters. Of course, the recursion here will be parameterized by the lower and upper bound of the current block and the index of the letter we need to observe.