|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|3 초||512 MB||4||4||4||100.000%|
Imperturbable Captain of the Unterzee chases the Pirate-Poet. Their rivalry was set long ago and since then knows no limits. Every time the Captain arrives at the port where the Pirate-Poet was expected to be, they find nothing but the message from the Pirate-Poet acknowledging that she departed the port a few days ago and leaving the Captain with another line of never-ending masterpiece: the Zong of the Zee.
Both the Captain and the Pirate-Poet know that the end of the Zong will put an ultimate end to their rivalry. Once the Captain retrieves it, they will find the Pirate-Poet and the final clash will begin.
Port after port, line after line... Perhaps, the answer was there all along. The Captain knows they can’t possibly last long enough to witness the end of the Zong, thus the only thing they can do is to outplay the Pirate-Poet.
So far, every single line of the poem was an anagram of the first one. Moreover, the Captain suspects that all lines are obtained in the same way, namely by applying some fixed permutation π1, . . . , πn to the previous line. That is, the character on position i on a new line was on position πi on the previous one.
The Captain wants to recover the whole poem by guessing the intended permutation. But firstly they want to know how many variants they have to check. The Captain thoroughly copied every single line of the poem, m lines of n Unterzian letters each. Unfortunately, it is sometimes hard to understand the Captain, thus some of letters (but at most one per line) may be replaced by question marks (“?”), meaning that you are uncertain what letter exactly it is. You have to calculate the number of permutations π1, . . . , πn which are consistent with the given data: in other words, such permutations that there is a way to replace all “?” with some Unterzian letters so that each line of the poem is obtained from the previous one by applying this permutation.
Output the answer modulo 109 + 7. The Captain knows what to do with this information. Probably.
The first line of input contains two integers m and n (2 ≤ n, m ≤ 3000).
The i-th of the following m lines contains the i-th line of the poem. Each such line contains exactly n characters, each character being either an Unterzian letter or a question mark (“?”). Each line contains at most one question mark.
Each Unterzian letter has ASCII code between 33 and 126, except for “?” which has code 63.
Output a single integer which is the answer to the problem.
3 3 ib. .?b b.?
2 4 abb? ba?a