Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là đếm số cách chia mảng thành các đoạn liên tiếp sao cho mọi đoạn đều chỉ gồm các giá trị phân biệ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 tiếp theo chứa \(n\) số nguyên \(x_1, x_2,\dots, x_n\): các phần tử của mảng.

Output

In ra một số nguyên: đáp án của bài toán lấy 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

6

Explanation

Có sáu cách chia hợp lệ:

• \([1], [2], [1], [3]\)

• \([1], [2], [1, 3]\)

• \([1], [2, 1], [3]\)

• \([1], [2, 1, 3]\)

• \([1, 2], [1], [3]\)

• \([1, 2], [1, 3]\)