Count divisible subsequences

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.

Expected approach

• Let dp[j] = number of good subsequences currently of length j, with dp[0] = 1.
• Process elements left to right. A value x can extend a subsequence to length j only if j divides x. For each x, iterate j over the divisors of x in decreasing order and do dp[j] += dp[j-1].
• Descending divisor order prevents reusing the same element twice in one pass.
• Answer is sum(dp[1..n]). Complexity ≈ O(n · d(max)), where d is the number of divisors.