#6089. 小 Y 的背包计数问题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Idvzchuscvol

题目描述

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

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

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

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

输入格式

第一行一个整数 n

输出格式

输出一行,表示方案数。

样例

样例输入 1

3

样例输出 1

2

数据范围与提示

对于 10\% 的数据,满足 n\le 10

对于 30\% 的数据,满足 n\le 1000

对于 50\% 的数据,满足 n \le 10^4

对于 100\% 的数据,满足 n \le 10^5

加强于原题