Олимпиадный тренинг

Задача . кп08-257


(Е. Джобс) Петя составляет четырёхбуквенные слова из букв слова СТЕПУХА и записывает их в алфавитном порядке в список. Вот начало списка:

1. АААА

2. АААЕ

3. АААП

4. АААС

5. АААТ

6. АААУ

7. АААХ

8. ААЕА

...

Сколько существует слов, стоящих на позициях с номером большим 1000, в которых нет двух одинаковых подряд идущих букв?