Grumpy Granny

All submissions for this problem are available.
After the death of their mother, Alphonse and Edward now live with Pinako and Winry. Pinako is worried about their obsession with Alchemy, and that they don't give attention to their studies. So to improve their mathematical solving ability, every day she gives a mathematical problem to solve. They can go out to practice Alchemy only after they have solved the problem. Help them by solving the given problem, so that they can go early today for their Alchemy practice. Given an array $A$ of $N$ nonnegative integers and two integers $K$ and $M$. Find the number of subsequences of array $A$ of length $K$ which satisfies the following property: Suppose the subsequence is $S = S_1S_2 \ldots S_K$, then for all $i$ such that $1 \leq i \leq K$, $$ S_i \% M = i \% M $$ should hold true, where $S_i$ denotes the $i$th element of the subsequence, using **1based indexing**. As the number of subsequences may be very large, output the answer modulo $1000000007$. PS: We also proposed the idea of making a lookalike clone through alchemy and keeping it in front of the study table. But it seems impossible to convince Edward to make a clone of his exact same height, and not taller than him. So solving the problem for him was a better choice. ### Input:  The first line contains $T$, the number of test cases. Then the test cases follow.  For every test case, the first line contains $N$, $K$ and $M$.  For every test case, the second line contains $N$ integers $A_{i}$ ( $1 \leq i \leq N$). ### Output: For every test case, output in a single line an integer denoting the number of valid subsequences modulo $10^9+7$ ### Constraints  $1 \leq T \leq 100$  $1 \leq N \leq 10^{4}$  $1 \leq K \leq N$  $\lceil \frac{K}{100}\rceil \leq M \leq 100\times K$  $0 \leq A_{i} \leq 10^{9}$ ### Sample Input: ``` 1 12 4 3 4 5 6 7 1 4 6 9 0 0 10 2 ``` ### Sample Output: ``` 8 ``` ### Explanation: The subsequences of length $4$, satisfying the given criteria are $[4, 5, 6, 7]$, $[4, 5, 6, 10]$, $[4, 5, 6, 10]$, $[4, 5, 6, 1]$, $[4, 5, 9, 10]$ ,$[4, 5, 6, 4]$ , $[4, 5, 0, 10]$ and $[4, 5, 0, 10]$. This accounts for a total of $8$ valid subsequences. Let us take one subsequence and see why it satisfies the given property. Consider $[4, 5, 9, 10]$.  $ S_1 \% M = 4 \% 3 = 1 = 1 \% 3 = 1 \% M $  $ S_2 \% M = 5 \% 3 = 2 = 2 \% 3 = 2 \% M $  $ S_3 \% M = 9 \% 3 = 0 = 3 \% 3 = 3 \% M $  $ S_4 \% M = 10 \% 3 = 1 = 4 \% 3 = 4 \% M $ All the valid $i$ satisfy the condition, and hence this is a valid subsequence.Author:  sachin_yadav 
Editorial  https://discuss.codechef.com/problems/GRUMPMA 
Tags  dcod2019, dynamicprogramming, easy, sachin_yadav, sachin_yadav, subsequence 
Date Added:  19102019 
Time Limit:  1 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. 