Chains of Multiples

Count non-decreasing length-L sequences of values from 1 to N where in every pair one value divides the other, modulo 1e9+7.

Medium7CombinatoricsDynamic programmingMathNumber theoryNo attempts yetTime limit2sMemory limit512 MB

Problem

Minho wants to build a sequence of length LL using integers from 1 to NN. With no restriction the count would be NLN^L.

Minho finds such sequences dull, so he builds only the sequences that obey both rules below.

  1. The sequence is non-decreasing. An earlier term is never greater than a later term.
  2. 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 109+710^9 + 7.

Input

The first line contains NN and LL, separated by a single space. (1N,L20001 \le N, L \le 2000)

Output

Print the number of sequences that obey both rules, modulo 109+710^9 + 7, on one line.