Dr. Skywind is drawing a picture, using his favorite six colors, namely red, orange, yellow, green, blue, and violet.
The paper has N grids in a line. Each time he will fill a grid with one of the six colors. All grids needs to be filled. To make his drawing more beautiful, Skywind decided to draw symmetrically. Moreover, as he hates sorting, Skywind will never come up with the situation where all colors are in their original order. So he won't draw red-orange-yellow-green-blue-violet in a continuous way. And to make his drawing clearer, he won't paint the same color in adjacent grids.
Given N, you are asked to calculate the number of ways that Skywind can complete his drawing. As the answer might be very large, just output the number MOD 112233.
There are multiple test cases ended with an EOF. Each test case will be a line containing one positive integer N. (N <= 10^9)
For each test case, output the answer MOD 112233 in a single line.