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

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

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

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

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

输入格式

第一行一个整数 n n n

输出格式

输出一行,表示方案数。

样例

样例输入 1

3

样例输出 1

2

数据范围与提示

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

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

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

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

加强于原题