题目描述

在一张足够大的空白纸上画 $n$ 条直线。这些直线的位置可以自行安排。

为了使纸张被分成的部分尽可能多，画线时可以保证：

• 任意两条直线都不平行；
• 任意三条直线不交于同一点。

请问，最多能将这张纸划分成多少个部分？

输入格式

输入一个整数 $n$，表示直线的条数。

输出格式

输出一个整数，表示最多能划分出的部分数。

数据范围

$1\le n\le 10^7$。答案可能较大，请使用 64 位整数。

输入输出样例

样例 1 输入

1

样例 1 输出

2

样例 2 输入

7

样例 2 输出

29

说明

第 k 条直线与前面 k-1 条直线产生 k-1 个不同交点，因此最多新增 k 个区域。