A293.坤坤的魔力鸡

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

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

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

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

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

一行，一个正整数 表示初始的鸡的体重，n（n≤500）。

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

对于 n = 6，所有可能的序列为：

1. [6]
2. [6, 1]
3. [6, 2]
4. [6, 2, 1]
5. [6, 3]
6. [6, 3, 1]