Alphabet Soup

Peter is having lunch at home. Unfortunately for him, today’s meal is soup. As Peter’s mother is aware that he doesn’t like it very much, she has cooked a special soup using pasta pieces shaped like letters from the alphabet, numbers and other characters. She has a special knife with which she can prepare an unlimited supply of pasta pieces that may come in S different forms. The soup always has P pasta pieces in it, and is so thick that the pieces never move.

Despite her efforts, Peter is still not happy with today’s menu and asks how many days in his life he will have to eat soup. His mother promises him that she will prepare a different soup every day, and that on no day will the dish contain the same shapes in all positions as any soup dish previously served. However, the number P of pasta pieces, as well as the positions in which pieces float, will remain the same every day. Peter is not easily fooled (or so he thinks), and he cleverly realizes that this can still make him eat soup for ages. In an attempt to reduce the number of configurations, he tells his mother he will not accept any dish which can be obtained by rotating one of the configurations previously seen.

Figure 1: Top view of Peter’s dish

Consider the dish as a circle of radius 2 centered at the origin. All the symbols will be floating in the soup at a given angle (in millidegrees) at distance 1 from the origin. Two plates are considered equal if you can perform a rotation of one of the dishes about its center so that the positions of the symbols, as well as the symbols themselves, are the same in both.

Your program will be given the number of possible symbols Peter’s mother has available, and the angles determining the location of each of the pasta pieces (measured clockwise in millidegrees). Write a program that returns the number of possible plates Peter’s mother can prepare. As this number can be very large, output the number modulo 100, 000, 007, which is prime.

The first line of input in each test case contains two numbers: S (2 ≤ S ≤ 1, 000), the number of symbols Peter’s mother can use; and P (P > 0), the number of pasta pieces floating in the soup. Each of the next P lines contain the angle A (0 ≤ A < 360, 000) of one of the P pieces (measured clockwise in millidegrees). All angles will be different.

Different tests cases are separated by a blank line. After the last test case there is a line with S = P = −1.

For each test case output a single integer in a line by itself, the number of different plates Peter’s mother can cook modulo 100, 000, 007.