All submissions for this problem are available.
In the King's court, there is a bitter rivalry between the Mathematician and the Jester.
The King gives both of them an array A, and then the Mathematician begins asking the jester: "What is the maximum value of the elements of the array between position i and j?" The jester, being lazy, doesn't compute the maximum of all the elements, instead he just computes the maximum between the value A[i] and A[j] and tells it to the Mathematician.
The King supports the Jester, since his wit is what keeps the court distressed and calm. Hence, he wishes to give an array A such that no matter what values of i and j the Mathematician chooses, the Jester gives the correct answer. How many possible arrays are there of this sort, where the length of the array is N and each element of the array is between 1 and M.
Since the answer may be large, output the value modulo 1000000007.
- The first line consists of the number of test-cases T.
- The next T lines each contain two integers: M and N.
For each test-case, output the answer on a single line.
Input: 3 2 2 3 3 1 5 Output: 4 22 1
|Time Limit:||0.116279 - 0.465116 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.