Намисто 2#2436
Настали складні часи для наречених міста . Щоб одружитися з дівчиною, юнак повинен подарувати їй всі можливі намиста, що складаються з намистин, кожна з яких пофарбована в один із кольорів. Якщо два намиста можна перетворити одне в одне обертанням або віддзеркаленням, вони вважаються однаковими, і дарувати потрібно лише одне. Наш герой, Анонім, знову закохався — цього разу у прекрасну Аврору, і бажає одружитися з нею. З часу першого звернення до вас по допомогу він багато вправлявся у математиці та програмуванні, тож тепер легко може підрахувати, скільки днів йому знадобиться, щоб подарувати всі такі намиста. Однак з'явилося нове випробування.
У першому рядку вхідних даних записано натуральні числа N \leq 10^7 та m \leq 10000. У другому рядку записано натуральних чисел c_1, c_2, \dots, c_m, розділених пропусками. Гарантовано, що c_1 + c_2 + \dots + c_m = N.
Виведіть в одному рядку кількість способів розфарбувати намисто з намистин у кольорів так, щоб у ньому було рівно по c_i намистин -го кольору (1 \leq i \leq m).
Приклад 1