Фарбування

На заняттях шкільного гуртка Євгенію навчили виготовляти з паперу моделі правильних многогранників (платонових тіл) і напівправильних многогранників (архіме­дових тіл). Вона запам’ятала такі означення:

1. Платоновим тілом називають (опуклий) много­гранник, у якому всі грані — правильні однакові многокутники, а многогранні кути при всіх вершинах однакові.

2. Архімедовим тілом називають (опуклий) много­гранник, у якому всі грані — правильні многокутники (не обов’язково з однаковою кількістю сторін), а много­гранні кути при всіх вершинах однакові. При цьому є щонайменше дві різні грані.

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

Кілька моделей многогранників Євгенія виготовила для оформлення кабінету математики і прихопила додому, щоб вразити своїх рідних. Враження, звичайно, вона справила. Але, вечеряючи, недогледіла, як молодша сестра Марічка взялася розфар­бовувати грані: кожну грань лише однією фарбою. При цьому кілька граней могли бути й одного кольору, навіть якщо вони були суміжними, тобто мали спільне ребро. Євгенія задумалась… Її, як майбутнього математика, зацікавило питання: скількома способами можна розфарбувати грані тіла Архімеда, маючи певну кількість фарб, з точністю до симетрій — рухів простору, що залишають многогранник на тому самому місці. Інакше кажучи, коли не розрізняють розфарбування, отримані одне з іншого взаємно одно­знач­ним відображенням граней при збереженні відношення суміжності.

Знаючи все про суміжність чи несуміжність граней тіла Платона чи Архімеда, визначте кількість розфарбувань цього многогранника для даної кількості кольорів.

Вхідні дані

У першому рядку вказано кількість фарб m (m < 6). Кількість вхідних рядків на 1 перевищує кількість граней многогранника і менша від 24. Усі грані многогранника занумеровано послідовними натуральними числами, починаючи з 1. j-й рядок (j > 1) містить (невпорядкований) перелік номерів граней, суміжних з гранню j – 1.

Вхідні дані гарантують, що кількість симетрій многогранника не перевищує 120.

Вихідні дані

Вивести кількість розфарбувань граней тіла, виконаних за допомогою m фарб і різних з точністю до симетрій многогранника.

Приклади