771028 - 合法的数列

通过次数

14

提交次数

32

时间限制 : 1 秒
内存限制 : 128 MB

给出自然数n,要求按如下方式构造数列: 1.只有一个数字n的数列是一个合法的数列。 2.在一个合法的数列的末尾加入一个自然数,但是这个自然数不能超过该数列最后一项的一半,可以得到一个新的合法数列。请你求出,一共有多少个合法的数列。两个合法数列a,b不同当且仅当两数列长度不同或存在一个正整数i≤|a|,使得ai≠bi。

输入

输入只有一行一个整数,表示n。

输出

输出一行一个整数,表示合法的数列个数。

样例

输入

6

输出

6

提示

样例1解释 满足条件的数列为: 6; 6,1; 6,2; 6,3; 6,2,1; 6,3,1; 数据规模与约定 对于全部的测试点,保证1≤n≤10^3。