题目背景

把字刻在石头上。 ——罗辑

战斗渐渐平息，苍凉的战场上野指针四处飞溅，ssh 还未断开的窗口不断燃烧，放出 $01$ 串的浓烟，AKIOI 的压缩文件残骸里散落着破碎的指令集，平日滴滴作响的 qq.exe 也只得躲在残破的防火墙后面瑟瑟发抖。

这时，人们发现由于你 A 了前两题来做 T3，在前面的电子战中毫发无损，便在物理世界向你冲来，你只得亡命机房。逃亡路上，你看到路过的一台电脑上的一个玄学阵法，决定把它布置出来把身后的追兵扔进沙盒里。

题目描述

你要布置一个阵法，这个阵法十分简单，只需要在一个圆上任意取 $n$ 个点刻上不同的 AK 图章，并把 AK 图章两两连线，生成沙盒的坚固程度为这样雕刻布阵后形成的三角形个数，现在你从 C 盘文件夹里搜出 个不同的 AK 图章,想知道阵法的最大威力是多少。答案对 $100000007$ 取模。

如果有 4 个图章排成正方形，如图所示，则共形成了 $8$ 个三角形（其中 4 个面积为正方形的 $1/4$ ，4 个面积为正方形 $1/2$）。

输入格式

输入一行一个整数 $n$。

输出格式

输出一行一个整数为阵法的最大威力。

样例 #1

样例输入 #1

6

样例输出 #1

111

提示

对 $10\%$ 的数据保证 $n\le 10$；

对 $30\%$ 的数据保证 $n \le 1000$；

对 $100\%$ 的数据保证 $n \le 10000$ 。