题目描述

给定一个长为\(n\)的正整数序列，求它共有多少个互不相同的非空子序列。由于结果可能很大，你只需要输出将其除以\(10^5 + 3\)之后的余数。
“子序列”指的是从原序列中选取若干个数（位置可以不连续），保持相对位置不变，而得到的新序列。

格式

输入格式

第一行是一个正整数\(n\)；
第二行是\(n\)个正整数，表示原序列。

输出格式

一个正整数，互不相同的非空子序列总数除以\(10^5 + 3\)之后的余数。

样例

输入

4
1 2 3 2

输出

13

数据规模及限制

时间限制1s，空间限制64MB
共10组测试数据。所有数据均保证序列中的数\(\le 10^5\)。
测试点#1 ~ #2：\(n \le 15\)
测试点#3 ~ #4：\(n \le 150\)
测试点#5 ~ #6：\(n \le 1500\)
测试点#7 ~ #10：\(n \le 1.5 \times 10^5\)

来源

2017.7 太原五中高一集训
From: FZU Online Judge