[Baltic2007]Connected Points连点

时间限制:5s      空间限制:162MB

题目描述


输入格式

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


输出格式

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


样例输入

3

样例输出

8


提示

30%的测试数据N<=200; 70%的测试数据N<=100,000。


题目来源

没有写明来源