Marinada '16

Neka je $a_n$ niz prirodnih brojeva definiran preko: \\ $a_1=1$, \\ $a_{2k}=a_k$, \\ $a_{2k+1}=a_k+1$. \\ Koliko postoji prirodnih brojeva $n$ između $1$ i $2016^{2016}$ (uključujući) takvih da je $a_n=a_{n+1}$ ? Ispišite ostatak pri dijeljenju sa $100$.