题目描述

有$\red{m}$个在$\red{[0,2^n)}$内均匀随机取值的整型变量，求至少有两个变量取值相同的概率。

为了避免精度误差，假设你的答案可以表示成的形式($\red{}$其中$\red{(ab)=1}$)，你需要输出$\red{a}$和$\red{b}$对$\red{10^6+3}$取模后的值。

输入格式

第一行两个正整数 $\red{n, m}$。

输出格式

一行两个整数，它们的含义如题所述。

样例

输入样例1

3 2

输出样例1

1 8

输入样例2

1 3

输出样例2

1 1

输入样例3

4 3

输出样例3

23 128

提示

对于 $\red{10\% }$的数据，$\red{nm < 16}$；

对于 $\red{30\% }$的数据，$\red{nm < 64}$；

对于 $\red{50\% }$的数据，$\red{nm ≤}$ $\red{10^3}$；

对于 $\red{70\% }$的数据，$\red{m ≤}$ $\red{10^6}$；

对于 $\red{100\% }$的数据，$\red{1 ≤}$ $\red{n ≤}$ $\red{10^{18} , 2 ≤}$ $\red{m ≤}$ $\red{10^{18}}$。