The Sweetest Dessert in the World
Time limit1sMemory limit1024 MB
Find the volume and surface area mod 1,000,000,007 after carving a side-N cube M times, keeping only the small cubes that touch the original edges.
- Level
Medium6 of 10
- Topics
- Math, Recursion, Implementation
- Solved
- No attempts yet
Problem
Hanbyeol is making lokum, a traditional jelly from Turkey and Greece. Lokum is made by boiling starch, water, sugar, lemon juice, and other ingredients in a pot, stirring until it thickens, and then dusting the outside with powdered sugar and letting it set. Hanbyeol wants to make the lokum even sweeter. She realizes that if she enlarges the surface area of the lokum, more powdered sugar will stick to the outside, and the dessert will be much sweeter.
Hanbyeol starts with a cube of lokum whose width, depth, and height are each . She divides each edge of the cube into equal parts, which splits the cube into small cubes. Then she removes every small cube except those that contain an edge of the original large cube. The same procedure can be applied to each small cube that remains, carving out the inside of each one in the same way. Hanbyeol repeats this process times. In each round, she applies the method to all cubes of the same size that currently exist.


The figures above show the cases () () and ().
Find the volume and the surface area of the shape that remains after Hanbyeol carves out the inside of the lokum.
Input
Two integers and are given, separated by a space. ()
Output
After rounds, print the volume and the surface area of the lokum, separated by a space. Since the answers can be large, print each one modulo .