Chains of Multiples
Time limit2sMemory limit512 MB
Count non-decreasing length-L sequences of values from 1 to N where in every pair one value divides the other, modulo 1e9+7.
- Level
Medium7 of 10
- Topics
- Combinatorics, Dynamic programming, Math, Number theory
- Solved
- No attempts yet
Problem
Minho wants to build a sequence of length using integers from 1 to . With no restriction the count would be .
Minho finds such sequences dull, so he builds only the sequences that obey both rules below.
- The sequence is non-decreasing. An earlier term is never greater than a later term.
- For any two positions in the sequence, one of the two values is a multiple of the other.
Count the sequences that obey both rules. The count can grow very large, so report it modulo .
Input
The first line contains and , separated by a single space. ()
Output
Print the number of sequences that obey both rules, modulo , on one line.