<A HREF="http://www.randomservices.org/random/urn/Birthday.html">Birthday problem:</A>

The probability density function of the number of distinct values $Z$ for population size $M$ and sample size $N$ is given by
$$P(Z = j) = \binom{M}{j} \sum_{k=0}^j (-1)^k \binom{j}{k} \left(\frac{j - k}{M}\right)^N, \quad j \in \{1, 2, \ldots, \min(M,N)\}$$
$$=\frac{M!}{M^N(M-j)!}S_N^{(j)}$$
(<A HREF="https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind">Stirling number of the second kind</A>)   
If you wish $Z$ to be close to $M$ with large probability you will need $N\gtrsim M\log M$.