「小 Y 的背包计数问题」

传统 1000 ms 256 MiB

$759$ 通过 $1702$ 提交

题目描述

小 Y 有一个大小为 $n$ 的背包，并且小 Y 有 $n$ 种物品。

对于第 $i$ 种物品，共有 $i$ 个可以使用，并且对于每一个 $i$ 物品，体积均为 $i$。

求小 Y 把该背装满的方案数为多少，答案对于 $23333333$ 取模。

定义两种不同的方案为：当且仅当至少存在一种物品的使用数量不同。

输入格式

第一行一个整数 $n$。

输出格式

输出一行，表示方案数。

样例

输入

3

输出

2

数据范围与提示

• 对于 $10\%$ 的数据，满足 $n \leq 10$
• 对于 $30\%$ 的数据，满足 $n \leq 1000$
• 对于 $50\%$ 的数据，满足 $n \leq 10^4$
• 对于 $100\%$ 的数据，满足 $n \leq 10^5$

加强于原题