问题说明

在一个平面上有一个圆和n组直线，这几组直线中每组中的一条直线在圆内同其他组的直线相交（不存在当前这根线只与一条线相交），假设没有3组直线相交于一点，这个时候Gold King有了一个疑问这些直线最多能将圆分成多少区域呢，请你帮忙一下。

输入格式

输入一个正整数n，表示有n条直线（0<=n<=3000）

输出格式

输出一个正整数，表示对应分成的平面区域数。

2

9

提示

注意：一组平行线的时候是3块区域。

来源/分类

算法培训-05-递推 算法培训-02-递归、递推、错排、排列组合