We're Not Looking For Trailing Zeroes?

Relevant wiki: Factorials Problem Solving - Intermediate

First we can find the number of trailing zeros of $2015!$ . Which is 502. $\lfloor \dfrac{2015}{5}\rfloor + \lfloor \dfrac{2015}{25}\rfloor + \lfloor \dfrac{2015}{125}\rfloor + \lfloor \dfrac{2015}{625}\rfloor = 502$ . Now Let $M$ be $\dfrac{2015!}{5^{502}}$ and $N$ be $\dfrac{M}{2^{502}}$ .We want to find $N \pmod{1000}$ .

Let's start with $M \pmod {1000}$ which can be reduced to the separated calculus of $M \pmod 8$ and $M \pmod {125}$ thanks to Chinese Remainder Theorem.
We can notice that $\dfrac{2015!}{5^{502}}=1\times2\times3\times4\times1\times6\times7\times8\times9\times2\times11\times12\times13\times\ldots$
So $M \pmod 8$ is obviusly $\equiv 0$ so now we have to find $M \pmod {125}$ .

There is a nice pattern in that, $1\times2\times3\times4 \equiv 6\times7\times8\times9 \equiv \ldots \equiv 24 \pmod{125}$ . So we have $24^{403}$ (there are 403 repetition), now we can notice that we have the same pattern repeted for those factors which are in the form $5k$ . So There are $24^{80}\times 401\times402\times403$ <--the last 3 terms are "extra" so we have to count them apart.
Now there is the same pattern for those terms $5^2k$ so there is $24^{16}$ , then for those terms $5^3k$ there is $24^{3}$ and at the end we have $1\times2\times3\times16$ which is the last pattern with 3 factor of the form $5^4k$ and the last factor $=16$ . How rewriting everything we have $24^{403}\times24^{80}\times24^{16}\times24^{3}\times31\times6\times16$ using properties of powers $24^{502}\times31\times6\times16$ and we have to calculate it $\pmod{125}$ and using $\phi(125)=100$ that is equal to $24^2\times101$ that can be easily calculate and it is $51\pmod{125}$ . Applying CRT we have $\begin{cases} M \equiv 0 \pmod 8 \\ M \equiv 51 \pmod{125} \end{cases}$ . So $M\equiv 176 \pmod{1000}$ .
About $2^{502}$ It is thanks to $\phi$ $\equiv 4 \pmod {125}$ and applying CRT to calculate last 3 digits we have $\begin{cases} 2^{502} \equiv 0 \pmod 8 \\ 2^{502} \equiv 4 \pmod{125} \end{cases}$ . So it is $504$ .
Now $\dfrac{M}{2^{502}}$ can be rewritten as $\dfrac{176}{504} \pmod{1000}$ . Applying another time CRT we have $\begin{cases} \dfrac{176}{504} \equiv 0 \pmod 8 \\ \dfrac{176}{504} \equiv \dfrac{51}{4} \pmod{125} \end{cases}$

For the second one we can multiply by 4 obtaining $4X \equiv 51 \pmod{125}$ . the $inv_{125}(4)=94$ <--we can obtain it solving an easy diophantine $4j-125k=1$ .
$94\times4X \equiv 94\times51 \pmod{125} \implies X\equiv 44 \pmod{125}$

Last thing is to solve this CRT system:

$\begin{cases} X \equiv 0 \pmod 8 \\ X \equiv44 \pmod{125} \end{cases}$ .

And the solution is $X\equiv 544 \pmod{1000}$

Let’s define the function: A(n) which removes all trailing zeros from n. Example: A(120) = 12, A(1200003) = 1200003 and A(46900) = 469 and so on. We want to find (A(2015!)) mod 1000.

Let’s also define D(0) = 1 X 2 X 3 X 4 X 6 X 7 X 8 X 9, D(1) = 11 X 12 X 13 X 14 X 16 X 17 X 18 X 19, D(2) = 21 X 22 X 23 X 24 X 26 X 27 X 28 X 29, and in general: D(n) = (10n + 1) X (10n + 2) X (10n + 3) X (10n + 4) X (10n + 6) X (10n + 7) X (10n + 8) X (10n + 9) It can easily be shown that: D(n) mod 1000 = D(n mod 1000)

Since 2015! = 1 X 2 X 3 X 4 …. X 2011 X 2012 X 2013 X 2014 X 2015. Let’s separate the multiples of 5 together.

