Given an integer array&nbsp;nums, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

&nbsp;
Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].


Example 2:

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 2000
	-106 &lt;= nums[i] &lt;= 106


class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        
        if not nums or len(nums) == 0:
            return 0
        
        def find_pos(sub, val):
            left, right = 0, len(sub) - 1
            while left < right:
                mid = (left + right) >> 1
                if sub[mid] >= val: 
                    right = mid
                else:
                    left = mid + 1
            return left 
        
    
        sub_list = []
        
        for val in nums:
            if len(sub_list) == 0 or val > sub_list[-1][-1][0]:
                # should append a new element at the end
                cur_count = sum([x[1] for x in sub_list[-1] if val > x[0]]) if len(sub_list) != 0 else 1
                sub_list.append([(val, cur_count)])
            else:
                # get the last number to turn it back to a LIS problem
                cur_sub = [array[-1][0] for array in sub_list]
                pos = find_pos(cur_sub, val)
                # if pos == 0, means it is smallest, no need to look the previous level and set it to be 1
                cur_count = sum([x[1] for x in sub_list[pos - 1] if val > x[0]]) if pos > 0 else 1
                sub_list[pos].append((val, cur_count))
      
        return sum([x[1] for x in sub_list[-1]])
class Solution {
    public int findNumberOfLIS(int[] nums) {
        int N = nums.length;
        int []dp =new int[N];
        int []count = new int[N];
        Arrays.fill(dp,1);Arrays.fill(count,1);
        int maxi = 1;
        for(int i=0;i<N;i++){
            for(int j=0;j<i;j++){
                if(nums[j] < nums[i] && dp[j]+1 > dp[i]){
                    dp[i] = dp[j]+1;
                    //inherit a new one
                    count[i]=count[j];
                    maxi = Math.max(dp[i],maxi);
                }else if(nums[j] < nums[i] && dp[j]+1 == dp[i]){
                    //got one as same len, increase count
                    count[i]+=count[j];
                }
            }
        }//for ends
        int maxlis=0;
        for(int i=0;i<N;i++){
            if(maxi == dp[i]){
                maxlis+=count[i];
            }
        }
        return maxlis;
    }
}
class Solution {
public:
	int findNumberOfLIS(vector<int>& nums) {
		int n = nums.size(), maxI=0, inc=0;
		vector<int> dp(n,1), count(n,1);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<i;j++){
				if(nums[i]>nums[j] && 1+dp[j] > dp[i])
				{
					dp[i] = 1+dp[j];
					count[i] = count[j];
				}
				else if(nums[i]>nums[j] && 1+dp[j] == dp[i])
					count[i] += count[j];
			}
			maxI = max(maxI, dp[i]);
		}
		for(int i=0;i<n;i++)
			if(maxI == dp[i])   inc += count[i];
		return inc;
	}
};
var findNumberOfLIS = function(nums) {
    const { length } = nums;
    const dpLength = Array(length).fill(1);
    const dpCount = Array(length).fill(1);

    for (let right = 0; right < length; right++) {
        for (let left = 0; left < right; left++) {
            if (nums[left] >= nums[right]) continue;
            if (dpLength[left] + 1 === dpLength[right]) {
                dpCount[right] += dpCount[left];
            } else if (dpLength[left] + 1 > dpLength[right]) {
                dpLength[right] = dpLength[left] + 1;
                dpCount[right] = dpCount[left];
            }
        }
    }

    const maxLength = Math.max(...dpLength);
    return dpLength.reduce((result, length, index) => {
        const count = dpCount[index];
        return result + (maxLength === length ? count : 0);
    }, 0);
};
Number of Longest Increasing Subsequence