Одномерное динамическое программирование

Исполнитель Счетовод преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавь 1
2. Умножь на 3
3. Прибавь предыдущее

При выполнении команды 3 к текущему числу прибавляется число, меньшее на 1 (например к числу 5 нужно будет прибавить число 4).
Примечание: для числа 1 предыдущим принять тоже 1.
Программа для исполнителя Счетовод – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 15?