414B.md (1650B)
1 Source: https://codeforces.com/problemset/problem/414/B 2 3 B. Mashmokh and ACM 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Mashmokh's boss, Bimokh, didn't like Mashmokh. So he fired him. Mashmokh decided to go to university and participate in ACM instead of finding a new job. He wants to become a member of Bamokh's team. In order to join he was given some programming tasks and one week to solve them. Mashmokh is not a very experienced programmer. Actually he is not a programmer at all. So he wasn't able to solve them. That's why he asked you to help him with these tasks. One of these tasks is the following. 22 23 A sequence of *l* integers *b*1, *b*2, ..., *b**l* (1 ≤ *b*1 ≤ *b*2 ≤ ... ≤ *b**l* ≤ *n*) is called good if each number divides (without a remainder) by the next number in the sequence. More formally  for all *i* (1 ≤ *i* ≤ *l* - 1). 24 25 Given *n* and *k* find the number of good sequences of length *k*. As the answer can be rather large print it modulo 1000000007 (109 + 7). 26 27 Input 28 29 The first line of input contains two space-separated integers *n*, *k* (1 ≤ *n*, *k* ≤ 2000). 30 31 Output 32 33 Output a single integer — the number of good sequences of length *k* modulo 1000000007 (109 + 7). 34 35 Examples 36 37 Input 38 39 ``` 40 3 2 41 ``` 42 43 Output 44 45 ``` 46 5 47 ``` 48 49 Input 50 51 ``` 52 6 4 53 ``` 54 55 Output 56 57 ``` 58 39 59 ``` 60 61 Input 62 63 ``` 64 2 1 65 ``` 66 67 Output 68 69 ``` 70 2 71 ``` 72 73 Note 74 75 In the first sample the good sequences are: [1, 1], [2, 2], [3, 3], [1, 2], [1, 3].