Necklace 2#2436
It has become a challenging time for the suitors of the city of . To marry a girl, a young man must present her with every possible necklace made of beads, each bead colored with one of colors. If two necklaces can be transformed into one another by rotation or reflection, they are considered identical, and only one must be given. Our hero, Anonymous, has fallen in love again, this time with the beautiful Aurora, and he wishes to marry her. Since first asking for your help, he has practiced mathematics and programming a lot, and now he can easily figure out how many days it would take to give all such necklaces. However, a new challenge has appeared.
The first line of the input contains natural numbers N \leq 10^7 and m \leq 10000. The second line contains natural numbers c_1, c_2, \dots, c_m separated by spaces. It is guaranteed that c_1 + c_2 + \dots + c_m = N.
Output a single line with the number of ways to color a necklace of beads with colors so that there are exactly c_i beads of the -th color (1 \leq i \leq m).
Example 1