La fila che si accorcia

Davanti al banco dei dolci si mette in fila un numero enorme di persone: esattamente $10^{12}$, numerate da $1$ a $10^{12}$ dalla testa alla coda.

Il fornaio manda via la prima persona della fila, poi lascia passare la seconda, manda via la terza, lascia passare la quarta, e così via fino in fondo: elimina cioè tutte quelle che occupano un posto dispari. Chi resta si ricompatta mantenendo l'ordine, e il fornaio ricomincia da capo con la stessa regola. Va avanti finché resta una sola persona.

Che numero portava, all'inizio, il superstite? Rispondi con le ultime quattro cifre.