← 返回题目列表

Codeforces · 711/E

E. ZS 和生日悖论

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

ZS the Coder 最近发现了一个有趣的概念,称为生日悖论。它指出,随机抽取 23 个人,其中两人生日相同的可能性约为 50%。编码员 ZS 发现这非常有趣,并决定与乌代兰的居民进行测试。

在乌代兰,一年有 2n 天。编码员 ZS 想要采访来自 Udayland 的 k 个人,他们每个人的生日都在 2n 天中的某一天(每一天的概率相等)。他感兴趣的是其中至少两个人生日在同一天的概率。

ZS 编码员知道答案可以写成不可约分数 $$\frac{\overline{A}}{\overline{B}}$$。他想要找到A和B的值(他不喜欢处理浮点数)。你能帮助他吗?

输入

输入的第一行也是唯一一行包含两个整数 n 和 k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 1018),这意味着一年有 2n 天,并且编码员 ZS 想要采访 k 个人。

输出

如果一年中至少有 2 k 个人拥有相同生日的概率等于 $$\frac{\overline{A}}{\overline{B}}$$ (A ≥ 0, B ≥ 1, $$\gcd(A,B)=1$$),则将 A 和 B 打印在一行中。

由于这些数字可能太大,因此将它们打印为模 106 + 3。请注意,在取模 106 + 3 的余数之前,A 和 B 必须互质。

示例

输入 #1

3 2

输出 #1

1 8

输入 #2

1 3

输出 #2

1 1

输入 #3

4 3

输出 #3

23 128

注意

在第一个示例案例中,乌代兰有 23 = 8 天。 2 个人中有 2 个人生日相同的概率显然是 $${ \frac { 1 } { 8 } }$$,所以 A = 1,B = 8。

在第二个样本案例中,Udayland 只有 21 = 2 天,但有 3 个人,因此保证其中两个人生日相同。因此,概率为 1,A = B = 1。