← 返回题目列表

Codeforces · 439/E

E. Devu 和生日庆典

中文机器翻译题面 查看原题

今天是 Devu 的生日。为了庆祝这个日子,他从附近的市场买了n块糖果。他邀请了他的f个朋友。他想把糖果分给他们。由于他是一个好人,而且场合又好,他不想让任何朋友难过,所以他会保证给每个朋友至少一份糖果。

他想以独特的方式庆祝这一节日,因此他希望确保糖果分发的以下条件。假设他已经向他的朋友分发了 n 颗糖果,使得第 i 个朋友得到了 a 颗糖果。他想确保不应该有任何正整数 x > 1 来整除每个 ai。

请找出他可以按要求的方式向朋友分发糖果的方式数。请注意,分布的顺序很重要,例如 [1, 2] 和 [2, 1] 是不同的分布。由于答案可能非常大,因此输出答案模 1000000007 (109 + 7)。

为了使问题变得更有趣,我们向您提供了 q 个查询。每个查询包含一个 n, f 对。对于每个查询,请输出所需的路数模 1000000007 (109 + 7)。

输入

第一行包含一个整数 q ,表示查询数量 (1 ≤ q ≤ 105)。接下来的 q 行中的每一行都包含两个空格分隔的整数 n, f (1 ≤ f ≤ n ≤ 105)。

输出

对于每个查询,在与每个查询的答案相对应的行中输出一个整数。

示例

输入 #1

5
6 2
7 2
6 3
6 4
7 4

输出 #1

2
6
9
10
20

注意

对于第一个查询:n = 6,f = 2。可能的分区为 [1, 5] 和 [5, 1]。

对于第二个查询:n = 7,f = 2。可能的分区为 [1, 6] 和 [2, 5] 和 [3, 4] 和 [4, 3] 以及 [5, 3] 和 [6, 1]。所以总共有6种可能的分区方式。