A group of friends was given a necklace. The necklace is a circular nylon wire with gold beads of various weights glued on. They want to cut the wire into segments so that everybody gets one segment, every person gets the same amount of gold, no bead is cut, and no gold is left over. They wonder whether such a split is possible.

-----Input-----
The first line contains two integers $k$ and $n$ where $k$ is the number of friends and $n$ is the number of beads on the necklace. The next line contains $n$ positive integers—the weights of the beads in the order they occur on the necklace. You may assume $k\leq 1000000$, $n\leq 10000000$, and that bead weights are each $\leq 1000000000$.

-----Output-----
The output consists of a single line consisting of the string YES if the necklace can be split into $k$ segments of equal weight, and the string NO otherwise.

-----Examples-----
Sample Input:
3 4
1 2 2 1 
Sample Output:
YES

Difficulty: competition

Starter code:

Solutions: