Свято дівчат

На честь святкування $100$-річчя Цінхуа університету $n$ дівчат планують влаштувати вечірку. Вони — експертки у співі й танцях та обожнюють виступати у групах. За їхнім нинішнім планом буде сцена та ряд сидінь. Коли група дівчат має співати або танцювати на сцені, вони встають зі своїх місць і йдуть на сцену. Після виступу вони повертаються на свої місця (вони не міняються місцями, бо у кожної на місці багато особистих речей).

Вони хочуть, щоб цей процес виглядав ефектно, тому для кожного виступу місця акторок мають бути послідовними. Наприклад, якщо є $4$ дівчини, і на сцену виходять дівчини $1$, $2$ та $4$, то вони не можуть сидіти у порядку $1$-$2$-$3$-$4$, бо коли дівчата $1$, $2$ та $4$ встануть, буде дивно бачити не акторку (дівчину $3$) між $2$ та $4$.

Як уже згадувалося, вони дуже добре співають і танцюють, тож вигадали багато різних комбінацій. Тепер їх трохи турбує: чи є спосіб розсадити всіх дівчат так, щоб виконувалася описана вимога (тобто для кожної комбінації місця акторок є послідовними)?

Як пристойний програміст, ви вирішуєте (точніше, вас просили) написати програму, яка може підрахувати кількість можливих розсаджень. Оскільки дівчата постійно придумують нові комбінації, ваша програма повинна зчитувати нові комбінації й відповідно оновлювати відповідь. Якщо можливих варіантів небагато (тобто не більше $k$ рішень), програма має вивести всі ці варіанти.