Counting equilateral triangles

Interview

Time limit1sMemory limit128 MB

Summary

Given a triangular tower with N layers of unit triangles, count every equilateral triangle of any size, both upward and downward pointing.

Level: Medium4 of 10
Topics: Math, Combinatorics, Implementation, Brute force
Solved: No attempts yet

Problem

Small equilateral triangles of side length 1 are stacked into a triangular tower of $N$ layers. Count how many equilateral triangles, large and small together, the lines of that figure form. Triangles pointing up and triangles pointing down both count, and every side length from 1 small triangle up to $N$ small triangles counts.

When $N$ is 2, the answer is 5.

Input

The first line contains the layer count $N$ of the triangular tower. ( $1 \le N \le 10{,}000$ )

Output

Print the total count of triangles, large and small together, on the first line.

Examples2

Example 1
Input
```
2
```
Expected output
```
5
```
Example 2
Input
```
10
```
Expected output
```
315
```