You are given a regular polygon with $n$ vertices labeled from $1$ to $n$ in counter-clockwise order. The triangulation of a given polygon is a set of triangles such that each vertex of each triangle is a vertex of the initial polygon, there is no pair of triangles such that their intersection has non-zero area, and the total area of all triangles is equal to the area of the given polygon. The weight of a triangulation is the sum of weigths of triangles it consists of, where the weight of a triagle is denoted as the product of labels of its vertices.

Calculate the minimum weight among all triangulations of the polygon.


-----Input-----

The first line contains single integer $n$ ($3 \le n \le 500$) — the number of vertices in the regular polygon.


-----Output-----

Print one integer — the minimum weight among all triangulations of the given polygon.


-----Examples-----
Input
3

Output
6

Input
4

Output
18



-----Note-----

According to Wiki: polygon triangulation is the decomposition of a polygonal area (simple polygon) $P$ into a set of triangles, i. e., finding a set of triangles with pairwise non-intersecting interiors whose union is $P$.

In the first example the polygon is a triangle, so we don't need to cut it further, so the answer is $1 \cdot 2 \cdot 3 = 6$.

In the second example the polygon is a rectangle, so it should be divided into two triangles. It's optimal to cut it using diagonal $1-3$ so answer is $1 \cdot 2 \cdot 3 + 1 \cdot 3 \cdot 4 = 6 + 12 = 18$.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
ans = 0
for i in range(1, n - 1):
    ans += (i + 1) * (i + 2)
print(ans)

ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())

n = ii()
ans = 0
for i in range(3, n + 1):
    ans += i * (i - 1)
print(ans)

n = int(input())
print(n*(n - 1)*(n + 1)//3 - 2)

n = int(input())
t = 0

for i in range(n-2):
    t += (i+2)*(i+3)

print(t)

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))




n=nn()

total=0

for i in range(n-2):
	total=total+1*(i+2)*(i+3)

print(total) 


def li ():
	return list (map (int, input ().split ()))


def num ():
	return map (int, input ().split ())


def nu ():
	return int (input ())

mm = 1000000007


def solve ():
	t = 1
	for it in range (t):
		n=nu()
		cc=0
		for i in range(2,n):
			cc+=i*(i+1)
		print(cc)



def __starting_point():
	solve ()
__starting_point()

N = int(input())
ans = 0
for i in range(N-2):
    ans += (i+2)*(i+3)

print(ans)


# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
ans = 0
for i, j in zip(list(range(2, N+1)), list(range(3, N+1))):
    ans += i*j
print(ans)


n=int(input())-2
print(n*(n*n+6*n+11)//3)

n=int(input())
ans=0
for i in range(2, n):
    ans+=i*(i+1)
print(ans)


# stdin=open('input.txt')

# def input():
# 	return stdin.readline()[:-1]

# a, b = map(int, input().split())

# l = list(map(int, input().split()))


# CODE BEGINS HERE.................

ans = 0
for t in range(2, int(input())):
	ans += t*(t + 1)

print(ans)
#CODE ENDS HERE....................





n = int(input())
n = n - 1

print(n * (n + 1) * (2 * n + 1) // 6 + n * (n + 1) // 2 - 2)

n = int(input())
m = 0
for i in range(2, n):
	m += i * (i + 1)
print(m)

#JMD
#Nagendra Jha-4096

 
import sys
import math

#import fractions
#import numpy
 
###File Operations###
fileoperation=0
if(fileoperation):
    orig_stdout = sys.stdout
    orig_stdin = sys.stdin
    inputfile = open('W:/Competitive Programming/input.txt', 'r')
    outputfile = open('W:/Competitive Programming/output.txt', 'w')
    sys.stdin = inputfile
    sys.stdout = outputfile

###Defines...###
mod=1000000007
 
###FUF's...###
def nospace(l):
    ans=''.join(str(i) for i in l)
    return ans
 
 
 
##### Main ####
t=1
for tt in range(t):
    n=int(input())
    ans=0
    for i in range(2,n):
        ans+=i*(i+1)
    print(ans)
    #n,k,s= map(int, sys.stdin.readline().split(' '))
    #a=list(map(int,sys.stdin.readline().split(' ')))
    
    
#####File Operations#####
if(fileoperation):
    sys.stdout = orig_stdout
    sys.stdin = orig_stdin
    inputfile.close()
    outputfile.close()

n=int(input())
ans=0
for i in range(2,n):
     ans+=i*(i+1)
print(ans)

n=int(input())
ans=0
for i in range(2,n,1):
	ans+=i*(i+1);
print(ans)

a = int(input())
ans = 0
for i in range(a - 2):
    ans += (i + 2) * (i + 3)
print(ans)

#!/usr/bin/env python3
import sys

def rint():
    return list(map(int, sys.stdin.readline().split()))
#lines = stdin.readlines()

n = int(input())

ans = 0
for i in range(2,n):
    ans += i*(i+1)

print(ans)


n = int(input())
print(sum(i * (i - 1) for i in range(3, n + 1)))


n = int(input())
ans = 0
for i in range(2, n):
    ans += i * (i + 1)
print(ans)


n = int(input())
cnt = 0
for i in range(3, n + 1):
    cnt += i * (i - 1)
print(cnt)

n=int(input())
ans=0
for i in range(2,n):
    ans+=(i*(i+1))
print(ans)

import re, math, decimal, bisect
def read(): return input().strip()
def iread(): return int(input().strip())
def viread(): return [int(_) for _ in input().strip().split()]

# code goes here
n = iread()
_sum = 0
for i in range(n - 2):
    _sum += (i + 2) * (i + 3)
print(_sum)