Accessory Combinations: Calculating Bell Numbers

You are given a single integer n representing the number of items. The task is to compute the n-th Bell number. The Bell number, denoted as \(B_n\), is the number of ways to partition a set with \(n\) elements. This problem models a real-world scenario where each car must have at least one accessory, and each configuration corresponds to a distinct partitioning of the accessories.

The Bell numbers can be defined recursively using the relation:

[ B_{n+1} = \sum_{k=0}^{n} \binom{n}{k} B_{k}, \quad \text{with } B_0=1. ]

In this problem, however, you can use an iterative dynamic programming approach to compute the Bell number efficiently.

inputFormat

The input consists of a single integer \(n\) read from standard input. \(n\) represents the number of elements and satisfies \(1 \leq n \leq 15\) (for the scope of this problem).

outputFormat

Output the n-th Bell number to standard output.

1

1