CF711E ZS and The Birthday Paradox

ZS the Coder 最近发现了一个有趣的概念叫做“生日悖论”。它表明在一组随机选择的 $23$ 个人中，有大约 $50\%$ 的概率存在两个人生日相同。ZS the Coder 觉得这很有意思，于是决定在 Udayland 的居民中验证这一现象。 在 Udayland，一年有 $2^{n}$ 天。ZS the Coder 想要采访 $k$ 个人，每个人的生日都在这 $2^{n}$ 天中的某一天（每一天的概率均等）。他对至少有两个人生日在同一天的概率感兴趣。 ZS the Coder 了解到答案可以写成最简分数 $\frac{A}{B}$ 的形式。他不喜欢处理浮点数，希望你帮他找到 $A$ 和 $B$。 由于 $A$ 和 $B$ 可能非常大，请输出 $A$ 和 $B$ 模 $10^6+3$ 的结果。注意，在取模之前，$A$ 和 $B$ 需要互质。

输入包含一行两个整数 $n$ 和 $k$，表示一年有 $2^{n}$ 天，ZS the Coder 要采访恰好 $k$ 个人。 $1 \leq n \leq 10^{18}$，$2 \leq k \leq 10^{18}$。

如果至少有两个人生日相同的概率为最简分数 $\frac{A}{B}$，请输出 $A$ 和 $B$，用空格隔开。输出结果需先将 $A$ 和 $B$ 约分到互质后再取模 $10^6+3$。

在第一个样例中，一年有 $2^{3}=8$ 天。对于 $2$ 个人，生日相同的概率显然是 $\frac{1}{8}$，因此 $A=1$，$B=8$。 在第二个样例中，一年只有 $2^{1}=2$ 天，但有 $3$ 个人，因此必然有两人生日相同。概率是 $1$，即 $A=B=1$。 由 ChatGPT 5 翻译