A hiker's altimeter records the heights of the waypoints of a trail in heights. A climb is a choice of waypoints, kept in trail order, whose heights are strictly increasing. Among all climbs of the greatest possible length, return how many different ones there are (two climbs differ if they use a different set of waypoint positions), modulo 10**9 + 7. An empty trail has 0 climbs.
Examples
Input: heights = [1, 4, 2, 5, 3, 6]
Output: 3
Explanation: the longest climbs have 4 waypoints: 1-4-5-6, 1-2-5-6 and 1-2-3-6.
Input: heights = [5, 5, 5]
Output: 3
Explanation: no climb is longer than one waypoint, and there are three single waypoints.
Constraints
0 <= len(heights) <= 3000-10**9 <= heights[i] <= 10**9- Target complexity: O(n^2) time; the number of increasing subsequences can be exponential.
Goals
- Store a (length, count) pair for the best increasing subsequence ending at each index
- Merge equally long predecessors by adding their counts
- Sum the counts of every index that reaches the overall best length