A cashier wants to split N identical coins into one or more stacks. Each stack must hold at least one coin, and the stacks are unlabeled, so only the multiset of stack sizes matters (for example, splitting 4 coins as 3+1 is the same as 1+3).
Count the number of distinct ways to split N coins into stacks. If N is 0, there is exactly one way: no stacks at all.
Input format
A single line: the integer N.
Output format
A single integer: the number of distinct partitions of N.
Constraints
- 0 <= N <= 40