Migrated from Lutece 451 Tetris

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

As we all played tetris, lili did too, and he is a good player. When he was tired, he began to think about some of the other problems about tetris. He wants to change the width to $3$,And he does not like the shape which is a line.And then, lili sets the height a number $h$($0\leq h\leq 50000$). To play this game, he also wants all the grid be covered .

Of course every time you can use any kind of the given shapes,and you can flip and rotate it.Notice that,a grid can covered only once. He wants to know the number of method.

Input

Multiple cases.

A number $h$.

Output

The number of the method mod $100000007$.

Samples

0
1
4

1
0
16

Note

You can use any kind of the given shapes except the shape which lili does not like.

Resources

5th BUPT Programming Contest Final