Description：

有 $m$ 个在 $[0,2^n)$ 内随机取值的整形变量，求至少有两个变量取值相同的概率。

假设答案为 $\frac a b(gcd(a,b)=1)$ ，输出 $a$ 和 $b$ 对 $10^6+3$ 取模后的值。

$1\le n \le 10^{18}$ $2\le m \le 10^{18}$

Solution：

正难则反，考虑取值两两不同的概率，第一个可以随便选，第二个为了不和第一个相同只有 $2^n-1$ 种取值，所以结果是 $\begin{align}\prod_{i=1}^{m-1}\frac{2^n-i}{2^n}\end{align}$ ，答案就是 $1-\begin{align}\prod_{i=1}^{m-1}\frac{2^n-i}{2^n}\end{align}$ 。

但还没完，由于题目要求求出约分后取模的值，所以不能简单地对分母求逆元，而是要先约分再求逆元，问题就变成了统计 $\begin{align}\prod_{i=1}^{m-1}2^n-i\end{align}$ 里 $2$ 的次数是多少，这个很不好求，但是这个值等于 $(m-1)!$ 里二的次数，因为若 $a+b=2^k$ ，则 $a$ 和 $b$ 中二的次数相同。于是就可以求出这个约数的逆元，并在分子约掉这个数，在分母可以直接指数相减。又发现 $m$ 最大是 $10^{18}$ ，但这其实是骗人的，因为如果 $m\ge10^6+3$ ，那么一定存在一个 $2^n-i$ 是 $10^6+3$ 的倍数，直接输出分母约掉约数即可。注意这时分母不能约分，因为是在模意义下的。还要注意如果 $2^n< m$ ，那么一定会选到两个相同的，可以用 $log2$ 判断大小。还有 $power(2,n*m)=power(power(2,n),m)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000003

typedef long long ll;

ll n,m;

ll cnt2 = 0;

ll power(ll a,ll b)

{

	a %= MOD;

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % MOD;

		a = a * a % MOD;

		b = b >> 1;

	}

	return res;

}

int main()

{

	freopen("random.in","r",stdin);

	freopen("random.out","w",stdout);

	cin >> n >> m;

	if(log2(m) > n)

	{

		puts("1 1");

		return 0;

	}

	ll s = m - 1;

	while(s > 0){cnt2 += s / 2;s /= 2;}

	ll inv = power(power(2,cnt2),MOD - 2);

	if(m >= MOD)

	{

		cout << power(power(2,n),m - 1) * inv % MOD << " " << power(power(2,n),m - 1) * inv % MOD << endl;

		return 0;

	}

	ll res = 1;

	for(ll i = 1;i <= m - 1;++i)

	{

		res = (res * (power(2,n) - i + MOD) % MOD) % MOD;

	}

	cout << ((power(power(2,n),m - 1) - res + MOD) % MOD) * inv % MOD << " " << power(power(2,n),m - 1) * inv % MOD << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}