Migrated from Lutece 1859 Smothered

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Calculate

$\sum_{x1=1}^{N}\sum_{x2=x1}^N\sum_{x3=x2}^N\sum_{x4=x3}^N(N-x1)\cdot(N-x2)\cdot(N-x3)\cdot(N-x4) \mod 10^9 + 7$

Input

The first line contains a postive integer $N$ $(1 \leq N \leq 666).$

Output

Print the corresponding answer in a single line.

Samples

5

1701

10

359502

15

8408778

Resources

The 16th UESTC Programming Contest Preliminary