Counting equilateral triangles

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

Medium4MathCombinatoricsImplementationBrute forceInterviewNo attempts yetTime limit1sMemory limit128 MB

Problem

Small equilateral triangles of side length 1 are stacked into a triangular tower of NN 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 NN small triangles counts.

When NN is 2, the answer is 5.

Input

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

Output

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