2015! = (1 X 2 X 3 X 4 X 6 X 7 X 8 X 9) X (11 X 12 X 13 X 14 X 16 X 17 X 18 X 19) X … X (2001 X 2002 X 2003 X 2004 X 2006 X 2007 X 2008 X 2009) X (2011 X 2012 X 2013 X 2014 X (5 X 10 X 15 X 20 X 25 X 30 X … X 2000 X 2005 X 2010 X 2015)

2015! = D(0) X D(1) X D(2) X … D(200) X (2011 X 2012 X 2013 X 2014) X (5 X 10 X 15 X 20 X 25 X 30 X … X 2000 X 2005 X 2010 X 2015)

2015! = D(0) X D(1) X D(2) X … D(200) X (2011 X 2012 X 2013 X 2014) X 5^403 X (1 X 2 X 3 X 4 X 5 X … 403)

2015! = D(0) X D(1) X D(2) X … D(200) X (2011 X 2012 X 2013 X 2014) X 5^403 X 403! (1)

In the same way, we can develop 403! 403! = D(0) X D(1) X D(2) X … D(39) X (401 X 402 X 403) X 5^80 X 80! (2)

In the same way, we can develop 80! 80! = D(0) X D(1) X D(2) X … D(7) X 5^16 X 16! (3)

In the same way, we can develop 16! 16! = D(0) X (11 X 12 X 13 X 14 X 16) X 5^3 X 3! (4)

From 1, 2, 3, 4 we get:

2015! = (D(0) X D(1) X D(2) X … D(200)) X (D(0) X D(1) X D(2) X … D(39)) X (D(0) X D(1) X D(2) X … D(7)) X D(0) X 5^502 X (2011 X 2012 X 2013 X 2014) X (401 X 402 X 403) X (11 X 12 X 13 X 14 X 16) X 6 (5)

Let us define E(n) = D(n) mod 1000 E(n) = ((10n + 1) X (10n + 2) X (10n + 3) X (10n + 4) X (10n + 6) X (10n + 7) X (10n + 8) X (10n + 9)) mod 1000 E(n) = ((10n + 1) X (10n + 9) X (10n + 2) X (10n + 8) X (10n + 3) X (10n + 7) X (10n + 4) X (10n + 6)) mod 1000 E(n) = ((100n2 + 100n + 9) X (100n2 + 100n + 16) X (100n2 + 100n + 21) X (100n2 + 100n + 24)) mod 1000 E(n) = ((100n2 + 100n + 9) X (100n2 + 100n + 16)) mod 1000 X ((100n2 + 100n + 21) X (100n2 + 100n + 24) mod 1000) mod 1000 E(n) = ((500n2 + 500n + 144) mod 1000 X ((500n2 + 500n + 504) mod 1000) mod 1000 E(n) = 144 X 504 mod 1000 = 576 (6)

From 5 and 6: A(2015!) mod 1000 = A((576 ^ (201 + 40 + 8 + 1) mod 1000 X 5^502 X (2011 X 2012 X 2013 X 2014) X (401 X 402 X 403) X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

A(2015!) mod 1000 = A((576 ^ 250) mod 1000 X 5^502 mod 1000 X (2011 X 2012 X 2013 X 2014) mod 1000 X (401 X 402 X 403) mod 1000 X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

A(2015!) mod 1000 = A(376 X 5^502 mod 1000 X (11 X 12 X 13 X 14) mod 1000 X (401 X 402 X 403) mod 1000 X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

A(2015!) mod 1000 = A(376 X 5^502 X 24 X (406) X (11 X 12 X 13 X 14 X 16) X 6) mod 1000

It can be easily shown that if n is a multiple of 8 then : (376 X n) mod 1000 = n mod 1000

A(2015!) mod 1000 = A(5^502 X 24 X 406 X 6 X (11 X 12 X 13 X 14 X 16)) mod 1000
A(2015!) mod 1000 = A(5^502 X 464 X 11 X 12 X 13 X 14 X 16) mod 1000
A(2015!) mod 1000 = A(5^502 X 104 X 12 X 13 X 14 X 16) mod 1000
A(2015!) mod 1000 = A(5^502 X 248 X 13 X 14 X 16) mod 1000
A(2015!) mod 1000 = A(5^502 X 224 X 14 X 16) mod 1000
A(2015!) mod 1000 = A(5^502 X 136 X 16) mod 1000
A(2015!) mod 1000 = A(5^502 X 136 X 16) mod 1000
A(2015!) mod 1000 = A(5^502 X 176) mod 1000 (11)

Since 2^100 mod 1000 = 376 Then 2^600 mod 1000 = 376

In 11: A(2015!) mod 1000 = A(5^502 X 176 X 2^600) mod 1000
A(2015!) mod 1000 = A(10^502 X 176 X 2^98) mod 1000
A(2015!) mod 1000 = (176 X 2^98) mod 1000
Since 2^80 mod 1000 = 176, 2^10 mod 1000 = 24, 2^8 mod 1000 = 256,
2^98 mod 1000 = (176 X 24 X 256) mod 1000 = 344 A(2015!) mod 1000 = (176 X 344) mod 1000 = 544