# Beautiful Array

Hard
0/120
Average time to solve is 50m
Contributed by

## Problem statement

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.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= Q <= 500
1 <= N <= M <= 5 * 10 ^ 3

Time Limit: 1 sec.
``````
##### Sample Input 1:
``````2
3 2
4 3
``````
##### Sample Output 1:
``````4
9
``````
##### Explanation of Sample Input 1:
``````In the query case, M = 3 and N = 2
array : [ 1, 1, 2 ] [ 1, 2, 1 ] [ 1, 2, 2 ] [ 2, 1, 2 ] are beautiful. So the answer is 4.

In the second query,.M = 4, N = 3
array  [1 1 2 3] [1 2 1 3] [1 2 2 3] [1 2 3 1] [1 2 3 2] [1 2 3 3] [1 3 2 3] [2 1 2 3] [3 1 2 3] are beautiful. So the answer is 9.
``````
##### Sample Input 2:
``````1
4 4
``````
##### Sample Output 2:
``````1
``````
##### Explanation of Sample Output 2:
``````In the first query, only [1 2 3 4] is a beautiful array.
``````
Console