L. Разбиения множества

Множество $\{1, 2, \dots, N\}$ надо разбить на непустые непересекающиеся части. Перечислите все такие разбиения.

Чтобы каждое разбиение записывалось единственным образом, используется такая запись: для каждого элемента выводится номер его части, причём части нумеруются в порядке появления. Первый элемент всегда в части 1; элемент может попасть либо в одну из уже начатых частей, либо в новую — с номером на единицу больше наибольшего использованного.

Например, при $N = 3$ записи такие: 111, 112, 121, 122, 123 — всего пять, и это число Белла.

Выведите все записи в лексикографическом порядке, каждую без пробелов.

Одна строка содержит число $N$ ($1 \le N \le 9$).

Все записи разбиений, по одной на строку.