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。