题目描述

训练两年半的坤坤养了一只会魔法的鸡。这只鸡有以下特殊能力：

1. 魔法产蛋：可以立即生出一个蛋并瞬间孵化成新鸡（每只鸡一生只能使用一次该能力）。
2. 体重限制：新生鸡的体重 ≤ 原鸡体重的一半。
3. 魔力消失：当鸡的体重为 1 时，无法再使用魔法。

给定初始鸡的体重 n ，经过若干次魔法繁殖后，会生成一个体重序列。例如：

• 初始体重 4 ，可能的序列为 [4] 、 [4, 2] 、 [4, 2, 1] 。

问题：对于给定的初始体重 n ，计算所有可能的不同序列的数量。

输入格式

一行，一个正整数表示初始的鸡的体重，n (1 ≤ n ≤ 500) 。

输出格式

一个整数，表示序列的数量

4

4