Woburn Challenge 2015-16 Round 3 - Senior Division

While Superman was preparing in secrecy for the fight to come, feelings of fever, rage and powerlessness were festering within the dark knight of Gotham. He can do nothing but watch as the planet praise an alien capable of annihilating it. The peace of Gotham he fought so long to protect is now compromised by a godly figure that has unworthily gained the world's reverence.

To take care of this threat for good, the masked billionaire will have to elaborate a plan like no other he's ever concocted. In preparation, Batman plans on doing some heavy-duty detective work to figure out Superman's weaknesses. The logical place to start is by determining his secret identity. After compiling an abundance of data on Superman's movements and past battles, as well as newspaper articles written about him, he will need a program that can efficiently cross-reference them to fill in the missing pieces and hopefully uncover the man behind Superman. As the new intern of the batcave, your first task is to write a cryptanalysis program that can process the compiled data to help Batman figure out who Superman really is.

The data that Batman has compiled consists of ~N~ ~(1 \le N \le 1\,000)~ uppercase, alphabetical strings ~S_1, \dots, S_N~, each of length ~M~ ~(1 \le M \le 500)~. A good detective knows that no data from the real world is ever fully complete or accurate, so Batman has decided to represent unknown information in the strings with wildcard letters denoted by question marks. Specifically, each of these ~N~ strings will only consist of uppercase letters from A to Z, as well as special wildcard characters (?). The instincts of the world's greatest detective tell him that it will be possible to transform all of these strings into the same string (any string ~X~ of Batman's choice, made up of ~M~ letters), and hopefully this will be the real name of Superman. To accomplish this, some of the letters in the strings may be replaced with other letters at a cost of ~1~ each. But for this method to be effective in actually extracting useful data, the number of letters changed must be as small as possible! The lower the total cost, the more likely it is for the result to be accurate. Each wildcard character can also be changed into any letter of Batman's choice, at no cost.

But measuring this cost is not definitive, so Batman would also like to know the "error" of the process. In particular, this error is defined as the number of different strings ~X~ that Batman can choose, such that all ~N~ strings can be transformed into ~X~ with this minimal cost. Knowing this error is important, because the larger the total number of possibilities, the less likely that ~X~ is the actual name of Superman. Since this error value can actually get very large, Batman doesn't care any more than the last ~3~ digits (if the error is in the thousands or more, the data is unreliable anyway). So you are only required to compute the error modulo ~1\,000~. For example, if the error is ~2\,016~, simply output ~16~. Fortunately, Batman is also a genius-level number theorist so he has made you aware of the following two identities, which may prove useful:

• ~(A + B) \bmod M = ((A \bmod M) + (B \bmod M)) \bmod M~
• ~(A \times B) \bmod M = ((A \bmod M) \times (B \bmod M)) \bmod M~

Will Batman be able to solve one of the greatest-kept secrets in the world to help him defeat the most dangerous being in the world? His fate rests in your hands.

Input Specification

The first line of input will contain two space-separated integers ~N~ and ~M~.
The next ~N~ lines will each contain a single string, where line ~i~ contains ~S_i~, for ~i = 1 \dots N~.

Output Specification

The output should be a single line consisting of two space-separated integers. The first integer should be the cost, i.e. the minimum possible number of letters which must be changed to allow all ~N~ words to be turned into the same word. The second integer should be the error, i.e. the number of ways in which this can be accomplished (modulo ~1\,000~).

Sample Input 1

4 9
??ARKKANT
CL?RK?ENT
SUPERGIRL
???RK?UNT

Sample Output 1

11 64

Explanation 1

All four strings can be turned into the word CLARKKENT with minimal cost. The second string can be transformed to that with no extra cost, since the wildcard characters line up. The last A is wrong in the first string, so it will take a cost of ~1~ to make it an E. The third string shares no matching letters whatsoever with CLARKKENT, and therefore all ~9~ letters of it should be swapped. Finally, the U in the last string is incorrect, and should be switched for an E at a cost of ~1~. Similarly, there are ~64~ other words that may be reached by making exactly ~11~ replacements.

Sample Input 2

1 3
???

Sample Output 2

0 576

Explanation 2

With only one string, any assignment of the wildcard characters to letters will suffice. Each one can independently be turned into any of the ~26~ letters, so there are ~26^3 = 17\,576~ possibilities. This set of data is clearly not that helpful for Batman.