Алфавитный суп
Питер обедает дома. К несчастью для него, сегодняшней едой будет суп. Поскольку мать Питера знает, что ему это не очень нравится, она приготовила специальный суп, используя кусочки макарон в форме букв алфавита, цифр и других символов. У нее есть специальный нож, с помощью которого она может приготовить неограниченное количество кусочков пасты, которые могут быть s разных форм. В супе всегда имеются p кусочков пасты, и он такой густой, что кусочки никогда не двигаются.
Несмотря на ее усилия, Питер все еще недоволен сегодняшним меню и спрашивает, сколько дней в его жизни ему придется есть суп. Его мать обещает ему, что каждый день будет готовить новый суп, и что ни один день блюдо не будет содержать те же формы во всех положениях, что и любое суповое блюдо, подаваемое ранее. Однако количество p кусочков пасты, а также позиции, в которых они плавают, будут оставаться неизменными каждый день. Питера нелегко одурачить (по крайней мере, он так думает), и он ловко понимает, что это все еще может заставить его есть суп целую вечность. Пытаясь уменьшить количество конфигураций, он говорит своей матери, что не примет ни одно блюдо, которое можно получить, повернув одну из ранее увиденных конфигураций.
Рисунок 1: Вид сверху на блюдо Петра
Рассмотрим тарелку как круг радиуса 2 с центром в начале координат. Все символы будут плавать в супе под заданным углом (в миллиградусах) на расстоянии 1 от начала координат. Две тарелки считаются равными, если можно совершить вращение одной из тарелок вокруг ее центра так, чтобы положения символов, как и сами символы, были одинаковыми в обеих.
Ваша программа получит количество возможных символов, имеющихся в распоряжении матери Питера, и углы, определяющие расположение каждого из кусочков макарон (измеряется по часовой стрелке в миллиградусах). Напишите программу, которая возвращает количество возможных тарелок, которые может приготовить мать Питера. Поскольку это число может быть очень большим, выведите число по модулю 10^8 + 7, которое является простым.
Входные данные
Первая строка в каждом тесте содержит два числа: s (2 ≤ s ≤ 1000) - количество символов, которые может использовать мать Питера; и p (p > 0) - количество кусочков пасты, плавающих в супе. Каждая из следующих p строк содержит угол a (0 ≤ a < 360000) одной из p частей (измеренный по часовой стрелке). в миллиградусах). Все углы разные.
Тесты разделены между собой пустой строкой. После последнего теста идет строка с s = p = -1.
Выходные данные
Для каждого теста выведите в отдельной строке одно целое число - количество разных тарелок, которые мать Питера может приготовить по модулю 10^8 + 7.