In an array containing only positive integers, we say an integer is heavy if it appears more than once in the array, and light otherwise.

An array is good if the integers in the array alternate between light and heavy.

Given an array ~a_1, \ldots, a_N~, count the number of ways to partition it into some number of contiguous subarrays such that each subarray, when considered as an array on its own, is good. As the answer may be large, output it modulo ~1\,000\,003~.

Input Specification

The first line of input contains a single integer, ~N~.

The next line contains ~N~ integers ~a_1, \ldots, a_N~ ~(1 \le a_i \le N)~.

Marks Awarded	Bounds on ~N~	Additional Constraints
3 marks	~2 \le N \le 50\,000~	For each ~i~, ~a_i \le 26~.
4 marks	~2 \le N \le 5\,000~	No additional constraints.
5 marks	~2 \le N \le 500\,000~	If ~i~ is odd, then ~a_i = 1~.
6 marks	~2 \le N \le 500\,000~	Any number appears at most twice in the array.
7 marks	~2 \le N \le 500\,000~	No additional constraints.

Output Specification

The number of ways to partition the array into good contiguous subarrays, modulo ~1\,000\,003~.

Sample Input 1

5
1 2 3 2 3

Sample Output 1

4

Explanation for Sample 1

There are four valid partitions of ~[1, 2, 3, 2, 3]~:

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

Sample Input 2

5
1 2 1 3 1

Sample Output 2

6