Chef and the Number Sequence

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Chef has a sequence A consisting of N integers each lying between 1 and K, both inclusive. Now he wants to construct another sequence B of the same length also containing integers between 1 and K (again, both inclusive). Find out in how many ways he can construct the sequence B, such that the length of Longest Common Subsequence (LCS) of A and B is exactly L. As the answer could be large, print it modulo 10^{9} + 7.
Input
The first line of the input contains T denoting the number of test cases. Each test case contains two lines:
 The first line of each test case contains three space separated integers N, K, and L.
 The second line contains N space separated integers A_{1}, A_{2}, ... A_{N}.
Output
For each test case output the number of ways to construct B as described above. Output the result modulo 10^{9} + 7.Constraints
 1 ≤ T ≤ 10
 1 ≤ N,K ≤ 16
 1 ≤ L ≤ N
 The sequence A consists of integers between 1 and K (both inclusive).
Example
Input: 2 2 2 1 1 2 3 3 2 1 2 2 Output: 3 11
Explanation
First Example : There are total three possible valid sequences B : [1, 1], [2, 2] and [2, 1]. LCS of these sequences with sequence A is equal to 1. Note that [1, 2] is not a valid sequence as LCS of this and sequence A is equal to 2.
Second Example: The 11 ways are: [1, 1, 2], [1, 2, 1], [1, 2, 3], [1, 3, 2], [2, 1, 2], [2, 2, 1], [2, 2, 2], [2, 2, 3], [2, 3, 2], [3, 1, 2], [3, 2, 2].
Note
Two sequences of B are considered different if there is at least one position which contains different numbers in the sequences.Author:  rustinpiece 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/SEQLCS 
Tags  cook61, dp+bitmask, medium, rustinpiece 
Date Added:  1082015 
Time Limit:  4 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, 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. 