Форум: «ЕГЭ по информатике»

Здравствуйте, подскажите, пожалуйста решение задачи:

(№ 5073) (Н. Вольхин) Николай составляет слова из букв C, O, N, S, T. Каждый символ в последовательности может встречаться любое количество раз или не встречаться совсем. Слова должны удовлетворять следующим условиям:
1) не содержат двух одинаковых букв, стоящих рядом;
2) буква S не может быть первой и последней в слове;
3) буква S может находится только между двумя разными буквами.
Сколько различных 16-буквенных слов может составить Николай?

Не пойму по какому алгоритму её решать

Простым перебором не получается, так как очень большой список получается:

 
 from itertools import * 
  
 l = set(map(''.join, product('CONST', repeat=16))) 
 count = 0 
 for x in l: 
     if 'CC' not in x and 'OO' not in x and 'NN' not in x and 'SS' not in x and 'TT' not in x\ 
         and x[0] != 'S' and x[15] != 'S' and \ 
             'CSC' not in x and 'OSO' not in x and 'NSN' not in x and 'TST' not in x: 
         count += 1 
  
 print(count)

Пытался сделать таким же способом, как здесь: https://youtu.be/btX4IOUjF08

 
 from itertools import * 
 n = 10 
 for j in range(1, n): 
     l = set(map(''.join, product('CONST', repeat=j))) 
     count = 0 
     for x in l: 
         if 'CC' not in x and 'OO' not in x and 'NN' not in x and 'SS' not in x and 'TT' not in x\ 
             and x[0] != 'S' and x[j - 1] != 'S' and \ 
                 'CSC' not in x and 'OSO' not in x and 'NSN' not in x and 'TST' not in x: 
             count += 1 
  
     print(count)

Вывод:
4
12
48
180
684
2592
9828
37260
141264

Отношение к предыдущему различное:
4 : 4.0
12 : 3.0
48 : 4.0
180 : 3.75
684 : 3.8
2592 : 3.789473684210526
9828 : 3.7916666666666665
37260 : 3.791208791208791
141264 : 3.791304347826087

В итоге закономерности не вижу