D. BOPC
time limit per test
1 second
memory limit per test
64 megabytes
input
stdin
output
stdout

You invented a new chess figure and called it BOPC. Suppose it stands at the square grid at the point with coordinates X1, Y1. The point with coordinates X2, Y2 is under attack if |X1 - X2| < |Y1 - Y2|. Let the power of the figure denote the number of fields under attack for all possible starting positions of BOPC. Your goal is to calculate the power of BOPC figure given the field size.

Input

Single line containing one integer N — size of the field (1 ≤ N ≤ 109).

Output

Single line containing power of BOPC figure given the field size modulo 109 + 7.

Examples
Input
3
Output
26