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

• Подзадача 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