Under construction

Still being built. Things may change

The Sweetest Dessert in the World

Time limit1sMemory limit1024 MB

Summary
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 NN. She divides each edge of the cube into NN equal parts, which splits the cube into N3N^3 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 MM times. In each round, she applies the method to all cubes of the same size that currently exist.

The figures above show the cases (N,MN, M) == (4,14, 1) and (4,24, 2).

Find the volume and the surface area of the shape that remains after Hanbyeol carves out the inside of the lokum.

Input

Two integers NN and MM are given, separated by a space. (3≤N≤108,1≤M≤10183\leq N\leq 10^8, 1\leq M\leq 10^{18})

Output

After MM 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 1 000 000 0071\,000\,000\,007.

Examples2

  1. Example 1

    Input
    4 2
    
    Expected output
    1024 2976
    
  2. Example 2

    Input
    31415926 535897932384626433
    
    Expected output
    335375668 278164403