Let $ D = 2^n $ be the number of days in a year.
Let $ k $ be the number of people interviewed.
We are to compute the probability that at least two people share a birthday, expressed as an irreducible fraction $ \frac{A}{B} $, and output $ A \mod (10^6 + 3) $ and $ B \mod (10^6 + 3) $.
---
### **Complement Event: All birthdays are distinct**
The probability that all $ k $ people have distinct birthdays is:
$$
P_{\text{distinct}} = \frac{D \cdot (D - 1) \cdot (D - 2) \cdots (D - k + 1)}{D^k} = \prod_{i=0}^{k-1} \left(1 - \frac{i}{D}\right)
$$
Thus, the probability that **at least two** share a birthday is:
$$
P = 1 - P_{\text{distinct}} = 1 - \frac{D! / (D - k)!}{D^k} = \frac{D^k - D^{\underline{k}}}{D^k}
$$
where $ D^{\underline{k}} = D (D - 1) \cdots (D - k + 1) $ is the falling factorial.
So,
$$
\frac{A}{B} = \frac{D^k - D^{\underline{k}}}{D^k}
$$
We must reduce this fraction to lowest terms.
Let:
- Numerator: $ N = D^k - D^{\underline{k}} $
- Denominator: $ D^k $
Then $ A = \frac{N}{\gcd(N, D^k)} $, $ B = \frac{D^k}{\gcd(N, D^k)} $
---
### **Key Observations**
1. **If $ k > D $:** Then $ D^{\underline{k}} = 0 $ (since one term becomes zero), so $ N = D^k $, and $ \frac{A}{B} = 1 $, so $ A = 1, B = 1 $.
2. **If $ k \leq D $:** We compute $ A = D^k - D^{\underline{k}} $, $ B = D^k $, then reduce by $ \gcd(A, B) $.
But $ D = 2^n $, so $ D^k = 2^{nk} $, a power of two.
Therefore, $ \gcd(A, B) = \gcd(D^k - D^{\underline{k}}, D^k) = \gcd(-D^{\underline{k}}, D^k) = \gcd(D^{\underline{k}}, D^k) $
Since $ D^k $ is a power of two, the GCD is the largest power of two dividing $ D^{\underline{k}} $.
So we need to compute $ v_2(D^{\underline{k}}) $, the 2-adic valuation of the falling factorial.
Note: $ D = 2^n $, so $ D^{\underline{k}} = \prod_{i=0}^{k-1} (2^n - i) $
We need to compute $ v_2\left( \prod_{i=0}^{k-1} (2^n - i) \right) $
But $ 2^n - i \equiv -i \pmod{2} $, so we are essentially computing the 2-adic valuation of $ \prod_{i=0}^{k-1} (2^n - i) $
This is equal to $ v_2\left( \prod_{i=1}^{k-1} (2^n - i) \right) $ since $ i=0 $ gives $ 2^n $, which contributes $ n $.
Actually:
$$
D^{\underline{k}} = \prod_{i=0}^{k-1} (D - i) = D \cdot (D - 1) \cdot \ldots \cdot (D - k + 1)
$$
So:
- $ v_2(D^{\underline{k}}) = v_2(D) + \sum_{i=1}^{k-1} v_2(D - i) = n + \sum_{i=1}^{k-1} v_2(2^n - i) $
Now, for $ 1 \leq i \leq k-1 < 2^n $, $ 2^n - i $ is just a number between $ 2^n - (k-1) $ and $ 2^n - 1 $, all less than $ 2^n $, so they are not divisible by $ 2^n $, but may be divisible by lower powers of 2.
We need to compute the total power of 2 dividing the product $ \prod_{i=1}^{k-1} (2^n - i) $
But note: $ \prod_{i=1}^{k-1} (2^n - i) \equiv \prod_{i=1}^{k-1} (-i) = (-1)^{k-1} (k-1)! \pmod{2^m} $ for any $ m $, but valuation is not preserved under congruence.
Actually, $ v_2(2^n - i) = v_2(i) $ **if** $ i < 2^n $ and $ i \ne 0 $, because $ 2^n \equiv 0 \mod 2^{v_2(i)+1} $, so $ 2^n - i \equiv -i \mod 2^{v_2(i)+1} $, and since $ i $ is divisible by $ 2^{v_2(i)} $ but not higher, then $ -i $ is too, and $ 2^n $ is divisible by a higher power, so $ v_2(2^n - i) = v_2(i) $
**This is true!**
> **Lemma:** For $ 1 \leq i < 2^n $, $ v_2(2^n - i) = v_2(i) $
**Proof sketch:** Let $ v = v_2(i) $, so $ i = 2^v \cdot m $, $ m $ odd. Then $ 2^n - i = 2^v (2^{n-v} - m) $. Since $ m $ is odd, $ 2^{n-v} - m $ is odd (because $ n > v $, so $ 2^{n-v} $ is even if $ n-v \geq 1 $, minus odd = odd). So $ v_2(2^n - i) = v = v_2(i) $.
Thus:
$$
v_2(D^{\underline{k}}) = v_2\left( \prod_{i=0}^{k-1} (D - i) \right) = v_2(D) + \sum_{i=1}^{k-1} v_2(D - i) = n + \sum_{i=1}^{k-1} v_2(i)
$$
But $ \sum_{i=1}^{k-1} v_2(i) = v_2((k-1)!) $
So:
$$
v_2(D^{\underline{k}}) = n + v_2((k-1)!)
$$
Therefore:
- $ v_2(B) = v_2(D^k) = nk $
- $ v_2(N) = v_2(D^k - D^{\underline{k}}) $
We now compute $ v_2(N) = v_2(D^k - D^{\underline{k}}) $
Note: $ D^k = 2^{nk} $, and $ D^{\underline{k}} $ has 2-adic valuation $ n + v_2((k-1)!) $
Let $ v = n + v_2((k-1)!) $
Then $ D^{\underline{k}} \equiv 0 \mod 2^v $, and $ D^k \equiv 0 \mod 2^{nk} $
We want $ v_2(D^k - D^{\underline{k}}) $
Since $ v_2(D^k) = nk $, and $ v_2(D^{\underline{k}}) = v $, then:
- If $ v < nk $, then $ v_2(D^k - D^{\underline{k}}) = v $
- If $ v = nk $, then we need to compute the exact difference — but since $ D^k $ is divisible by a higher power, and $ D^{\underline{k}} $ is divisible by exactly $ 2^v $, then $ D^k - D^{\underline{k}} \equiv -D^{\underline{k}} \mod 2^{v+1} $, so valuation is still $ v $
Wait: Actually, if $ v < nk $, then $ D^k \equiv 0 \mod 2^{v+1} $, and $ D^{\underline{k}} \equiv 0 \mod 2^v $ but not $ 2^{v+1} $, so $ D^k - D^{\underline{k}} \equiv -D^{\underline{k}} \not\equiv 0 \mod 2^{v+1} $, so $ v_2(N) = v $
If $ v = nk $, then both terms divisible by $ 2^{nk} $, and we need to know if $ D^k \equiv D^{\underline{k}} \mod 2^{nk+1} $
But $ D^k = (2^n)^k = 2^{nk} $
$ D^{\underline{k}} = \prod_{i=0}^{k-1} (2^n - i) $
We need to compute $ D^{\underline{k}} \mod 2^{nk+1} $
But this is complicated. However, note:
We are only required to compute $ A = \frac{D^k - D^{\underline{k}}}{\gcd(D^k - D^{\underline{k}}, D^k)} $, and $ B = \frac{D^k}{\gcd(\cdot)} $
Since $ D^k = 2^{nk} $, the gcd is $ 2^{\min(v_2(N), nk)} = 2^v $, because $ v_2(N) = v = n + v_2((k-1)!) $, and we have:
> **Claim:** $ v = n + v_2((k-1)!) \leq nk $ always?
> For $ k \geq 2 $, $ v_2((k-1)!) \leq k-2 $, so $ v \leq n + k - 2 $. But $ nk \geq 2n \geq n + 2 $ for $ n \geq 2, k \geq 2 $.
> For $ n=1, k=2 $: $ v = 1 + v_2(1!) = 1 + 0 = 1 $, $ nk = 2 $, so $ v < nk $.
> For $ n=1, k=3 $: $ v = 1 + v_2(2!) = 1 + 1 = 2 $, $ nk = 3 $, so $ v < nk $.
> For $ k > 2^n $, we already handled: $ D^{\underline{k}} = 0 $, so $ v_2(D^{\underline{k}}) = \infty $, but we handle that case separately.
Actually, when $ k > D = 2^n $, then $ D^{\underline{k}} = 0 $, so $ N = D^k $, so $ A = 1, B = 1 $
So we assume $ k \leq 2^n $
Then $ v = n + v_2((k-1)!) \leq n + (k-2) \leq n + 2^n - 2 $
But $ nk \geq 2n $, and for $ n \geq 1 $, $ 2n \geq n + 2 $ when $ n \geq 2 $, and for $ n=1 $, $ k \leq 2 $, so $ k=2 $: $ v=1 $, $ nk=2 $, so $ v < nk $
Thus, **in all cases where $ k \leq 2^n $, we have $ v < nk $**
Therefore:
$$
v_2(N) = v = n + v_2((k-1)!)
$$
$$
v_2(B) = nk
$$
$$
\gcd(N, B) = 2^v
$$
Thus:
- $ A = \frac{D^k - D^{\underline{k}}}{2^v} $
- $ B = \frac{D^k}{2^v} = 2^{nk - v} $
We must compute $ A \mod (10^6 + 3) $, $ B \mod (10^6 + 3) $
But $ D^k = 2^{nk} $, $ D^{\underline{k}} = \prod_{i=0}^{k-1} (2^n - i) $
We need to compute:
- $ A = \frac{2^{nk} - \prod_{i=0}^{k-1} (2^n - i)}{2^v} $
- $ B = 2^{nk - v} $
But $ v = n + v_2((k-1)!) $
We cannot compute $ 2^{nk} $ directly since $ n, k \leq 10^{18} $
So we must compute everything modulo $ M = 10^6 + 3 = 1000003 $
Note: $ M $ is prime.
We need to compute:
### Step 1: Check if $ k > 2^n $
But $ n \leq 10^{18} $, so $ 2^n $ is astronomically huge. We cannot compute $ 2^n $.
But we can check: if $ k > 2^n $, then since $ 2^n \geq 1 $, and $ k \leq 10^{18} $, then if $ n \geq 60 $, $ 2^n > 10^{18} $, so $ k \leq 10^{18} < 2^n $
So:
- If $ n \geq 60 $, then $ k \leq 10^{18} < 2^{60} < 2^n $, so $ k \leq 2^n $
- If $ n < 60 $, then $ 2^n \leq 2^{59} \approx 5.76 \times 10^{17} $, so we can compute $ 2^n $ as integer and compare with $ k $
So:
- If $ n < 60 $ and $ k > 2^n $: output $ A = 1, B = 1 $
- Else: proceed with $ k \leq 2^n $
### Step 2: Compute $ v = n + v_2((k-1)!) $
We need $ v_2((k-1)!) = \sum_{i=1}^{\infty} \left\lfloor \frac{k-1}{2^i} \right\rfloor $
This is computable in $ O(\log k) $
### Step 3: Compute $ B = 2^{nk - v} \mod M $
Since $ M = 1000003 $ is prime, we can compute exponent modulo $ \phi(M) = M - 1 = 1000002 $
So compute:
$ exp_B = (nk - v) \mod \phi(M) $, but if $ nk - v \geq \phi(M) $, we can reduce exponent mod $ \phi(M) $ only if base and modulus coprime — which they are (2 and M coprime)
So:
$ B \equiv 2^{(nk - v) \mod \phi(M)} \mod M $, but if $ nk - v < 0 $, then $ B = 0 $? No, $ v < nk $ always, so $ nk - v > 0 $
So compute:
$ exp_B = (nk - v) \mod \phi(M) $
But $ nk $ can be huge: $ n, k \leq 10^{18} $, so $ nk \leq 10^{36} $
We compute $ nk \mod \phi(M) $, then subtract $ v \mod \phi(M) $, then mod $ \phi(M) $
Similarly for $ A $:
### Step 4: Compute $ A = \frac{2^{nk} - \prod_{i=0}^{k-1} (2^n - i)}{2^v} \mod M $
We need to compute numerator $ N = 2^{nk} - \prod_{i=0}^{k-1} (2^n - i) $, then divide by $ 2^v $
But we are working modulo $ M $, and division by $ 2^v $ is multiplication by inverse of $ 2^v \mod M $
But we must compute the product $ P = \prod_{i=0}^{k-1} (2^n - i) \mod {2^v \cdot M} $? No — we need exact value modulo $ M $, but we are dividing by $ 2^v $
Actually, since we know $ v_2(N) = v $, then $ N $ is divisible by $ 2^v $, so $ A = N / 2^v $ is integer.
We can compute $ A \mod M $ as:
$ A \equiv \left( (2^{nk} \mod {M \cdot 2^v}) - P \mod {M \cdot 2^v} \right) / 2^v \mod M $
But $ v $ can be large? $ v = n + v_2((k-1)!) \leq n + \log_2(k-1) \leq 10^{18} + 60 $, so $ 2^v $ is astronomical — we cannot compute modulo $ M \cdot 2^v $
Alternative approach:
We compute $ N \mod M $, and $ 2^v \mod M $, and then compute $ A \equiv N \cdot (2^v)^{-1} \mod M $
But is this valid?
Only if $ v_2(N) = v $, then $ N / 2^v $ is integer, and we want $ A \mod M $
We have:
$ A = N / 2^v $
We want $ A \mod M $
We can compute $ N \mod (M \cdot 2^v) $, then divide by $ 2^v $, then mod M — but $ 2^v $ is too big.
But note: since $ M $ is prime and odd, and $ 2^v $ is a power of two, $ \gcd(2^v, M) = 1 $, so $ 2^v $ has an inverse mod $ M $
Therefore, we can compute:
$ A \equiv (2^{nk} - P) \cdot (2^v)^{-1} \mod M $
Where $ P = \prod_{i=0}^{k-1} (2^n - i) \mod M $
But we must compute $ 2^{nk} \mod M $, $ 2^n \mod M $, and the product $ \prod_{i=0}^{k-1} (2^n - i) \mod M $
But $ k $ can be up to $ 10^{18} $, so we cannot iterate over $ k $ terms.
We must compute $ \prod_{i=0}^{k-1} (x - i) \mod M $ where $ x = 2^n \mod M $
This is the polynomial $ x^{\underline{k}} = \prod_{i=0}^{k-1} (x - i) $
We can compute this modulo $ M $ using the fact that if $ k \geq M $, then the product includes a factor $ \equiv 0 \mod M $, because $ x - i \equiv 0 \mod M $ for some $ i \in [0, M-1] $, since $ i $ runs over $ k $ consecutive integers, and if $ k \geq M $, then the set $ \{x, x-1, ..., x-k+1\} \mod M $ covers all residues mod M, so one of them is 0.
Thus:
- If $ k \geq M = 1000003 $, then $ P \equiv 0 \mod M $
- Else, $ k < M $, so we can compute the product in $ O(k) $ time (but $ k \leq 10^{18} $, so if $ k \geq M $, we skip loop)
So:
**Algorithm:**
Given $ n, k $
1. Let $ M = 1000003 $, $ \phi = M - 1 = 1000002 $
2. If $ n < 60 $ and $ k > (1LL << n) $:
→ Output `1 1`
3. Else:
a. Compute $ v = n + v_2((k-1)!) $
→ Use: $ v_2((k-1)!) = \sum_{i=1}^{\infty} \left\lfloor \frac{k-1}{2^i} \right\rfloor $
→ Stop when $ 2^i > k-1 $
b. Compute $ x = 2^n \mod M $
→ Use modular exponentiation: $ x = \text{pow}(2, n \mod \phi, M) $
But note: $ 2^n \mod M $, since $ M $ prime, use $ 2^{n \mod \phi} \mod M $
c. Compute $ P = \prod_{i=0}^{k-1} (x - i) \mod M $
- If $ k \geq M $: then since $ i $ runs over $ k \geq M $ consecutive integers, and $ x $ is fixed, then among $ x, x-1, ..., x-k+1 $, there must be some $ i $ such that $ x - i \equiv 0 \mod M $, because residues mod M repeat every M, and k >= M → so one term ≡ 0 → P ≡ 0 mod M
- Else (k < M):
Compute product iteratively:
$ P = 1 $
for $ i = 0 $ to $ k-1 $:
$ P = P \cdot (x - i) \mod M $
d. Compute $ N = (2^{nk} - P) \mod M $
→ Compute $ 2^{nk} \mod M $:
Let $ exp = (n \cdot k) \mod \phi $
$ pow2_nk = \text{pow}(2, exp, M) $
$ N = (pow2_nk - P + M) \mod M $
e. Compute $ inv_2v = \text{modular inverse of } 2^v \mod M $
→ But $ v $ can be huge, so compute $ 2^v \mod M $ first:
$ pow2_v = \text{pow}(2, v \mod \phi, M) $
Then $ inv_2v = \text{pow}(pow2_v, M-2, M) $
f. $ A = N \cdot inv_2v \mod M $
g. Compute $ B = 2^{nk - v} \mod M $
→ $ exp_B = (nk - v) \mod \phi $
But since $ nk - v $ may be negative? No, $ v < nk $ always
So $ exp_B = (nk - v) \mod \phi $
$ B = \text{pow}(2, exp_B, M) $
4. Output $ A \mod M $, $ B \mod M $
---
### **Edge: k = 1**
But input says $ k \geq 2 $, so no problem.
### **Final Code Logic (pseudocode):**
```python
M = 1000003
phi = M - 1
n, k = map(int, input().split())
# Case 1: k > 2^n
if n < 60:
days = 1 << n
if k > days:
print("1 1")
exit()
# Compute v = n + v2((k-1)!)
def v2_factorial(m):
if m <= 0:
return 0
cnt = 0
p = 2
while p <= m:
cnt += m // p
p *= 2
return cnt
v = n + v2_factorial(k - 1)
# Compute x = 2^n mod M
x = pow(2, n % phi, M)
# Compute P = product_{i=0}^{k-1} (x - i) mod M
if k >= M:
P = 0
else:
P = 1
for i in range(k):
P = (P * (x - i)) % M
# Compute 2^(n*k) mod M
exp_nk = (n % phi) * (k % phi) % phi
pow2_nk = pow(2, exp_nk, M)
# N = (2^(n*k) - P) mod M
N = (pow2_nk - P) % M
if N < 0:
N += M
# Compute 2^v mod M
pow2_v = pow(2, v % phi, M)
inv_2v = pow(pow2_v, M - 2, M)
A = (N * inv_2v) % M
# Compute B = 2^(nk - v) mod M
exp_B = (exp_nk - v) % phi
if exp_B < 0:
exp_B += phi
B = pow(2, exp_B, M)
print(A, B)
```
But note: $ n \cdot k \mod \phi $: we did $ (n \mod \phi) \cdot (k \mod \phi) \mod \phi $ — this is valid because $ \phi $ is the totient.
However, $ n \cdot k $ might be huge, but modulo $ \phi $, we can compute:
$ (n \cdot k) \mod \phi = ((n \mod \phi) \cdot (k \mod \phi)) \mod \phi $
Yes.
This should work.
Let’s test with sample:
**Sample 1: n=3, k=2**
- D = 8
- k=2 <= 8 → proceed
- v = 3 + v2(1!) = 3 + 0 = 3
- x = 2^3 mod M = 8
- P = product_{i=0}^{1} (8 - i) = (8)(7) = 56
- 2^(3*2) = 2^6 = 64
- N = 64 - 56 = 8
- A = 8 / 2^3 = 1
- B = 2^{6-3} = 8
→ Output: 1 8 → correct
**Sample 2: n=1, k=3**
- 2^1 = 2, k=3 > 2 → output 1 1 → correct
Another test: n=2, k=3 → D=4
v = 2 + v2(2!) = 2 + 1 = 3
x = 2^2 = 4
P = (4)(3)(2) = 24
2^(2*3)=64
N=64-24=40
A=40 / 8 = 5
B=8
But probability = 1 - (4*3*2)/64 = 1 - 24/64 = 40/64 = 5/8 → so A=5, B=8 → correct
Compute mod M: 5 mod M =5, 8 mod M=8 → output 5 8
All good.
---
### ✅ Final Answer:
We output $ A \mod M $ and $ B \mod M $ as computed above.
The mathematical formulation is:
Let $ D = 2^n $, $ v = n + v_2((k-1)!) $
If $ k > D $:
$ A = 1 $, $ B = 1 $
Else:
$ A = \frac{D^k - D^{\underline{k}}}{2^v} $, $ B = \frac{D^k}{2^v} $
With $ D^{\underline{k}} = \prod_{i=0}^{k-1} (D - i) $
And compute modulo $ 10^6 + 3 $ using modular arithmetic as above.