Solution:

Work in the ring $\mathbb{F}_{503}[x]/(x^{502} - 1).$ Reducing $(1 + x)^{10000} = \sum_k \binom{10000}{k} x^k$ replaces each exponent $k$ by $k \bmod 502,$ so $$(1+x)^{10000} \equiv \sum_{r=0}^{501} S_r \, x^r \pmod{503,\ x^{502} - 1}.$$

Since $503$ is prime, $(1+x)^{503} \equiv 1 + x^{503} \pmod{503},$ and $x^{503} = x \cdot x^{502} \equiv x,$ so $(1+x)^{503} \equiv 1 + x$ in this ring. Writing $10000 = 19 \cdot 503 + 443,$ $$(1+x)^{10000} = \left((1+x)^{503}\right)^{19} (1+x)^{443} \equiv (1+x)^{19} (1+x)^{443} = (1+x)^{462}.$$ As $462 \lt 502,$ no exponents fold, so $S_r \equiv \binom{462}{r} \pmod{503}$ for $0 \le r \le 501,$ where $\binom{462}{r} = 0$ for $r \gt 462.$

For $0 \le r \le 462$ the binomial coefficient $\binom{462}{r}$ is not divisible by $503:$ both $462$ and $r$ are single digits in base $503,$ so Lucas' theorem gives a nonzero value (indeed $\binom{462}{r} = \frac{462!}{r!\,(462-r)!}$ involves no factor of $503$). Hence $S_r \equiv 0 \pmod{503}$ exactly for $r = 463, 464, \ldots, 501,$ which is $501 - 463 + 1 = 39$ values.