Lego

Vasya received a children's "Lego" construction set as a New Year's gift. The set consists of $3n$ identical pieces, each in the shape of a rectangular parallelepiped with dimensions 1 \times 1 \times 2. The pieces fit perfectly in a rectangular box with dimensions 1 \times 3 \times 2n, with no empty space (all space is filled by the pieces).

Vasya was not interested in assembling cars or houses, so he immediately started putting the pieces back into the box. He enjoyed this activity so much that he decided to scatter the pieces on the floor and reassemble them every day. After some time, he noticed that each time the arrangement of pieces in the box was different. He became interested in finding out how many different ways he could put all the pieces back into the box.

\InputFileA single natural number $n$ (1 \le n \le 100).

\OutputFilePrint the number of ways to fit the pieces into the box. Output the answer modulo 10^9 + 7.