Il calcolo più lento

Il computista della zecca calcola il massimo comune divisore di due numeri con l'algoritmo delle divisioni successive: dati $a > b > 0$, sostituisce la coppia $(a,b)$ con $(b,\ a \bmod b)$, e ripete finché il secondo numero diventa zero. Ogni sostituzione conta come una divisione.

Il computista vuole il caso peggiore: cerca il più piccolo valore di $b$ per cui esista un $a > b$ tale che il calcolo richieda esattamente $20$ divisioni.

Quanto vale questo $b$? Rispondi con le ultime quattro cifre.