如何在$O(n)$的时间复杂度内计算出$C_n^k\bmod (10^9+7) (k\leq n,n\leq 10^5)$

我试过这些方法，都没用

1. 直接用乘除法计算：如果计算完之后再取模的话会爆炸，一边计算一边取模的话则商的余数不等于余数的商。

2. 通过递归计算$C_n^k=C_{n-1}^k+C_{n-1}^{k-1}$：时间复杂度爆炸

3. 递归计算完$A_n^k$再除：商的余数不等于余数的商，所以不行。

所以各位大佬有更好地办法吗？