SimpleMazeEasy | Topcoder Archive

Problem Statement

A level-n simple maze consists of five squares arranged into the shape of a cross. Each square consists of n times n rooms, each having the shape of a unit square. Simple mazes of level 1 and level 3 are shown below, with each '.' representing one cell.

 .
...
 .

   ...
   ...
   ...
.........
.........
.........
   ...
   ...
   ...

In a single step you can move from your current room into any room that shares a side with your room. The distance between two rooms is the smallest number of steps needed to get from one room to the other.

You are given the long n. Consider the level-n simple maze. For each pair of rooms compute their distance. Let S be the sum of all those distances. Compute and return the value S modulo (10^9 + 7).

Definition

Class:: SimpleMazeEasy
Method:: findSum
Parameters:: long
Returns:: int
Method signature:: int findSum(long n)
(be sure your method is public)

Constraints

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

Examples

```
1
```
```
Returns: 16
```
The level-1 simple maze consists of five rooms. There are four pairs of adjacent rooms (i.e., distance = 1). There are six pairs of rooms that are at distance 2. Thus, the sum of all distances is 4*1 + 6*2 = 16.
```
3
```
```
Returns: 4680
```
```
5
```
```
Returns: 61000
```
```
12345
```
```
Returns: 598011702
```
don't forget mod.
```
1000000000000
```
```
Returns: 763641672
```

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.