When lwh took part in the big company interview, the interviewer gave a hard question to lwh, lwh felt it too simple, so he threw the question to you, the question is: You have a grid of size n \times 3 and you want to paint each cell of the grid with exactly one of the three colours: Red, Yellow or Green while making sure that no two adjacent cells have the same colour (no two cells that sharevertical or horizontal sides have the same colour).

Only a positive integer n \ (1≤n≤5000) the number of rows of the grid.

Return the number of ways you can paint this grid. As the answer may grow large, the answer must be computed modulo 10^9+ 7.