<p>You are given a <strong>0-indexed </strong>integer array <code>nums</code>.</p>

<p>The <strong>distinct count</strong> of a subarray of <code>nums</code> is defined as:</p>

<ul>
	<li>Let <code>nums[i..j]</code> be a subarray of <code>nums</code> consisting of all the indices from <code>i</code> to <code>j</code> such that <code>0 &lt;= i &lt;= j &lt; nums.length</code>. Then the number of distinct values in <code>nums[i..j]</code> is called the distinct count of <code>nums[i..j]</code>.</li>
</ul>

<p>Return <em>the sum of the <strong>squares</strong> of <strong>distinct counts</strong> of all subarrays of </em><code>nums</code>.</p>

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

<p>A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong>Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1]
<strong>Output:</strong> 15
<strong>Explanation:</strong> Six possible subarrays are:
[1]: 1 distinct value
[2]: 1 distinct value
[1]: 1 distinct value
[1,2]: 2 distinct values
[2,1]: 2 distinct values
[1,2,1]: 2 distinct values
The sum of the squares of the distinct counts in all subarrays is equal to 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> + 2<sup>2</sup> = 15.
</pre>

<p><strong>Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Three possible subarrays are:
[2]: 1 distinct value
[2]: 1 distinct value
[2,2]: 1 distinct value
The sum of the squares of the distinct counts in all subarrays is equal to 1<sup>2</sup> + 1<sup>2</sup> + 1<sup>2</sup> = 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>5</sup></code></li>
</ul>

class Solution:
    def __init__(self):
        self.N = 100005
        self.hell = 1000000007
        self.a = [0] * (self.N)
        self.seg = [0] * (4 * self.N)
        self.segsq = [0] * (4 * self.N)
        self.lazy = [0] * (4 * self.N)

    # Build the segment tree.
    def build(self, node, start, end):
        if start == end:
            self.seg[node] = self.a[start]
            self.segsq[node] = (self.a[start] * self.a[start]) % self.hell
            return
        mid = (start + end) >> 1
        self.build(node << 1, start, mid)
        self.build(node << 1 | 1, mid + 1, end)
        self.seg[node] = (self.seg[node << 1] + self.seg[node << 1 | 1]) % self.hell
        self.segsq[node] = (self.segsq[node << 1] + self.segsq[node << 1 | 1]) % self.hell

    # Update the segment tree and handle lazy propagation.
    def update(self, node, start, end, l, r, val):
        if self.lazy[node] != 0:
            self.segsq[node] += ((end - start + 1) * (self.lazy[node] * self.lazy[node]) % self.hell) % self.hell + (2 * self.lazy[node] * self.seg[node]) % self.hell
            self.segsq[node] %= self.hell
            self.seg[node] += ((end - start + 1) * self.lazy[node]) % self.hell
            self.seg[node] %= self.hell
            if start != end:
                self.lazy[node << 1] += self.lazy[node]
                self.lazy[node << 1 | 1] += self.lazy[node]
            self.lazy[node] = 0
        if start > end or start > r or end < l:
            return
        if l <= start and end <= r:
            self.segsq[node] += ((end - start + 1) * (val * val) % self.hell) % self.hell + (2 * val * self.seg[node]) % self.hell
            self.segsq[node] %= self.hell
            self.seg[node] += ((end - start + 1) * val) % self.hell
            self.seg[node] %= self.hell
            if start != end:
                self.lazy[node << 1] += val
                self.lazy[node << 1 | 1] += val
            return
        mid = (start + end) >> 1
        self.update(node << 1, start, mid, l, r, val)
        self.update(node << 1 | 1, mid + 1, end, l, r, val)
        self.seg[node] = (self.seg[node << 1] + self.seg[node << 1 | 1]) % self.hell
        self.segsq[node] = (self.segsq[node << 1] + self.segsq[node << 1 | 1]) % self.hell

    # Main function to find the sum of counts.
    def sumCounts(self, nums):
        n = len(nums)
        for i in range(1, n + 1):
            self.a[i] = 0

        # Build the segment tree.
        self.build(1, 1, n)

        prev_seen_at = {}

        ans = 0

        for i in range(n - 1, -1, -1):
            if nums[i] not in prev_seen_at:
                self.update(1, 1, n, i + 1, n, 1)
            else:
                self.update(1, 1, n, i + 1, prev_seen_at[nums[i]] - 1, 1)

            prev_seen_at[nums[i]] = i + 1

            ans = (ans + self.segsq[1]) % self.hell

        return ans


8157