Chef and Good Subsequences
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/SEPT19/hindi/GDSUB.pdf), [Bengali](http://www.codechef.com/download/translated/SEPT19/bengali/GDSUB.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/SEPT19/mandarin/GDSUB.pdf), [Russian](http://www.codechef.com/download/translated/SEPT19/russian/GDSUB.pdf), and [Vietnamese](http://www.codechef.com/download/translated/SEPT19/vietnamese/GDSUB.pdf) as well. Chef is given a sequence of prime numbers $A_1, A_2, \ldots, A_N$. This sequence has exactly $2^N$ subsequences. A subsequence of $A$ is *good* if it does not contain any two identical numbers; in particular, the empty sequence is good. Chef has to find the number of good subsequences which contain at most $K$ numbers. Since he does not know much about subsequences, help him find the answer. This number could be very large, so compute it modulo $1,000,000,007$. ### Input - The first line of the input contains two space-separated integers $N$ and $K$. - The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$. ### Output Print a single line containing one integer ― the number of good subsequences with size at most $K$, modulo $1,000,000,007$. ### Constraints - $1 \le K \le N \le 10^5$ - $2 \le A_i \le 8,000$ for each valid $i$ ### Subtasks **Subtask #1 (40 points):** $A_1, A_2, \ldots, A_N$ are pairwise distinct **Subtask #2 (60 points):** original constraints ### Example Input ``` 5 3 2 2 3 3 5 ``` ### Example Output ``` 18 ``` ### Explanation There is $1$ good subsequence with length $0$, $5$ good subsequences with length $1$, $8$ good subsequences with length $2$ and $4$ good subsequences with length $3$.
|Tags||anand20, dynamic-programming, namanbansal013, observations, sept19|
|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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.