Сегодня день рождения Деву. Чтобы отпраздновать это событие, он купил n конфет на рынке неподалеку и пригласил f своих друзей. Сейчас Деву хочет поделить конфеты между друзьями. Деву — добрый парень, и день сегодня особенный, так что он не хочет, чтобы кто-то грустил. Поэтому очень важно, чтобы каждый друг получил хотя бы одну конфету.
Юноша хочет, чтобы день рождения прошел особенным образом, поэтому конфеты требуется разделить по особенному. Предположим, что он раздал n сладостей своим друзьям так, что i-му другу досталось ai конфет. Не должно существовать ни одного целого числа x (x > 1), которое делит все ai.
Найдите количество способов распределения сладостей между друзьями, удовлетворяющих описанным ограничениям. Обратите внимание, что порядок имеет значение, например, [1, 2] и [2, 1] — различные распределения конфет. Так как ответ может быть достаточно велик, пожалуйста, выведите его по модулю 1000000007 (109 + 7).
Чтобы задача была еще интереснее, вам дано q запросов. Каждый запрос содержит пару n, f. Для каждого запроса выведите необходимое количество способов по модулю 1000000007 (109 + 7).
Примечание
Для первого запроса: n = 6, f = 2. Возможные разделения: [1, 5] и [5, 1].
Для второго запроса: n = 7, f = 2. Возможные разделения: [1, 6] и [2, 5] и [3, 4] и [4, 3] и [5, 3] и [6, 1]. Таким образом, всего есть шесть возможных способов разделения.