Сегодня день рождения Деву. Чтобы отпраздновать это событие, он купил n конфет на рынке неподалеку и пригласил f своих друзей. Сейчас Деву хочет поделить конфеты между друзьями. Деву — добрый парень, и день сегодня особенный, так что он не хочет, чтобы кто-то грустил. Поэтому очень важно, чтобы каждый друг получил хотя бы одну конфету.

Юноша хочет, чтобы день рождения прошел особенным образом, поэтому конфеты требуется разделить по особенному. Предположим, что он раздал n сладостей своим друзьям так, что i-му другу досталось a_i конфет. Не должно существовать ни одного целого числа x (x > 1), которое делит все a_i.

Найдите количество способов распределения сладостей между друзьями, удовлетворяющих описанным ограничениям. Обратите внимание, что порядок имеет значение, например, [1, 2] и [2, 1] — различные распределения конфет. Так как ответ может быть достаточно велик, пожалуйста, выведите его по модулю 1000000007 (10⁹ + 7).

Чтобы задача была еще интереснее, вам дано q запросов. Каждый запрос содержит пару n, f. Для каждого запроса выведите необходимое количество способов по модулю 1000000007 (10⁹ + 7).