Distribution of Colored Balls into Boxes

You are given n distinct colored balls. Your task is to determine the number of ways to distribute these balls into an infinite number of boxes such that no box contains more than one ball of the same color. This is equivalent to partitioning a set of n distinct elements into non-empty subsets.

The answer is given by the Bell number \(B(n)\), which can be computed using the recurrence relation:

[ B(n+1)=\sum_{k=0}^{n} \binom{n}{k} B(k), \quad B(0)=1 ]

Alternatively, a dynamic programming approach can be used to compute \(B(n)\) directly. For example, when \(n=1\), the output is \(1\); when \(n=3\), the output is \(5\); and when \(n=4\), the output is \(15\).

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 20) representing the number of distinct colored balls.

The input is provided via standard input.

outputFormat

Output a single integer which is the Bell number \(B(n)\), i.e., the number of ways to distribute the balls into boxes subject to the given condition.

The output should be printed on a single line to standard output.

1

1