Manao 正在尝试打开一把颇具挑战性的锁。锁上有n个按钮,要打开它,你应该按一定的顺序按下按钮才能打开锁。当您按下某个按钮时,它要么保持压入锁中(这意味着您已经猜对并按下了序列中的下一个按钮),要么所有按下的按钮都返回到初始位置。当所有按钮同时按下锁时,锁就会打开。
考虑一个具有三个按钮的示例。假设开头序列是:{2,3,1}。如果您首先按下按钮 1 或 3,按钮会立即松开。如果您首先按下按钮 2,它将保持按下状态。如果您在按 2 之后按 1,则所有按钮均会取消按下。如果您在按 2 之后按 3,按钮 3 和 2 将保持按下状态。一旦按下了两个按钮,您只需按下按钮 1 即可打开锁。
Manao 不知道开头顺序。但他真的很聪明,他会以最佳的方式行事。计算在最坏的情况下他需要按下按钮才能打开锁的次数。
输入
单行包含整数 n (1 ≤ n ≤ 2000) — 锁具有的按钮数量。
输出
在单行中打印 Manao 在最坏情况下按下按钮的次数。
示例
输入 #1
2
输出 #1
3
输入 #2
3
输出 #2
7
注意
考虑第一个测试样本。马纳奥可能会在第一次按下时失败并按下错误的按钮。在这种情况下,他在第二次推动时就已经能够猜到正确的了。他的第三次按下将按下第二个右侧按钮。因此,在最坏的情况下,他只需要推 3 次即可。