[Baltic2007]Connected Points连点
时间限制：5s 空间限制：162MB
题目描述
输入格式
为一个正整数N（ N <= 1, 000, 000, 000）。
输出格式
包括一个整数，即将所有点连成多边形的所有可能的数目模1,000,000,000的结果。
样例输入
3
样例输出
8
提示
30%的测试数据N<=200； 70%的测试数据N<=100,000。
题目来源
没有写明来源
时间限制：5s 空间限制：162MB
为一个正整数N（ N <= 1, 000, 000, 000）。
包括一个整数，即将所有点连成多边形的所有可能的数目模1,000,000,000的结果。
3
8
30%的测试数据N<=200； 70%的测试数据N<=100,000。
没有写明来源