Исполнитель «Цифрень» преобразует число на экране и использует цифровой корень при применении команд. Цифровой корень числа это рекурсивная сумма цифр числа, пока не останется одна цифра. Например, для числа 1993 цифровой корень будет 1+9+9+3 =>, 2+2 =>, 4. У исполнителя есть две команды, которым присвоены номера:
A. Прибавить 1
B. Прибавить 2
Программа для исполнителя – это последовательность команд. Программа не должна содержать команды, в которых цифровой корень исходного числа равен цифре младшего разряда результирующего числа. Сколько существует программ, для которых при исходном числе 12 результатом является число 37?
Например, можно к исходному числу 18 (цифровой корень 9) применить команду «Прибавить 2» и получим 20 (9 != 0) и нельзя к числу 20 (цифровой корень 2) прибавить 2 и получить 22, т.к. (2 == 2).