题目描述

给定一个数列 $a_1,a_2,\cdots,a_n$，请统计有多少个不相等的最长严格上升子序列。所谓两个序列不相等，就是这两个序列至少有一个对应的数字不相等。

例如对于 $1,2,3,1,2,3$，最长严格上升子序列是 $1,2,3$，尽管有多个不同的 $1$，但它们都是相等的。

由于答案可能很大，输出答案模 $1,000,000,007$ 的余数。

输入格式

第一行：单个整数 $n$； 第二行：$n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

单个整数：表示不相等的最长严格上升子序列的数量模 $1,000,000,007$ 的余数。

6
1 2 3 1 2 3

1

6
2 1 4 3 6 5

8

样例解释 2

第一项可以选1或2，第二项可以选3或4，第三项可以选5或6

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 100$；
• 对于 $60\%$ 的数据，$1\leq n\leq 2000$；
• 对于 $100\%$ 的数据，$1\leq n\leq 100,000$，
• $1\leq a_i\leq n$。