Set's size belong it

For each $k\in\{0; 1; 2; \ldots; 2015\}$ , we want to find how many elements there are of size $k$ .

Note that $k\ne0$ since $0\notin\{1; 2; \ldots; 2015\}$ .

Every subset of size $k$ must contain $k$ . The other $k-1$ elements can be anything. Therefore, there are $\displaystyle \binom{2014}{k-1}$ subsets of size $k$ that contains $k$ .

Therefore, $\displaystyle N=\sum_{k=1}^{2015}\binom{2014}{k-1}=\sum_{k=0}^{2014}\binom{2014}{k}=2^{2014}$ .

We have $\phi(625)=500$ , implies $2^{500}\equiv 1\pmod{625}$

Thus, $2^{2014}\equiv 2^{14}\equiv 16384\equiv 134 \pmod{625}$ .

Combining with $2^{2014}\equiv 0 \pmod{16}$ , yielding $2^{2014}\equiv 6384\pmod{10000}$

So, the answer is $\boxed{6384}$ .