UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1344. [Baltic2007]Connected Points连点

统计 下载数据

Description

Input

为一个正整数N( N <= 1, 000, 000, 000)。

Output

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

Sample Input

3

Sample Output

8

Hint

Source