Cho một mảng gồm \(n\) số nguyên, hãy đếm số dãy con mà mọi phần tử trong đó đều phân biệt.

Một dãy con là một dãy các phần tử của mảng theo thứ tự từ trái sang phải, có thể bỏ qua một số phần tử.

Input

Dòng đầu tiên chứa một số nguyên \(n\): kích thước của mảng.

Dòng thứ hai chứa \(n\) số nguyên \(x_1,x_2,\dots,x_n\): nội dung của mảng.

Output

In số dãy con có các phần tử phân biệt. Kết quả có thể lớn, vì vậy hãy in nó modulo \(10^9+7\).

Constraints

• \(1 \le n \le 2 \cdot 10^5\)

• \(1 \le x_i \le 10^9\)

Example

4
1 2 1 3

11

Giải thích: Các dãy con là \([1]\) (hai lần), \([2]\), \([3]\), \([1,2]\), \([1,3]\) (hai lần), \([2,1]\), \([2,3]\), \([1,2,3]\) và \([2,1,3]\).