Mr. D is interesting in combinatorial enumeration. Now he want to find out the number of ways on painting the vertexes of a cube. Suppose there are C different colors and two paintings are considered the same if they can transform from one to another by rotation.
For each test case, output the the number of painting ways. And if the number is equal or larger than 10^15, output the last 15 digits.
Case 1: 1
Case 2: 23
Case 3: 031651434916928
HyperHexagon’s Summer Day Gift