eolymp
bolt
Try our new interface for solving problems
Problems

Ожерелье 2

Ожерелье 2

Time limit 1 second
Memory limit 256 MiB

Тяжелые времена настали для женихов города N. Теперь, чтобы жениться на девушке, молодому человеку надо подарить ей все возможные ожерелья из N бусинок, где каждая из бусинок может быть покрашена в один из N цветов. При этом, как и раньше, если какое-то ожерелье уже подарено, а другое ожерелье можно получить из него поворотом или переворотом, то они считаются одинаковыми и второе дарить не надо. Наш герой Анонимус снова влюбился. На этот раз в прекрасную Аврору. И он хочет на ней жениться. С тех пор как он обращался к вам за помощью в первый раз, он много занимался математикой и программированием и теперь для него не составляет труда найти сколько дней он будет дарить ожерелья. Но возникла другая проблема.

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

Input data

В первой строке входного файла заданы натуральные числа N10^7 и m10000. Во второй строке заданы через пробел натуральные числа c_1, c_2, ..., c_m. Гарантируется, что c_1+c_2+...+c_m=N.

Output data

В единственную строку выходного файла выведите количество способов раскрасить ожерелье из N бусинок в m цветов так, чтобы было ровно c_i бусинок i-го цвета (1im).

Examples

Input example #1
3 1
3
Output example #1
1