407915: GYM102940 H Factory Tasks

The robot overlord has a bit of a dilemma on his hands. The army has constructed a huge factory stocked with worker robots in order to make the next generation army. There are $$$n$$$ types of robots that the army is trying to build, each type having a unique ID which is an integer between $$$1$$$ and $$$n$$$ (inclusive of $$$1$$$ and $$$n$$$).

Now, to meet the army's goal of world domination, they must construct $$$k$$$ robots every day (the type of each robot doesn't matter, just need $$$k$$$ total every day). However, his current batch of workers tends to be a little temperamental. They have threatened to go on strike unless their demands for the new robots were met. The overlord would usually just incinerate the obstinate robots and use the scrap parts to create a new workforce but due to the time crunch, the overlord decides to humor the workers.

The worker's demand is simple enough: they want each of the $$$k$$$ robots made that day to follow the rule that if the $$$i$$$th robot made is of type $$$a$$$ ($$$1 \leq a \leq n$$$) then the $$$i + 1$$$th robot made must be of type $$$b$$$ where $$$a \mid b$$$. This must hold for all $$$i$$$ where $$$1 \leq i \leq k - 1$$$ which means that if the sequence of robots made is $$$r_1, r_2, \dots, r_n$$$ then $$$r_i \mid r_{i+1}$$$ for all $$$i$$$ ($$$1 \leq i \leq n - 1$$$).

Given $$$n$$$ and $$$k$$$, help the overlord find out the number of distinct robot sequences that satisfy the above demand that can be made. Since this number can be quite large, the overlord will suffice with the number modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.

The only line of input will contain two space-separated integers $$$n$$$ and $$$k$$$ where $$$1 \leq n, k \leq 2000$$$.

Output a single integer representing the number of distinct robot sequences that satisfy the workers' demand modulo $$$1000000007$$$ $$$(10^9 + 7)$$$.

4 2

8

6 5

56

In the first sample, the sequences are $$$[1, 1], [2, 2], [3,3], [4,4], [1,2], [1, 3], [1,4], [2,4]$$$.