Задачка

В какой-то математической олимпиаде для школьников была недавно любопытная задачка.

Дано натуральное число k. Посчитайте, сколько существует упорядоченных наборов (a₁,...,a_k), которые удовлетворяют следующим трем условиям:

1)a₁,...,a_k - натуральные числа (возможно, повторяющиеся);

2) разность между любыми двумя соседними числами в наборе не превосходит 2 (т.е. для любого индекса i < k верно неравенство |a_i - a_i+1|< 3)

3) В наборе хотя бы один раз встречается число 4 или число 5 (может быть, оба вместе)

(Слово "упорядоченные" означает, что при изменении порядка чисел набор меняется. То есть (1,3,5,4,3,4) и (1,3,5,4,4,3) - это два различных набора, удовлетворяющих условию задачи при k=6)

С наскока я ее не решил, пришлось остановиться и чуть-чуть подумать.
Комбинаторика там довольно простая, просто надо все аккуратно представить.

( Подсказка 1 )

( Подсказка 2 )

( Подсказка 3 )