Alchemy

cubelover combines ingredients in this order.

1. Fill the cauldron with slime fluid and heat it over a fire.
2. Add one ingredient, then stir slowly four times clockwise and twice counterclockwise.
3. Offer a prayer facing east.
4. Repeat steps 2 and 3 until every ingredient is in.
5. Put out the fire and let the cauldron cool for 17 hours to finish the product.

A product made in this cauldron is decided without regard to the order the ingredients went in. If the ingredients differ, the product always differs too. The quality of a product equals the product of the qualities of all the ingredients that went in.

For example, suppose you use a lizard tail of quality $2$ and a fairy wing of quality $3$. If adding the lizard tail, the fairy wing, and the lizard tail in that order yields apple juice, the quality of that apple juice is $2 \times 3 \times 2 = 12$. The order has no effect on the product, so adding the fairy wing, the lizard tail, and the lizard tail yields the same apple juice.

Today cubelover combines $n$ ingredients. The warehouse holds $m$ kinds of ingredients whose qualities are $a_1, a_2, \dots, a_m$, all different, and he may add the same kind any number of times. Two products are the same exactly when they use the same count of every kind. There are so many products that cubelover could not count them himself. Find the sum of the qualities of every product he can make.

The first line has two integers $n$ and $m$ separated by a space. ($1 \le n \le 10^9$, $1 \le m \le 10^3$)

The second line has $a_1, a_2, \dots, a_m$ separated by spaces. ($1 \le a_i \le 10^9$, all $a_i$ are different)

Print on the first line the sum of the qualities of every product he can make, modulo $1000000007$.