### Problem Statement

Petya likes triangles. He draws a trianglar grid using the following process: He starts off with an equilateral triangle. He then draws points on the edges of this triangle, dividing each edge up into N equal-length segments. Next, he connects each pair of points that is at equal distance from some vertex of the triangle with a straight line, ending up with N*N smaller equilateral triangles. An example of this figure with N = 4 is shown below.

However, he likes hexagons more than he likes triangles. How many non-degenerate convex hexagons can be formed using the line segments in his figure? This number can be very big, so return it modulo 1000000007.

### Definition

 Class: ConvexHexagons Method: find Parameters: int Returns: int Method signature: int find(int N) (be sure your method is public)

### Notes

-The length of each edge of every hexagon must be greater than zero.

### Constraints

-N will be between 1 and 500000, inclusive.

### Examples

0)

 `4`
`Returns: 7`
 There are 7 hexagons:
1)

 `7`
`Returns: 232`
2)

 `104`
`Returns: 635471838`
3)

 `1`
`Returns: 0`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10715

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14179&pm=10715

Seyaua

#### Testers:

Rustyoldman , timmac , StevieT , maksay , K.A.D.R , Seyaua

#### Problem categories:

Dynamic Programming, Math