Solution:

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 \mid 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, 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 $3 \mid m$ only, take $D = 11 \cdot 101 = 1111:$ multiples of $3$ up to $1111$ avoiding $11$ and $101$ number $370 - 33 - 3 = 334.$ If $11 \mid m$ only, take $D = 9 \cdot 101 = 909:$ that gives $82 - 27 = 55.$ If $101 \mid m$ only, then $D = 99 \lt 101$ admits none. If $33 \mid m$ but $101 \nmid m,$ take $D = 101:$ the values $33, 66, 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.$