Count The Number Of Ideal Arrays

Back to problems

Leetcode

Medium

Arrays

Dynamic Programming

Combinatorics

Math

Google

Count The Number Of Ideal Arrays

Count arrays of length $n$ whose values stay nondecreasing under divisibility from left to right.

Acceptance 0%

Start Practice

Problem Statement

You are given two integers n and maxValue.

Count how many arrays arr of length n satisfy all of the following:

1 <= arr[i] <= maxValue for every index i
arr[i] divides arr[i+1] for every 0 <= i < n - 1

Return the number of such arrays modulo $10^9 + 7$ .

An array is called ideal if each element divides the next one.

Input Format

Two integers n and maxValue.
The task is to count all length-n arrays with values in [1, maxValue] such that each element divides the next one.

Output Format

Return a single integer: the number of ideal arrays modulo $10^9 + 7$ .

Constraints

$1 \le n, maxValue \le 10^4$
Answer must be computed modulo $10^9 + 7$

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 2, maxValue = 5

Output

Explanation

The valid arrays are [1,1], [1,2], [1,3], [1,4], [1,5], [2,2], [2,4], [3,3], [4,4], and [5,5].

Example 2

Input

n = 3, maxValue = 2

Output

Explanation

The valid arrays are [1,1,1], [1,1,2], [1,2,2], and [2,2,2].

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress