Problem Description
Mr.Panda did a survey among N candidates.
In the survey, each candidate was given a questionnaire which contains M yes/no questions. It is guaranteed that each question was answered with a “Yes” or a “No” by each candidate.
Mr.Panda likes variety. He considers a question as a good question if there are at least one candidate answered “Yes” and at least one candidate answered “No” for that question.
Now Mr.Panda has collected all the questionnaires. He wants to do some statistical analysis based on the survey result.
Because Mr.Panda is super lazy, he wants to randomly pick some of the questionnaires as a sample.
For each possible subset of questions (excluding empty set), Mr.Panda wants to know the probability that all questions in the subset are good questions, assuming that questionnaires in the sample are chosen randomly so that sample can be any subset (including full set and empty set) of questionnaires with equal probability.
Could you help Mr.Panda solve this problem?
To simplify the problem, you are only required to calculate ( P1⋅2N mod 1000000007) ⊕ ( P2⋅2N mod 1000000007) ⊕ · · · ⊕ ( P2M−1· 2N mod 1000000007)
where Pi means the probability of i th subset of questions to be good questions. It is obvious that Pi⋅2N is always an integer.
“⊕” which is known as “bitwise exclusive or” corresponds to operator “^”in both C/C++ and Java.
“ mod ” which is known as “modulo” corresponds to operator “%” in both C/C++ and Java.
Input
The first line of the input gives the number of test cases, T.
T test cases follow. Each test case consists of two lines. The first line contains two integers N, the number of questionnaires, and M, the number of questions.
The second line contains N strings Q1,Q2,...,QN representing the answers in each questionnaire.
Each questionnaire Qi is given in the form of exact M charecters where each character can be either “Y” standing for “Yes” or “N” standing for “No”.
Output
For each test case, output one line containing “Case #x: y”, where x is the test case number(starting from 1) and y is the xor sum of the weighted probabilities.
limits
∙1≤T≤20.
∙1≤N≤105.
∙1≤M≤15.
Sample Input
2
2 2
NY YN
4 2
NN NY YN YY
Sample Output
Case #1: 1
Case #2: 7
