思路：乘法原理+哈希表

我们可以从1开始枚举$k$

$k=1$，其实就是数组中元素值为1的个数

$k=2$，根据乘法原理可知，就是数组中元素值为1的个数$\times$数组中元素值为2的个数

以此内推，因此使用一个哈希表统计数组中元素的个数，然后按照上述方式枚举$k$即可

题目内容

给定一个长度为$n$的数组，求出这个数组有多少个子序列是一个$k$排列。$k\in[1,n]$

子序列:对数组删除若干个元素所得到的数组

$k$排列:一个长度为$k$的数组并且里面$[1,k]$ 每个整数恰好出现一次，例如$1,3,2,4$ 是一个$4$排列

输入描述

第一行输入一个整数$n(1\leq n\leq 10^5)$

第二行输入一个整数$a(1\leq a_i \leq 10^9)$

输出描述

一行一个整数，表示有多少个子序列是一个$k$ 排列 , $k \in[1,n]$ 。

由于答案过大，请对$10^9+7$取模。

示例1

输入

5
1 2 1 3 4

输出

8

方案为:

$[1],[1],[1,2],[2,1],[1,2,3],[2,1,3],[1,2,3,4],[2,1,3,4]$