Problem Statement

Given an integer array arr of length n, compute how many strictly increasing subsequences of length 3 can be formed, and return the result modulo (10 9 + 7). Note: A subsequence is obtained by deleting zero or more elements from the array without changing the order of the remaining elements. A subsequence of length 3 is strictly increasing if it consists of indices i < j < k such that: arr[i] < arr[j] < arr[k]. Return the total count of such subsequences modulo (10 9 + 7). Example 1 Input: n = 5, arr = [1, 2, 3, 4, 1] Output: 4 Some subsequences of length 3 (0-based indexing) Index of 1st Element Index of 2nd Element Index of 3rd Element Subsequence Is Strictly Increasing? 0 1 2 [1, 2, 3] Yes 0 2 4 [1, 3, 1] No 0 1 3 [1, 2, 4] Yes 0 2 3 [1, 3, 4] Yes 1 2 4 [2, 3, 1] No 1 2 3 [ 2, 3 , 4] Yes All strictly increasing subsequences of length three are: [1, 2, 3], [1, 2, 4 ], [1, 3, 4], and [2, 3, 4]. The answer is 4 modulo (10 9 +7), which is 4. Example 2 Input: n = 4, arr = [3,