Square Sum of Distinct Elements in Subarrays

You are given a sequence of n positive integers: \(A_1, A_2, \cdots, A_n\). Define the function \(f(l,r)\) as the number of distinct integers in the subarray \(A_l, A_{l+1}, \cdots, A_r\), i.e. \(f(l,r)=\left|\{A_l, A_{l+1},\cdots, A_r\}\right|\). Your task is to compute

[ S=\sum_{l=1}^{n}\sum_{r=l}^{n} \left(f(l,r)\right)^2 \mod (10^9+7). ]

Please output the value of \(S\) modulo \(10^9+7\).

inputFormat

The first line contains an integer n representing the length of the sequence. The second line contains n positive integers \(A_1, A_2, \cdots, A_n\) separated by spaces.

outputFormat

Output a single integer: the sum \(S=\sum_{l=1}^{n}\sum_{r=l}^{n} (f(l,r))^2\) modulo \(10^9+7\).

sample

1
1

1