{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eMr.Panda did a survey among N candidates.\u003cbr\u003eIn 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.\u003cbr\u003eMr.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.\u003cbr\u003eNow Mr.Panda has collected all the questionnaires. He wants to do some statistical analysis based on the survey result.\u003cbr\u003eBecause Mr.Panda is super lazy, he wants to randomly pick some of the questionnaires as a sample.\u003cbr\u003eFor 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.\u003cbr\u003eCould you help Mr.Panda solve this problem?\u003cbr\u003eTo simplify the problem, you are only required to calculate ( $P_1 · 2^N$ mod 1000000007) ♁ ( $P_2 · 2^N$ mod 1000000007) ♁ · · · ♁ ( $P_{2^M-1}$· $2^N$ mod 1000000007)\u003cbr\u003ewhere $P_i$ means the probability of i th subset of questions to be good questions. It is obvious that $P_i · 2^N$ is always an integer.\u003cbr\u003e“♁” which is known as “bitwise exclusive or” corresponds to operator “^”in both C/C++ and Java.\u003cbr\u003e“ mod ” which is known as “modulo” corresponds to operator “%” in both C/C++ and Java.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, T.\u003cbr\u003eT 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.\u003cbr\u003eThe second line contains N strings $Q_1, Q_2, ... , Q_N$ representing the answers in each questionnaire.\u003cbr\u003eEach questionnaire $Q_i$ is given in the form of exact M charecters where each character can be either “Y” standing for “Yes” or “N” standing for “No”.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"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.\u003cbr\u003e\u003ch2\u003elimits\u003c/h2\u003e\u003cbr\u003e$\\bullet 1 ≤ T ≤ 20.$\u003cbr\u003e$\\bullet 1 ≤ N ≤ 10^5.$\u003cbr\u003e$\\bullet 1 ≤ M ≤ 15.$"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2 2\r\nNY YN\r\n4 2\r\nNN NY YN YY\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\r\nCase #2: 7\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/50bfdb763bc92a9cf84f8a26b52304f5?v\u003d1715950351\"\u003e\u003c/center\u003e\u003cbr\u003e"}}]}