Alphabet Soup

Peter is having lunch at home, and unfortunately for him today's meal is soup. Knowing that Peter does not like it very much, his mother has cooked a special soup using pasta pieces shaped like letters of the alphabet, digits, and other characters. With a special knife she can prepare an unlimited supply of pasta pieces, which come in $S$ different shapes. Each bowl of soup always contains exactly $P$ pasta pieces, and the soup is so thick that the pieces never move.

Despite her effort, Peter is still unhappy with today's menu and asks how many days of his life he will have to eat soup. His mother promises to prepare a different soup every day: on no day will the dish contain the same shapes in all positions as any soup served before. However, the number $P$ of pasta pieces and the positions in which they float stay the same every day. Thinking himself clever, Peter realizes this could still make him eat soup for ages, so to reduce the number of configurations he declares that he will also refuse any dish that can be obtained by rotating one of the configurations already seen.

Figure 1: Top view of Peter's dish

Consider the dish as a circle of radius $2$ centered at the origin. Every symbol floats in the soup at distance $1$ from the origin, at a given angle measured in millidegrees. Two plates are considered equal if you can rotate one of the dishes about its center so that both the positions of the symbols and the symbols themselves match in the two dishes.

Your program is given the number $S$ of symbols Peter's mother has available and the $P$ angles (measured clockwise in millidegrees) that determine the location of each pasta piece. Compute the number of different plates Peter's mother can prepare. As this number can be very large, output it modulo $100000007$, which is prime.

The input contains several test cases.

The first line of each test case has two integers $S$ ($2 \le S \le 1000$), the number of available shapes, and $P$ ($P > 0$), the number of pasta pieces. Each of the next $P$ lines contains one integer $A$ ($0 \le A < 360000$), the angle of a piece measured clockwise in millidegrees. All $P$ angles are distinct.

Consecutive test cases are separated by a blank line. A line containing $S = P = -1$ (that is, the two values -1 -1) follows the last test case and ends the input.

For each test case, output a single line with the number of distinct bowls Peter's mother can prepare, taken modulo $100000007$.