Задача Bushways. Великий Селекціонер (ВС) завершує роботу, він хоче виростити спеціальний кущ для розведення шовкопряда. Кущ кращий від дерева: в нього буде багато гілок! Від кореня відходитимуть дві гілки (перший рівень розгалужень), від кожної з них – три (другий рівень), від кожної з цих трьох – по чотири (третій рівень), тобто на кожному наступному розгалуженні виростає на одну гілку більше. Оскільки кущ буде щільно вкритий листям, гусениці шовкопряду одержуватимуть достатню кількість їжі на коротких шляхах між розгалуженнями. Треба з’ясувати, скільки буде на кущі різних шляхів з довжиною t ділянок (ділянка – відстань між двома сусідніми розгалуженнями, у ідеального куща довжини всіх ділянок однакові, і їжі на всіх ділянках порівну). Шлях шовкопряда проходить через кожну гілку один раз (вдруге нічого їсти!), а стрибки через гілку неможливі (це ж гусениці!). Будь-які два шляхи відрізняються не менше ніж одною гілкою, якщо визначено шлях в один бік по гілці, шлях в інший бік не можливий (знову ж, не буде що їсти!) . Різні гусениці можуть мати спільні гілки у складі своїх шляхів (вони дуже повільно пересуваються і не чинитимуть перешкод одна одній, а їжа встигне вирости).
Технічні умови. Програма Bushways зчитує з пристрою стандартного введення кількість гілок, що їх зможе «об’їсти» гусениця за своє життя (це 2 або 3) та кількість рівнів розгалужень n – від 1 до 18 включно.
Програма виводить на пристрій стандартного виведення результат – кількість різних шляхів гусениці. Зрозуміло, що починати свій маршрут гусениця може як з кореня куща, так і з будь-якого розгалуження чи верхівки куща.
Приклади
Введення 2 3 Виведення 73
Введення 3 2 Виведення 6