Hi Codeforces, I'm wondering is it possible to calculate $$$C_n^k$$$ modulo $$$m$$$ with $$$n \leq 10^9, k \leq 10^5, m \leq 10^9$$$. I've already known that if $$$m$$$ is a big prime number (for example $$$10^9+7$$$), we can easily have an $$$O(k) \cdot log_2(m)$$$ algorithm using Fermat's little theorem to find the inverse modulo of number from $$$1$$$ to $$$k$$$. If $$$n$$$ is small (for example $$$n \leq 10^6$$$), we can use sieve to get rid of the dividing step, but if $$$n$$$ is big, I have no clue. Thanks in advance.