题目描述

Manao 正在尝试打开一个非常有挑战性的锁。这个锁上有 $n$ 个按钮，要打开它，你需要按照特定的顺序依次按下这些按钮。当你按下某个按钮时，要么该按钮一直保持按下的状态（表示你猜对了，下一个该按的就是这个按钮），要么所有已经按下的按钮会全部复位。当所有按钮都被同时按下时，锁就会被打开。

以有三个按钮为例。假设正确的开启顺序是：{2, 3, 1}。如果你第一次按 1 或 3，则按钮会立即复位。如果你先按 2，则它会保持按下状态。如果在 2 之后按 1，全部按钮会复位。如果在 2 之后按 3，则 2 和 3 会都保持按下。当你已经有两个按钮保持按下时，只需按下按钮 1 就可以打开锁。

Manao 并不知道正确的开启顺序。但是他非常聪明，并且会用最优的策略行动。请计算在最坏情况下，他需要按下按钮的次数。

输入格式

一行一个整数 $n$（$1 \leq n \leq 2000$），表示锁上有多少个按钮。

输出格式

输出一行，在最坏情况下，Manao 需要按下按钮的次数。

说明/提示

请考虑第一个样例测试。Manao 可能第一次按错按钮。如果出现这种情况，他第二次就能猜中正确的按钮。等到他知道第一个正确按钮后，他第三次按就能推测出第二个正确按钮。由此，在最坏情况下，他只需按下 3 次按钮。

由 ChatGPT 5 翻译

样例

2

3

3

7