This page is still under construction.

Parts of this page are still being built. What you see may change.

Chains of Multiples

Time limit2sMemory limit512 MB

Summary
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 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. (1≤N,L≤20001 \le N, L \le 2000)

Output

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

Examples5

  1. Example 1

    Input
    3 2
    
    Expected output
    5
    
  2. Example 2

    Input
    6 4
    
    Expected output
    39
    
  3. Example 3

    Input
    1 1
    
    Expected output
    1
    
  4. Example 4

    Input
    7 1
    
    Expected output
    7
    
  5. Example 5

    Input
    10 3
    
    Expected output
    53