Every element of $S$ is $\frac{k}{9999}$ with $1 \le k \le 9999$ and $9999 = 3^2 \cdot 11 \cdot 101$

$m$ is a numerator exactly when $m \le D$ and $\gcd(m, D) = 1$ for some divisor $D$ of $9999.$ Classify $m$ by which of $3,$ $11,$ or $101$ divide it.

Every element of $S$ equals $\frac{k}{9999}$ for some $1 \le k \le 9999,$ where $9999 = 3^2 \cdot 11 \cdot 101.$ In lowest terms this is $\frac{m}{D}$ where $D$ divides $9999,$ $m \le D,$ and $\gcd(m, D) = 1;$ conversely any such $\frac{m}{D}$ arises from $k = m \cdot \frac{9999}{D}.$ So $N$ counts the integers $m$ that are at most, and coprime to, some divisor $D$ of $9999.$

Classify $m$ by which of the primes $3,$ $11,$ or $101$ divide it, always using the largest divisor $D$ coprime to $m.$ If $\gcd(m, 9999) = 1,$ take $D = 9999:$ there are $\varphi(9999) = 6000$ such $m.$ If only $3$ divides $m,$ take $D = 11 \cdot 101 = 1111:$ multiples of $3$ up to $1111$ avoiding $11$ and $101$ number $370 - 33 - 3 = 334.$ If only $11$ divides $m,$ take $D = 9 \cdot 101 = 909:$ that gives $82 - 27 = 55.$ If only $101$ divides $m,$ then $D = 99 \lt 101$ admits none. If $m$ is divisible by $33$ but not by $101,$ take $D = 101:$ the values $33,$ $66,$ and $99$ give $3$ more, and any $m$ divisible by $3 \cdot 101$ or $11 \cdot 101$ would need $D \le 11,$ which is impossible.

Therefore $N = 6000 + 334 + 55 + 3$ $= 6392,$ and the remainder modulo $1000$ is $392.$