Partitioning into Good Arrays

Given an array of positive integers, we call an element heavy if it appears more than once in the array and light if it appears exactly once. A good array is defined as one in which the elements, when classified as light or heavy (based on their frequency within that subarray), appear in an alternating pattern. In other words, for a subarray b_1...k, let its classification be defined by \[ \text{cls}(b_i)=\begin{cases} L & \text{if the frequency of } b_i \text{ in the subarray is } 1,\\ H & \text{if the frequency is greater than } 1, \end{cases} \] then the subarray is good if for every 2 \le i \le k, \text{cls}(b_i) \neq \text{cls}(b_{i-1}). (Note that any subarray of length 1 is trivially good.)

You are given an array \(a_{1},a_{2},\ldots,a_{N}\). You need to partition the array into one or more contiguous subarrays such that each subarray is a good array. Compute the number of ways to partition the given array. Since the answer might be large, output it modulo \(1000003\).

inputFormat

The input consists of two lines.

• The first line contains an integer \(N\) (the number of elements in the array).
• The second line contains \(N\) positive integers \(a_1,a_2,\ldots,a_N\) separated by spaces.

outputFormat

Output a single integer representing the number of ways to partition the array into contiguous subarrays such that each subarray is a good array. The answer should be given modulo \(1000003\).

sample

1
1

1