Divisor Chains

Hard

Call an array arr of length length a **chain** if: - every element is an integer from 1 to max_value; - every element is divisible by the one before it: arr[i] % arr[i - 1] == 0 for all 0 < i < length. How many different chains are there? The number can be huge, so return it modulo 10⁹ + 7.

Example 1

length=3, max_value=4 → 13

Eight chains start with 1: [1,1,1], [1,1,2], [1,1,3], [1,1,4], [1,2,2], [1,2,4], [1,3,3], [1,4,4]. Three start with 2: [2,2,2], [2,2,4], [2,4,4]. 3 and 4 each give one constant chain. That is 8 + 3 + 1 + 1 = 13.

Example 2

length=4, max_value=1 → 1

The only allowed value is 1, so the single chain is [1, 1, 1, 1].

Example 3

length=2, max_value=6 → 14

Constraints

2 ≤ length ≤ 10⁴
1 ≤ max_value ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Dynamic Programming Combinatorics Number Theory

Similar problems

Tasters and the Spoiled Cask Hard Radio Show Without Quick Repeats Hard Parcel Run Orders Hard A Fair Split of Colored Beads Hard Other Orders for the Same Search Tree Hard

Input

length=3, max_value=4

Expected

Run checks the first 3 tests in your browser. Submit checks all 83 tests on the server, hidden ones included.