Palindromes Machine

All submissions for this problem are available.
Dr. Hasan is one of the most famous inventors in the world. One day, he invented a wonderful machine in order to examine the possibility of generating new palindrome strings by merging other strings. Hasan's machine takes a sequence of strings $(A_1, A_2, \ldots, A_K)$ as the input; $K$ may be any positive integer. The length of each of these strings must be exactly $N$; for each valid $j$, let's denote the $j$th character of the $i$th string by $A_{i, j}$. The machine magically generates a string $B$ by merging these strings and it determines if $B$ is a palindrome. The string $B$ is generated as follows:  $B_1 = A_{1, 1}, B_2 = A_{2, 1}, \ldots, B_K = A_{K, 1}$  $B_{K+1} = A_{1, 2}, B_{K+2} = A_{2, 2}, \ldots, B_{2 \cdot K} = A_{K, 2}$  ...  $B_{(N1) \cdot K + 1} = A_{1, N}, B_{(N1) \cdot K + 2} = A_{2, N}, \ldots, B_{N \cdot K} = A_{K, N}$ Hasan wants to test his new machine, so he prepared $N$ strings $S_1, S_2, \ldots, S_N$. Each of these strings has length $N$. Now, he wants to choose a sequence of $K$ pairwise distinct indices $i_1, i_2, \ldots, i_K$, where $1 \le K \le M$, and run the machine with strings $(S_{i_1}, S_{i_2}, \ldots, S_{i_K})$. His goal is to make the machine report that the string it generated is a palindrome. Can you help Hasan with testing his machine and tell him the number of sequences of indices he can choose? Since the answer could be very large, compute it modulo $10^9+7$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $M$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains a single string $S_i$. ### Output For each test case, print a single line containing one integer — the number of sequences Hasan can choose, modulo $10^9+7$. ### Constraints  $1 \le T \le 100$  $1 \le N \le 10^3$  $1 \le M \le N$  $S_i = N$ for each valid $i$  $S_1, S_2, \ldots, S_N$ contain only lowercase English letters  the sum of $N$ over all test cases does not exceed $5 \cdot 10^3$ ### Example Input ``` 1 4 2 aaaa abcb abcb bcba ``` ### Example Output ``` 5 ``` ### Explanation **Example case 1:** Hasan can choose the following sequences of indices:  $(1)$: the input of the machine is ("aaaa") and the generated string $B$ is "aaaa"  $(2, 4)$: the input is ("abcb", "bcba") and $B$ is "abbccbba"  $(3, 4)$: the input is ("abcb", "bcba") and $B$ is "abbccbba"  $(4, 2)$: the input is ("bcba", "abcb") and $B$ is "bacbbcab"  $(4, 3)$: the input is ("bcba", "abcb") and $B$ is "bacbbcab"Author:  i_love_islam 
Editorial  https://discuss.codechef.com/problems/PALMACH 
Tags  combinatorics, cook110, dynamicprogramming, fft, i_love_islam, mediumhard, taran_1407 
Date Added:  18092019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 