SEGMENT MAXIMA

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.
Input
 The first line consists of the number of testcases T.
 The next T lines each contain two integers: M and N.
Output
For each testcase, output the answer on a single line.
Constraints
Example
Input: 3 2 2 3 3 1 5 Output: 4 22 1
Author:  karthikv1392 
Tags  karthikv1392 
Date Added:  1032013 
Time Limit:  0.116279  0.465116 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 
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. 