ZS and The Birthday Paradox
Contest: Codeforces Round 369 (Div. 2)
Difficulty rating: 2300
Tags: math, number theory, probabilities

ZS the Coder has recently found an interesting concept called the Birthday Paradox. It states that given a random set of 23 people, there is around 50% chance that some two of them share the same birthday. ZS the Coder finds this very interesting, and decides to test this with the inhabitants of Udayland.

In Udayland, there are 2n days in a year. ZS the Coder wants to interview k people from Udayland, each of them has birthday in one of 2n days (each day with equal probability). He is interested in the probability of at least two of them have the birthday at the same day.

ZS the Coder knows that the answer can be written as an irreducible fraction $$\frac{\overline{A}}{\overline{B}}$$. He wants to find the values of A and B (he does not like to deal with floating point numbers). Can you help him?

Input format:
The first and only line of the input contains two integers n and k (1 ≤ n ≤ 1018, 2 ≤ k ≤ 1018), meaning that there are 2n days in a year and that ZS the Coder wants to interview exactly k people.

Output format:
If the probability of at least two k people having the same birthday in 2n days long year equals $$\frac{\overline{A}}{\overline{B}}$$ (A ≥ 0, B ≥ 1, $$\gcd(A,B)=1$$), print the A and B in a single line.

Since these numbers may be too large, print them modulo 106 + 3. Note that A and B must be coprime before their remainders modulo 106 + 3 are taken.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample case, there are 23 = 8 days in Udayland. The probability that 2 people have the same birthday among 2 people is clearly $${ \frac { 1 } { 8 } }$$, so A = 1, B = 8.

In the second sample case, there are only 21 = 2 days in Udayland, but there are 3 people, so it is guaranteed that two of them have the same birthday. Thus, the probability is 1 and A = B = 1.

Example input:
3 2

Example output:
1 8

Example input:
1 3

Example output:
1 1

Editorial:
Note that MOD = 106 + 3 is a prime.
Firstly, if we have k > 2n, then by pigeonhole principle we must have 2 people with the same birthday. Thus, we can directly output 1 1.
Thus, now we suppose k ≤ 2n. Then, instead of computing the probability directly, we compute the complement, i.e. the probability that all the people have distinct birthdays. This probability turns out to be much simpler to calculate, as it is just $${ \frac { ( 2 ^ { n } - 1 ) ( 2 ^ { n } - 2 )... ( 2 ^ { n } - ( k - 1 ) ) } { 2 ^ { ( k - 1 ) n } } }$$. (Fix the birthday of the first person, the probability that the second person has different birthday is $$\frac{2^n - 1}{2^n}$$, and for the next person it's $$\frac{2^n - 2}{2^n}$$ and so on.
Now, we know that the denominator is just a power of 2. However, we still have to reduce the fraction to the lowest terms. Note that $${ \frac { a } { b } }$$ is in the lowest terms if and only if $$1 - \frac{a}{b} = \frac{b-a}{b}$$ is in the lowest terms, since $$\gcd(a,b) = \gcd(b-a,b)$$. Also, note that the gcd is a power of 2 since the denominator is a power of 2. Thus, we need to find the highest power of 2 that divides (2n - 1)(2n - 2)...(2n - (k - 1)). This is also equal to the sum of the highest power of 2 that divides 2n - 1, 2n - 2, ..., 2n - (k - 1).
Now, if a power of 2 divides x < 2n, then it must also divides 2n - x and vice versa. So, we can actually translate this to finding the sum of highest power of 2 that divides 1, 2, ..., k - 1, or the highest power of 2 that divides (k - 1)!. Now, this is simple to calculate by Legendre's formula (which is quite easy to prove) in $$O(\log k)$$.
Now that we find the gcd of the numerator and denominator, we can immediately find the reduced denominator by binary exponentiation. For the numerator, we need a bit more work, since we have to deal with (2n - 1)(2n - 2)...(2n - (k - 1)). However, it is not hard either. The key fact is that MOD is small, so if k - 1 ≥ MOD, the product above is equal to 0 modulo MOD, because among MOD consecutive integers there must be one that is a multiple of MOD. Thus, the above product can be calculated in O(MOD) if k - 1 ≤ MOD and O(1) otherwise. The remaining parts can be calculated using direct binary exponentiation.
One minor note is that when we're calculating 2(k - 1)n, the value of (k - 1)n might overflow. One way to resolve this is to reduce it modulo MOD - 1, since 2MOD - 1 ≡ 1 modulo MOD by Fermat's Little Theorem. Another way is to just evaluate 2k - 1 first, then take the result and raise it to the n-th power.
Time Complexity : $${ \mathcal { O } } ( M O D + \log k + \log n )$$