ConvexHexagons | Topcoder Archive

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

```
4
```
```
Returns: 7
```
There are 7 hexagons:
```
7
```
```
Returns: 232
```
```
104
```
```
Returns: 635471838
```
```
1
```
```
Returns: 0
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.