Buttons

题意翻译

Manao在试图打开一个锁。锁有在它上面的 n个按钮并打开它，你应该按一定的顺序按下按钮来打开锁。当您按下某个按钮时，它会一直按下锁定（这意味着您已经正确猜到并按下顺序中的下一个按钮），或者所有按下的按钮都返回到初始位置。当所有按钮立即按入锁中时，锁将打开。 考虑一个带有三个按钮的示例。假设开场序列是：{2,3,1}。如果您首先按下按钮1或3，按钮会立即取消按下。如果您先按下按钮2，它会保持按下状态。如果在2之后按1，则所有按钮都会按下。如果在2之后按3，则按住按钮3和2。只要有两个按下的按钮，您只需按下按钮1即可打开锁定。 Manao不知道开场顺序。但他非常聪明，他将以最佳方式行事。计算在最坏的情况下他必须按下按钮才能打开锁的次数。

题目描述

Manao is trying to open a rather challenging lock. The lock has $ n $ buttons on it and to open it, you should press the buttons in a certain order to open the lock. When you push some button, it either stays pressed into the lock (that means that you've guessed correctly and pushed the button that goes next in the sequence), or all pressed buttons return to the initial position. When all buttons are pressed into the lock at once, the lock opens. Consider an example with three buttons. Let's say that the opening sequence is: {2, 3, 1}. If you first press buttons 1 or 3, the buttons unpress immediately. If you first press button 2, it stays pressed. If you press 1 after 2, all buttons unpress. If you press 3 after 2, buttons 3 and 2 stay pressed. As soon as you've got two pressed buttons, you only need to press button 1 to open the lock. Manao doesn't know the opening sequence. But he is really smart and he is going to act in the optimal way. Calculate the number of times he's got to push a button in order to open the lock in the worst-case scenario.

输入输出格式

输入格式

A single line contains integer $ n $ ( $ 1<=n<=2000 $ ) — the number of buttons the lock has.

输出格式

In a single line print the number of times Manao has to push a button in the worst-case scenario.

输入输出样例

输入样例 #1

2

输出样例 #1

3

输入样例 #2

3

输出样例 #2

7

说明

Consider the first test sample. Manao can fail his first push and push the wrong button. In this case he will already be able to guess the right one with his second push. And his third push will push the second right button. Thus, in the worst-case scenario he will only need 3 pushes.