Есть полоска, разделенная на $$$n$$$ клеток, пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Изначально все клетки являются бесцветными.

Мы проводим $$$(n-1)$$$ операцию; номера операций начинаются с $$$1$$$. В ходе $$$i$$$-й операции мы выбираем любое количество подряд идущих клеток и красим их в цвет $$$i$$$. Если какие-то клетки ранее были покрашены, их цвет меняется на новый.

Раскраской называется последовательность цветов клеток $$$c_1, c_2, \dots, c_n$$$, где $$$c_i$$$ — цвет $$$i$$$-й клетки. Назовем раскраску красивой, если для нее выполняются следующие условия:

• раскраску можно получить путем применения $$$(n-1)$$$ операций, описанных выше;
• ни одна клетка в раскраске не является бесцветной;
• для каждого цвета от $$$1$$$ до $$$n-1$$$ существует хотя бы одна клетка с этим цветом.

Посчитайте количество красивых раскрасок. Две раскраски являются различными, если цвет хотя бы одной клетки в этих раскрасках отличается.