<p>You are given a <strong>0-indexed</strong> array <code>nums</code> consisting of <strong>positive</strong> integers.</p>

<p>A partition of an array into one or more <strong>contiguous</strong> subarrays is called <strong>good</strong> if no two subarrays contain the same number.</p>

<p>Return <em>the <strong>total number</strong> of good partitions of </em><code>nums</code>.</p>

<p>Since the answer may be large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4]
<strong>Output:</strong> 8
<strong>Explanation:</strong> The 8 possible good partitions are: ([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]), and ([1,2,3,4]).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1,1]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only possible good partition is: ([1,1,1,1]).
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The 2 possible good partitions are: ([1,2,1], [3]) and ([1,2,1,3]).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def numberOfGoodPartitions(self, nums: List[int]) -> int:
        cnt = defaultdict(list)
        n = len(nums)

        def get_ans(ndistinct):
            M = 1_000_000_007
            ans = 1
            for i in range(ndistinct):
                ans = (ans * 2) % M
            return ans

        for i in range(n):
            cnt[nums[i]].append(i)

        intervals = []
        for num in cnt:
            if len(cnt[num]) > 1:
                intervals.append([cnt[num][0], cnt[num][-1]])
        if not intervals:
            return get_ans(n - 1)

        intervals.sort()
        combined = []
        start, end = intervals[0]
        for i in range(1, len(intervals)):
            if intervals[i][0] < end:
                end = max(end, intervals[i][1])
            else:
                combined.append([start, end])
                start, end = intervals[i]
        combined.append([start, end])

        total_interval_len = 0
        for (start, end) in combined:
            total_interval_len += end - start + 1

        ndistinct = (n - total_interval_len + len(combined) - 1)
        return get_ans(ndistinct)
        

        
45200