You are given an array of n integers. Your task is to count the number of ways to split the array into continuous segments such that all segments consists of distinct values.

Input

The first line has an integers n: the size of the array.

The next line has n integers x_1, x_2,\dots, x_n: the contents of the array.

Output

Print one integer: the answer to the problem modulo 10^9 + 7.

Constraints

• 1 \le n \le 2 \cdot 10^5
• 1 \le x_i \le 10^9

Example

Input:

4
1 2 1 3

Output:

6

Explanation: There are six valid splits:

• [1], [2], [1], [3]
• [1], [2], [1, 3]
• [1], [2, 1], [3]
• [1], [2, 1, 3]
• [1, 2], [1], [3]
• [1, 2], [1, 3]