Find $\binom{80}{40}\bmod 2000$ 
Find $\displaystyle\binom{80}{40}\bmod 2000$.

So far, I've found that $\displaystyle\binom{80}{40}$ is divisible by $2^2$ and $5^1$, so the answer isn't $0$. Usually, with smaller numbers, I would split the $\bmod 2000$ into $2^4$ and $5^3$, find the answer through brute force for each of those, then use the Chinese Remainder theorem. But $80$ and $40$ are too big for this.
 A: Since $${80 \choose 40} = \frac{80\cdot 79 \cdot 78 \cdot 77 \cdot ...\cdot 41}{40 \cdot 39 \cdot 38 \cdot 37 \cdot ... \cdot 1}$$ we can cancel the terms in the denominator with terms in the numerator leaving a factor of $2$, so $2^{40}$ is a factor of the answer. It only remains to see how many factors of 5 remain.  $75, 65, 55$, and $45$ are all factors, so at least $5^4$ is a factor.  As a result, the expression is definitely a multiple of $2000$, so modulo $2000$ the answer is $0$.
EDIT: A few minutes later I realized my mistake, and returned to find several people pointing it out: only the numbers down to 21 in the denominator cancel.  That still leaves $$\frac{2 \cdot 79 \cdot 2 \cdot 77 \cdot 2 \cdot 75 \cdot...\cdot 2 \cdot 41}{ 20 \cdot 19 \cdot 18 \cdot...\cdot 3 \cdot 2 \cdot 1}$$ which gives $20$ factors of $2$ in the numerator and $10 + 5 + 2 + 1 = 18$ factors of $2$ in the denominator, so only $2^2$ is a factor. For the $5's$, we have $5$ factors in the numerator and $4$ in the denominator, so it is a multiple of $5$ but not $5^2$.
So now we have $$\frac{79 \cdot 77 \cdot 3 \cdot 73 \cdot...\cdot 43 \cdot 41}{ 19 \cdot 9 \cdot 17 \cdot 3 \cdot 7...\cdot 6 \cdot 3}$$. Continuing to cancel factors, we find $3^{8}$ in the numerator and $3^8$ in the denominator, and so forth. We end up computing ${80 \choose 40}$ and then can find the answer by inspection.
A: I built Pascal's triangle in a spreadsheet program, but always reducing mod 2000. There's never a need to keep more than the result mod $2000$. The result I get is $1620$.

*

*Cell A2: 0

*Cell A3: =A2+1 and carry down to Cell A82 with value $80$.

*Cell B1: 0

*Cell C1: =B1+1 and carry rightward to Cell AP1 with value $40$.

Now these are the indices of Pascal's triangle. For $\binom{n}{k}$, $n$ is in column A and $k$ is in row 1.

*

*Cell B2: 1 and carry all the way down.

*Cell C3: =MOD(B2+C2,2000), carry all the way rightward, and then all the way down, filling out the table.

Now Cell AP82 is $\binom{80}{40}$ mod $2000$. It gives $1620$.
To do this by hand, at first it may seem like you would calculate about $80\cdot40=3200$ cell entries mod $2000$. But actually you would only need to compute about $\frac14$ of those entries, as represented in blue here:

The red is all $0$. The orange is not needed to reach the $\binom{80}{40}$ cell. And the green can be written using symmetry from the blue. So this would take about $800$ additions mod $2000$ plus some other less signiicant labor.

But we an do better, because there is the identity $$\binom{80}{40}=\sum_{n=0}^{40}\binom{40}{n}^2=\binom{40}{20}+2\sum_{n=0}^{19}\binom{40}{n}^2$$
So actually if we can get Pascal's triangle down to the first half of the 40th row, then we can square mod $2000$ about 20 times, double, sum the results mod $20$ and have our answer.
A similar analysis reveals that you would need to calculate about $400$ of the entries of Pascal's triangle mod $2000$ for this approach.
