Little Elephant and Movies
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Little Elephant from Zoo of Lviv likes to watch movies.
There are N different movies (numbered from 0 to N − 1) he wants to watch in some order. Of course, he will watch each movie exactly once. The priority of ith movie is Pi.
A watching of a movie is called exciting if and only if one of the following two conditions holds:
- This is the first watching.
- The priority of this movie is strictly greater than the maximal priority of the movies watched so far.
Let us call the number of exciting watchings the excitingness of the order.
Help him to find the number of different watching orders whose excitingness does not exceed K. Since the answer can be large, print it modulo 1000000007 (109+7).
The first line of input contains an integer T, denoting the number of test cases. Then T test cases follow.
The first line of each test case contains two space-separated integers N and K. The next line contains N space-separated integers P1, P2, ..., PN.
For each test case, print the number of different watching orders having at most K excitingness modulo 1000000007 (109+7).
- 1 ≤ T ≤ 10
- 1 ≤ K ≤ N ≤ 200
- 1 ≤ Pi ≤ 200
Input: 2 3 1 3 1 2 4 3 1 2 2 3 Output: 2 24
In the first case, there are two boring watching orders whose excitingness not greater than K=1: [3, 1, 2], [3, 2, 1]. Both watching orders have one exciting watching: the first watching.
In the second case, every watching order has at most 3 excitingness.
|Tags||easy-medium, feb14, witua|
|Time Limit:||4 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.