题目描述

Manao 在试图打开一个锁。锁有在它上面的 $n$ 个按钮并打开它，你应该按一定的顺序按下按钮来打开锁。当您按下某个按钮时，它会一直按下锁定（这意味着您已经正确猜到并按下顺序中的下一个按钮），或者所有按下的按钮都返回到初始位置。当所有按钮立即按入锁中时，锁将打开。

考虑一个带有三个按钮的示例。假设开场序列是：$\{2,3,1\}$。

• 如果您首先按下按钮 $1$ 或 $3$，按钮会立即取消按下。
• 如果您先按下按钮 $2$，它会保持按下状态。
• 如果在 $2$ 之后按 $1$，则所有按钮都会按下。
• 如果在 $2$ 之后按 $3$，则按住按钮 $3$ 和 $2$。
• 只要有两个按下的按钮，您只需按下按钮 $1$ 即可打开锁定。

Manao 不知道开场顺序。但他非常聪明，他将以最佳方式行事。计算在最坏的情况下他必须按下按钮才能打开锁的次数。

输入格式

一个整数 $n$，$1\le n\le 2000$。

输出格式

输出一个整数表示答案。

2

3

3

7