C. Multiplicitytime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an integer array a_1, a_2, \ldots, a_n.The array b is called to be a subsequence of a if it is possible to remove some elements from a to get b.Array b_1, b_2, \ldots, b_k is called to be good if it is not empty and for every i (1 \le i \le k) b_i is divisible by i.Find the number of good subsequences in a modulo 10^9 + 7. Two subsequences are considered different if index sets of numbers included in them are different. That is, the values ​of the elements ​do not matter in the comparison of subsequences. In particular, the array a has exactly 2^n - 1 different subsequences (excluding an empty subsequence).InputThe first line contains an integer n (1 \le n \le 100\,000) — the length of the array a.The next line contains integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^6).OutputPrint exactly one integer — the number of good subsequences taken modulo 10^9 + 7.ExamplesInput21 2Output3Input52 2 1 22 14Output13NoteIn the first example, all three non-empty possible subsequences are good: \{1\}, \{1, 2\}, \{2\}In the second example, the possible good subsequences are: \{2\}, \{2, 2\}, \{2, 22\}, \{2, 14\}, \{2\}, \{2, 22\}, \{2, 14\}, \{1\}, \{1, 22\}, \{1, 14\}, \{22\}, \{22, 14\}, \{14\}.Note, that some subsequences are listed more than once, since they occur in the original array multiple times.
Input21 2
Output3
['data structures', 'dp', 'implementation', 'math', 'number theory', '*1700']