# Beautiful Array

#### You are given two integers ‘M’ and ‘N’. Your task is to find the number of a unique beautiful array of length ‘M’.

#### The array of length ‘M’ is said to be beautiful if -

```
The array consists of elements from 1 to ‘N’.
The array contains at least one ‘N’ length strictly increasing subsequence.
```

#### Note:

```
A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of the array [1, 2, 3] are [1], [2], [3], [1, 2], [1, 3], [2, 3] and [1, 2, 3] where [2, 1], [3,2, 1] are not subsequence of array [1, 2, 3]
The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in strictly increasing order.
```

#### For example:

```
For M = 3 and N = 2
array : [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 2, 1, 2 ] are beautiful.
array: [ 1, 1, 1 ] [ 2, 1, 1 ] [ 2, 2, 1 ] [ 2, 2, 2 ] are not beautiful.
```

##### Input Format:

```
The first line of input contains an integer ‘Q’, denoting the number of queries. Then each query follows.
The first line and the only of each query contains a pair of integers ‘M’ and ‘N’ , where ‘M’ is the length of the array and ‘N’ is the range of elements.
```

##### Output Format:

```
For each query, print a single line containing ‘X’, denoting the number of beautiful arrays of length ‘M’.
As this number can be quite large, print your answer modulo 10 ^ 9 + 7.
The output of each test case will be printed on a separate line.
```

##### Note:

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

##### Constraints:

```
1 <= Q <= 500
1 <= N <= M <= 5 * 10 ^ 3
Time Limit: 1 sec.
```

Since we have to use elements from [1, N] and make the longest increasing subsequence, we must use all elements of [1, N] and for ‘N’ position out of ‘M’, place them in increasing order.

Like for ‘N’ = 3, ‘M’ = 5, some possible placements of ‘N’ elements are

Array[ ] : _ 1 _ 2 3

position : 1 2 3 4 5

Array[ ] : _ 1 2 _ 3

position : 1 2 3 4 5

So, we have ( M C N) ways to select the ‘N’ position such that the selected position makes an increasing subsequence of length ‘N’. For example (N = 3 and M = 5 ) we have 10 ways (5 C 3) to select 3 positions out of 5, such that the selected position makes an increasing subsequence of length 3. Let the selected position be {p1, p2, p3 ...pn}.

After doing so our task is to fill the gaps.

Now to avoid repetition of the array, we don’t place 1 before p1, don’t place 2 before p2 and after p1, don’t place 3 before p3 and after p2, and so on.

We can say in the set {p1, p2, p3 ...pn} p1, p2, p3….pn are the first positions of 1, 2, 3..N respectively.

If we carefully observe, there are (‘N’ - 1) ways to fill not filled positions before ‘pn’ (the first position of N) and ‘N’ ways to fill each not filled position after ‘pn’.

Let x = ‘pn’ - N, be the not filled position to the left of ‘pn’ and y = M - ‘pn’, be the not filled position to the right of ‘pn’.

So, loop for each ‘pn’ position from N to M, and find the number of ways for each position of ‘pn’ and add to our answer.

Total number of ways for each pn = ( (pn - 1) **C** (N -1) )( pow (x, N-1) ) * ( pow(y, N) )), where n C r denotes the total combination of ‘r’ elements among ‘n’.

We have done (('pn' - 1) C (N - 1)) not (pn C N) because we have to fix ‘N’-th element at ‘pn’ and arrange only ‘N’ - 1 element in ‘pn’ -1 positions such that it maintains the constraints of the question( increasing subsequence).

Note:

- Take care of modulo operation where mod = 10^9 +7.
- Since this question has a different number of queries, So pre-calculate factorial, and multiplicative modular inverse.

**Algorithm :**

- Take ‘factorial’ and ‘inverse’ array that stores the factorial and modular multiplicative inverse.
- Do precalculation by calling the function ‘preCalculate( factorial, inverse)’.
- Take the vector ‘res’, which stores the answer of each query.
- Do the following for each query from 0 to ‘N’.
- Let ‘n’ = arr[i][0] and ‘m’ = arr[i][1], be pairs of numbers given.
- Let ‘ans’ be the variable to store the answer ( number of the beautiful arrays)
- Let ‘n1powx’ be variable initialized to 1.
- Let ‘npowx’ be the variable initialized to power( ‘n’, ‘m’ -’n’)
- Let ‘inverseN’ be the modular multiplicative inverse of ‘n’ under mod.
- Take a counter ‘i’ and run a loop from ‘n’ to ‘m’
- Calculate iCm by calling the function nCk(i-1, n-1) and store it in variable nck.
- Update ‘ans’ i.e ans = ( ( (nck * npowx) % mod ) * n1powx ) % mod
- Update ‘n1powx’ as n1powx = ( n1powx * (n -1)) % mod
- Update ‘npowx’ as npowx = (npowx * inverseN) % mod

- Push (ans%mod) in ‘res’ vector

- return ‘res’

#### Description of preCalculate ( factorial, inverse ) function:

- Initialize, factorial[0] = 1
- Initialize, inverse[0] = inverse[1] = 1
- Run a loop from 1 to 5 * 10 ^ 3.
- Store factorial[i] = (factorial [i - 1] * i) % 'mod'
- Store inverse[i] = multiverse( factorial [i], mod.

#### Description of modInverse (num, mod) function:

This function returns the modular multiplicative inverse of num under modulo ‘mod’

- Let ‘x’ and ‘y’ be the variable that satisfies the extended euclidean equation on ‘num’ and ‘mod’
- Just find the value of ‘x’ and ‘y’ using an extended Euclidean algorithm.
- If ’x’ if negative then add ‘mod’ to it as ‘x’ = ‘x’ + ‘mod’
- Return ‘x’

#### Description of nCk( ‘n’, ‘k’) function:

- Return (((factorial [ n ] * inverse [k] ) % mod ) * inverse[n-k] ) % mod)