Філософський камінь (phil_stone)
Щоб перешкодити Волан де Морту в його пошуках філософського каменю, Гаррі Потер та його друзі Рон Уізлі і Герміона Грейнджер вирішили створити копію реліквії. У древніх фоліантах Герміона знайшла алгоритм отримання філософського каменю і тепер друзям залишилося втілити його в життя. Виявилося, що філософський камінь – це не суцільна субстанція, а структура, що складається з однакових кубиків. За основу береться паралелепіпед розміром NxMxH кубиків. Він називається філософським каменем нульового рівня. Щоб збільшити силу цього філософського каменя, потрібно до кожної доступної вільної грані кубиків, що входять до конструкції, прикріпити магічним способом по такому самому кубику. Закріпивши усі можливі кубики на початковій конструкції, друзі отримали філософський камінь першого рівня. Герміона переконала друзів, що сила створеного каменя недостатня і хлопці вирішили продовжити роботу.
З’ясувалося, що для створення філософського каменя будь-якого наступного рівня необхідно повторювати вже описану процедуру, тобто до всіх вільних граней кубиків конструкції поточного рівня приєднувати магічним шляхом такі ж кубики. Зупиняти будівництво рівня заборонено, так як філософський камінь при цьому втрачає свою силу. Поступово збільшуючи рівень філософського каменя, можна добитися того, що він стане практично всесильним. Але є одна проблема. Кількість кубиків, що є будівельним матеріалом для філософського каменя обмежена. І Гаррі стало цікаво: якщо друзям потрібно створити філософський камінь К рівня, скільки мінімально необхідно мати кубиків в запасі.
Формат входу-виходу:
Программа phil_stone зчитує з клавіатури (стандартного пристрою введення) три натуральних числа, що не перевищують 106 – розмір початкового паралелепіпеда, і з наступного рядка номер бажаного рівня К (ціле невід’ємне число, не більше 106).
Программа phil_stone виводить на екран (стандартний пристрій виведення) єдине число – необхідну кількість кубиків для побудови конструкції рівня К по модулю 109+7.
Приклад вхідних и вихідних даних:
|
Введення
|
Виведення
|
|
1 1 1
2
|
25
|
|
2 2 2
1
|
32
|
