the-battle-17

The Battle between Shinigami's in the Shinigami world has gone to new levels. They are fighting each other for notebooks of death. 
They are standing at such positions that vertices form a convex polygon ( a convex polygon has all of its interior angles less than 180 degrees). Each one of them fights some other Shinigami's. So we have diagonals in the polygon depicting who fight whom.  
The rule being followed in this battle states that no three diagonals will intersect in a point in the given polygon.     
Supposing that no three diagonals will intersect in a point in the given polygon, you have to find the number of intersections between all pairs of diagonals in the polygon.    

Shown is one such polygon for N=6. 
Input 
First line of input contains N, denoting the number of vertices of given polygon.    

Output 
Output the required output on one line modulo 1000000007.    

Constraints 
3 ≤ N ≤ 10^7

SAMPLE INPUT
6

SAMPLE OUTPUT
15

Source: hackerearth | Difficulty: MEDIUM
Tags: Mathematics


Solutions: