Stringhe ternarie di lunghezza 9 senza la sottostringa 012

Quante stringhe di lunghezza 9 sull'alfabeto $\{0, 1, 2\}$ non contengono la sottostringa 012, cioè non hanno mai tre caratteri consecutivi uguali a 0, 1, 2 in quest'ordine?