Вот тут на контесте попалась такая вот ДП. Не могу понять, как решить. Вот условие :

Рассмотрим двухбуквенные последовательности, которые могут состоять только из букв a, b и при этом: 1.никогда не содержат двух букв b подряд, 2.ни в одном последовательности никогда не встречается три одинаковых подпоследовательности подряд. Например, этому правилу не удовлетворяют следующие последовательности: aaa (так как три раза подряд содержит a), ababab (так как три раза подряд содержит ab), aabababa (также три раза подряд содержит ab).

Напишите программу, которая подсчитает количество всех двухбуквенных последовательностей длинной ровно K символов, удовлетворяющих сформулированным выше правилам.

Формат входных данных

Вводится одно число K (1 ≤ K ≤ 100 000).

Формат выходных данных

Выведите одно число — количество различных двухбуквенных последовательностей длины K.

У меня получилась формула a[i] = a[i-1]+a[i-2]-x; Но вот что отнимать надо тут(этот пресловутый x), я не знаю.

Может кто-то поможет.

Большое спасибо!