402901: GYM100942 B High-Speed Pedestrian walkway 1.0

Construction of the High-Speed Pedestrian walkway that connects two capitals was ordered by the Department for Innovation. But nobody knew how to construct it. Fortunately, there is a unique plant in the city for pedestrian walkway components production.

The plant produces m types of tiles – rectangles of 1 × k cm, available in c_k different colors,1 ≤ k ≤ m.

The pedestrian walkway consists of a rectangular segments of 2 × n cm. Each segment in the construction is assembled with tiles of above mentioned kind. Since the completion of the pedestrian walkway will be accepted by the top Heads, so it was decided to construct it from unique segments, in other words, all segments should be different in way of tiling.

Now it is important to find out what the maximum possible number of unique segments is.

The first line contains integers n and m (1 ≤ n ≤ 10¹⁸,  1 ≤ m ≤ 9) — length of a segment and number of tiles' kinds. The second line contains space separated m non-negative integers c₁, c₂, ..., c_m, at least one of which is different from zero. All integers do not exceed 10⁹.

Output the required number modulo (10⁹ + 9).

3 3
0 1 2

7 

2 4
0 0 1 0

0