Алфавітний суп
Пітер обідає вдома. На жаль, сьогодні на обід суп. Оскільки мати Пітера знає, що він не дуже любить суп, вона приготувала його особливим чином, використовуючи шматочки макаронів у формі літер алфавіту, цифр та інших символів. У неї є спеціальний ніж, за допомогою якого вона може створити необмежену кількість шматочків пасти, які можуть мати 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.