Count the Number of Ideal Arrays
You are given two integers n and maxValue, which are used to describe an ideal array.
A 0-indexed integer array arr of length n is considered ideal if the following conditions hold:
- Every
arr[i]is a value from1tomaxValue, for0 <= i < n. - Every
arr[i]is divisible byarr[i - 1], for0 < i < n.
Return the number of distinct ideal arrays of length n. Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input
n = 2, maxValue = 5Output
10There are 5 arrays starting with 1, 2 arrays starting with 2, and 1 array each starting with 3, 4, and 5, for a total of 10 distinct ideal arrays.
Example 2
Input
n = 5, maxValue = 3Output
11There are 9 arrays starting with 1, 1 array starting with 2, and 1 array starting with 3, for a total of 11 distinct ideal arrays.
Constraints
- 2 <= n <= 10^4
- 1 <= maxValue <= 10^4