题目背景

翻译自 CCO 的 2024P5题。

题目描述

在一个只包含正整数的数组中，如果一个数字在数组里多次出现，我们就称它为“重的”，否则为“轻的”。定义好的数组是指数组里的数字交替出现“轻的”元素和“重的”元素。给你一个数组 $a_{1}, \ldots, a_{N}$，请计算把它划分成若干个连续的子数组，使得每个子数组本身也都是好数组的方案数。由于答案可能很大，请将最终结果对 $1000003$ 取模输出。

输入格式

第一行包含一个正整数 $N$。

第二行包含 $N$ 个正整数 $a_{1}, \ldots, a_{N}\ (1 \leq a_{i} \leq N)$，表示数组中的元素。

输出格式

输出一行一个整数，表示方案数对 $1000003$ 取模后的结果。

5
1 2 3 2 3

4

5
1 2 1 3 1

6

提示

对于 $100\%$ 的数据，$2 \leq N \leq 5\times 10^5$。