Problem Description
The cost of an array arr is the sum of all the values in the left subtree of the Binary Search Tree formed by inserting the elements of arr in the order they appear in it.
For example, Binary Search Tree for arr = [5, 2, 9, 1] will look like-
5
/ <br> 2 9
/
1
So, the cost will be 2 + 1 = 3.
Find the sum of the cost of all the permutations of length A. Since answer can be large, return it modulo 109 + 7.
A permutation of length N is an array consisting of N distinct integers from 1 to N in arbitrary order.
1 <= N <= 105
Input 1:
2
Input 2:
3
Output 1:
1
Output 2:
8
Explanation 1:
There are 2 permutations- 1. [1, 2] BST 1 \ 2 Cost = 0
- [2, 1] BST 2 / 1 Cost = 1
Explanation 2:
There are 6 permutations-
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.