Тяжелые времена настали для женихов города \textbf{N}. Теперь, чтобы жениться на девушке, молодому человеку надо подарить ей все возможные ожерелья из \textbf{N} бусинок, где каждая из бусинок может быть покрашена в один из \textbf{N} цветов. При этом, как и раньше, если какое-то ожерелье уже подарено, а другое ожерелье можно получить из него поворотом или переворотом, то они считаются одинаковыми и второе дарить не надо. Наш герой Анонимус снова влюбился. На этот раз в прекрасную Аврору. И он хочет на ней жениться. С тех пор как он обращался к вам за помощью в первый раз, он много занимался математикой и программированием и теперь для него не составляет труда найти сколько дней он будет дарить ожерелья. Но возникла другая проблема. Как-то раз наш герой нес в подарок Авроре очередное ожерелье и заметил, что в этом ожерелье присутствуют бусинки ровно \textbf{m} цветов, причем имеется ровно \textbf{c_i} бусинок \textbf{i}-го цвета (\textbf{1} ≤ \textbf{i} ≤ \textbf{m}). Он задумался: "\textit{А если мне можно было бы дарить только ожерелья с таким свойством, сколько дней мне понадобилось бы, чтобы покорить сердце Авроры?}" Ответить на этот вопрос ему оказалось не под силу и он опять обратился за помощью к вам. \InputFile В первой строке входного файла заданы натуральные числа \textbf{N} ≤ \textbf{10^7} и \textbf{m} ≤ \textbf{10000}. Во второй строке заданы через пробел натуральные числа \textbf{c_1}, \textbf{c_2}, ..., \textbf{c_m}. Гарантируется, что \textbf{c_1}+\textbf{c_2}+...+\textbf{c_m}=\textbf{N}. \OutputFile В единственную строку выходного файла выведите количество способов раскрасить ожерелье из \textbf{N} бусинок в \textbf{m} цветов так, чтобы было ровно \textbf{c_i} бусинок \textbf{i}-го цвета (\textbf{1} ≤ \textbf{i} ≤ \textbf{m}).