#1344. [Baltic2007]Connected Points连点

题目描述

输入格式

为一个正整数N（ N <= 1, 000, 000, 000）。

输出格式

包括一个整数，即将所有点连成多边形的所有可能的数目模1,000,000,000的结果。

样例

样例输入

3

样例输出

8

数据范围与提示