整除性

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

给定整数数组 $a_1,a_2,\ldots,a_n$。

若非空数组 $b_1,b_2,\ldots,b_k$ 是 $a$ 的子序列，并且对每个 $1\le i\le k$ 都有 $i\mid b_i$，则称它是一个好子序列。

求 $a$ 的好子序列个数，答案对 $10^9+7$ 取模。两个子序列只要选择的下标集合不同，就视为不同。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出好子序列的个数对 $10^9+7$ 取模后的结果。

样例输入 1

2
1 2

样例输出 1

3

样例输入 2

5
2 2 1 22 14

样例输出 2

13

数据范围

对于全部数据，$1\le n\le 100000$，$1\le a_i\le 10^6$。