Count divisible subsequences

Problem Given an array of n positive integers, count the number of non-empty subsequences b_1, b_2, …, b_k (kept in original order) that are "good": a subsequence is good if every element b_i is divisible by its position i within the subsequence. Return the count modulo 10^9 + 7.

Input / Output

• Input: integer n and the array a of n positive integers.
• Output: number of good subsequences, modulo 10^9 + 7.

Constraints

• 1 <= n <= 10^5
• 1 <= a[i] <= 10^6

Example

• a = [1, 2, 3, 4, 5, 6] → 39.