题目描述

从序列 $\{a_1,\ a_2,\ ..\ ,\ a_n\}$ 中选出非空子序列 $\{b_1,\ b_2,\ ..\ ,\ b_k\}$，一个子序列合法需要满足 $\forall\ i \in [1,\ k],\ i\ |\ b_i$。求有多少互不相等的合法子序列，答案对 $10^9 + 7$ 取模。

序列 $\{1,\ 1\}$ 有 $2$ 种选法得到子序列 $\{1\}$，但 $1$ 的来源不同，认为这两个子序列不相等。

输入格式

第一行包含一个整数 $n$ ( $1 \le n \le 100\,000$ ) - 数组的长度 $a$ 。

下一行包含整数 $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^6$ )。

输出格式

打印一个整数--取模为 $10^9 + 7$ 的符合要求的子序列的个数 .

样例 #1

样例输入 #1

2
1 2

样例输出 #1

3

样例 #2

样例输入 #2

5
2 2 1 22 14

样例输出 #2

13

提示

在第一个例子中，所有三个非空的可能子序列都是好的：$\{1\}$ , $\{1, 2\}$ , $\{2\}$

在第二个例子中，可能的好子序列是 $\{2\}$ , $\{2, 2\}$ , $\{2, 22\}$ , $\{2, 14\}$ , $\{2\}$ , $\{2, 22\}$ , $\{2, 14\}$ , $\{1\}$ , $\{1, 22\}$ , $\{1, 14\}$ , $\{22\}$ , $\{22, 14\}$ , $\{14\}$ .

请注意，有些子序列被列出了不止一次，因为它们在原始数组中出现了多次。