calculating n choose k mod one million I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula
$$
{n\choose k} = {n\choose k-1} \frac{n-k+1}{k}
$$
so I don't have to calculate huge factorials. Is there any way to use this formula and just keep track of the last 6 digits. Could you compute the next k, with only knowing the some of the last digits.
I understand this is a lot to ask, so all I ask is a point in the right direction.
Maths is by far not my strongest subject.
Thanks in advance.

You might also want to use $\binom{n}{k}=\binom{n}{n-k}$ to reduce the case where $k>n/2$.
Using $\binom{n}{k} = \binom{n}{k-1} \frac{n-k+1}{k}$ mod one million has a problem when $(k,10)\not=1$. Such $k$ are zero divisors mod one million, so you cannot divide by $k$ mod one million and get a meaningful result.
However, you can count the number of factors of $p$ that are in $\binom{n}{k}$ for prime $p$. Let $s_p(n)$ be the sum of the base $p$ digits of $n$.  Then, the number of factors of $p$ in $\binom{n}{k}$ is $(s_p(k)+s_p(n-k)-s_p(n))/(p-1)$.  Thus, instead of multiplying by $n-k+1$ and dividing by $k$, multiply by $n-k+1$ with all factors of $2$ and $5$ removed and divide by $k$ with all factors of $2$ and $5$ removed.  At the end, multiply by the number of factors of $2$ and $5$ computed above.
For example, let's compute $\binom{97}{89}=\binom{97}{8}$.
Here are $97$, $8$, and $89$ in base $2$ and $5$ followed by their sum of digits:
$$
97=1100001_2(3)=342_5(9)
$$
$$
8=1000_2(1)=13_5(4)
$$
$$
89=1011001_2(4)=324_5(9)
$$
Therefore, the number of factors of $2$ in $\binom{97}{89}$ is $(1+4-3)/(2-1)=2$, and the number of factors of $5$ is $(4+9-9)/(5-1)=1$. Therefore, mod one million,
$$
\begin{align}
\binom{97}{8}
&=\frac{97}{1}\frac{96/32}{2/2}\frac{95/5}{3}\frac{94/2}{4/4}\frac{93}{5/5}\frac{92/4}{6/2}\frac{91}{7}\frac{90/10}{8/8}\times2^2\times5^1\\
&=\frac{97}{1}\frac{3}{1}\frac{19}{3}\frac{47}{1}\frac{93}{1}\frac{23}{3}\frac{91}{7}\frac{9}{1}\times4\times5\\
&=010441\times20\\
&=208820
\end{align}
$$
Everything is good above since we can divide by $3$ and $7$ mod one million.
Caveat:
Remember that modular division is quite different than standard division of integers, rationals, and reals. It requires solving a Diophantine equation which usually involves the Euclidean algorithm. For example, $1/7=3\pmod{10}$ because $3\times7=1\pmod{10}$.
