Necklace 2
In the city of N, times have become challenging for suitors. To win a girl's hand in marriage, a young man must present her with every possible necklace made from N beads, where each bead can be one of N colors. Furthermore, if a necklace can be transformed into another by rotation or reflection, they are considered identical, and only one needs to be given. Our hero, Anonymous, has fallen in love once more, this time with the enchanting Aurora, and he wishes to marry her. Since first seeking your assistance, he has immersed himself in mathematics and programming, and now he easily calculates how many days it will take to present all the necklaces. However, a new challenge has emerged.
One day, while carrying a necklace as a gift for Aurora, he noticed that it featured exactly m different colors of beads, with precisely c_i beads of the i-th color (1 ≤ i ≤ m). He pondered: "If I could only give necklaces with this specific property, how many days would it take to win Aurora's heart?" Unable to solve this puzzle, he once again seeks your expertise.
Input
The first line of the input contains the natural numbers N ≤ 10^7 and m ≤ 10000. The second line lists the natural numbers c_1, c_2, ..., c_m, separated by spaces. It is guaranteed that c_1+c_2+...+c_m=N.
Output
Output a single line with the number of ways to color a necklace of N beads using m colors such that there are exactly c_i beads of the i-th color (1 ≤ i ≤ m).