CountingTriangles | Topcoder Archive

Problem Statement

We have a single equilateral triangle. We will now perform a sequence of n steps. In each step, we will take each of the currently smallest equilateral triangles and we will subdivide it into four identical triangles, each half the size of the original one.

You are given the long n. Let X be the number of different ways in which one can find an equilateral triangle in the picture obtained after n steps. As X can be very large, compute and return the value (X modulo 1,000,000,007).

The first two steps are shown in the figure below.

Definition

Class:: CountingTriangles
Method:: findCount
Parameters:: long
Returns:: int
Method signature:: int findCount(long N)
(be sure your method is public)

Constraints

n will be between 1 and 10^18, inclusive.

Examples

```
1
```
```
Returns: 5
```
This test case corresponds to the grid shown in the middle of the figure in the problem statement. If the smallest triangles have side length 1, the figure contains four triangles with side length 1 and one triangle with side length 2.
```
2
```
```
Returns: 27
```
This example corresponds to the grid shown on the right side of the figure. When counting all the triangles, don't miss the one triangle with side length 2 and tip pointing downwards.

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.