You probably know the game where two players in turns take 1 to 3 stones from a
pile. Looses the one who takes the last stone. We'll generalize this well known game.
Assume that both of the players can take not 1, 2 or 3 stones, but
*k*_{1}, *k*_{2}, …, *k*_{m} ones.
Again we'll be interested in one question: who wins in the perfect game. It is guaranteed that it is possible to make next move irrespective to already made moves.

### Input

The first line contains two integers: *n* and *m* (1 ≤ *n* ≤ 10000; 1 ≤ *m* ≤ 50) — they are an initial amount of stones in the pile and an amount of numbers *k*_{1}, …, *k*_{m}. The
second line consists of the numbers *k*_{1}, …, *k*_{m}, separated with a space (1 ≤ *k*_{i} ≤ *n*).

### Output

Output 1, if the first player (the first to take stones) wins in a perfect game.
Otherwise, output 2.

### Sample

**Problem Author: **Anton Botov

**Problem Source: **The 3rd high school children programming contest, USU, Yekaterinburg, Russia, March 4, 2001