Migrated from Lutece 1396 With Friends Like These

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

If you have ever player the video game Starcraft 2 the heart of the swarm, you may finished the mission With Friends Like These.

The queen of the blades Sarah Kerrigan find the human’s space ship Hyperion and its’ captain Matt Horner. They decide to make a deal with a mercenary Mira Han to let her

release a computer master to save Jim Raynor who is the leader of revolution army and the lover of Kerrigan.

But things go badly due to the avarice of the mercenary Mira Han. Mira Han claim that she has no right to release the computer master without the agreement of Jim. Finally

Matt Horner think things are not negotiable, so he has to fight with Mira by using his Battlecruiser Hyperion.

You can regard the space as a Cartesian coordinate system, the Hyperion is now at the point of $(0,0,0)$. The Battlecruiser Hyperion can jump to a neighboring integer point

every step, for example, if the ship is now at the point of $(1,0,-1)$, it can jump to $(1,-1,-1)$ or $(1,0,-2)$ etc in the next step. Because the space is full of minor planet,

Matt can only drive the Hyperion randomly and it has the same probability to jump to any direction.

Worrying her lover Jim, Kerrigan wants to know the expect number of points the Hyperion visited after $N$ steps.

Because the queen’s mind is invaded by worry and anxiety, this task is given to you, you need to make a program to calculate the expect number of visited points. \

$1\le N \le 500$

Input

An integer $N$ means $N$ steps

Output

We define $E$ as the expect number of visited points, you should output an integer $E*6^Nmod1000000007$

Samples

1

12

2

102

Resources

IEEEXTREME Programming Competition / 2016 UESTC Training for Math