愚公移山

题目描述

为了让中小学生更好地理解题目，我们可以将背景设定为一个游戏场景。在这个游戏中，玩家需要帮助愚公移山，屏幕上出现 n 个积木，屏幕下方的底盘是二维方格，每个方格恰好能放置一个积木。

积木放置的规则是：底盘由多行多列的方格组成；每一列必须从最左边的一列开始摆放；每列从最下面的方格开始连续摆放积木；底盘至少要放两列；后一列放的积木数至少比前一列多一个。

原图给出 5 个积木的两种摆放方案。用每列从左到右的积木数表示，这两种方案分别是 (1, 4) 和 (2, 3)；每种方案中，所有积木都从各列最下面的方格起连续放置。

玩家需要思考如何将这些积木放置在底盘上，使得所有积木都能够被放置，并且符合规则。玩家可以通过不断尝试和调整来寻找合法的摆放方案，从而完成愚公移山的任务。

现在，请你帮助计算 n 个积木共有多少种摆放方案呢？

输入描述

一行，一个整数 n。

输出描述

一行，一个整数，表示结果。

样例 1

输入：

5

输出：

2

样例 2

输入：

10

输出：

9

样例 3

输入：

99

输出：

409173

数据范围

• 对 40% 的数据保证：1 ≤ n ≤ 25。
• 对 80% 的数据保证：1 ≤ n ≤ 80。
• 对 100% 的数据保证：1 ≤ n ≤ 145。