Ожерелье 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).