Description

有一个数组，初始时数组中只有一个元素 $0$，现进行下述操作 $k$ 次:

1. 选择数组中随机某个位置到结尾的一段，复制并拼接到结尾；
2. 将拼接到结尾的这一段中的每个元素加 $1$。

注: 选择的段的长度不能为 $0$，也就是说，每次操作至少会复制一个元素。

如数组 $[0,1,2,3,4,5,6,7]$：

• 随机选择的位置为 $4$，则将数组中从下标 $4$ 开始到结尾的元素复制并拼接到结尾，得到$[0,1,2,3,4,5,6,7,4,5,6,7]$。
• 然后将拼接到结尾的段中的每个元素加 $1$，得到$[0,1,2,3,4,5,6,7,5,6,7,8]$

现给定操作次数 $k$ 的值，求 $k$ 次操作后数组中最后一个元素的值是多少。

Input Format

输入一个整数 $k$，表示操作次数。

Output Format

输出一个整数，表示答案。

2

2

Hint

对 $100\%$ 的数据，$0 \le k \le 10^{9}$。