eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Намисто 2

Намисто 2

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

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

Якось наш герой ніс у подарунок Аврорі чергове написто і помітив, що у цьому написті присутні бусинки рівно m кольорів, причому є рівно c_i бусинок i-го кольору (1im). Він задумався: "А якщо мені можна було б дарувати лише намиста з такою властивістю, скільки днів мені задобилось би, щоб покорити серце Аврори?" Відповісти на це питання йому виявилось не під силу і він знову звернувся за допомогою до вас.

Вхідні дані

У першому рядку вхідного файлу задано натуральні числа N10^7 і m10000. У другому рядку задано через пропуск натуральні числа c_1, c_2, ..., c_m. Гарантується, що c_1+c_2+...+c_m=N.

Вихідні дані

У єдиний рядок вихідного файлу виведіть кількість способів розфарбувати намисто з N бусинок у m кольорів так, щоб було рівно c_i бусинок i-го кольору (1im).

Приклад

Вхідні дані #1
3 1
3
Вихідні дані #1
1