I. НОД и подмножества
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кроша есть множество из $$$n$$$ натуральных чисел от $$$1$$$ до $$$n$$$. Он называет подмножество этого множества из $$$k$$$ элементов красивым, если наибольший общий делитель всех элементов подмножества равен $$$1$$$. Помогите ему посчитать количество красивых подмножеств из $$$k$$$ элементов. Так как ответ может быть большим, выведите его остаток от деления на $$$10^9+7$$$.

Входные данные

Вам даны числа $$$2 \le n \le 1000000$$$ и $$$2 \le k \le n$$$.

Выходные данные
Система оценки
  • Подзадача 1 (10 баллов) $$$k = 2, n \le 100$$$
  • Подзадача 2 (14 баллов) $$$k = 2, n \le 10^5$$$, необходимые подзадачи – 1
  • Подзадача 3 (14 баллов) $$$n \le 20$$$
  • Подзадача 4 (18 баллов) $$$n \le 500$$$, необходимые подзадачи – 1, 3
  • Подзадача 5 (18 баллов) $$$n \le 2000$$$, необходимые подзадачи – 1, 3, 4
  • Подзадача 6 (26 баллов) без дополнительных ограничений, необходимые подзадачи – 1, 2, 3, 4, 5
Пример
Входные данные
10 2
Выходные данные
31