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