Neo was bored of always living in three-dimensional space. In order to cope with his boredom, he learned how to lucid dream, where he was able to recreate his own world with ~K~-dimensions and conveniently place himself in any corner of his world. His world can be imagined as a ~K~-dimensional grid where each dimension is located on a unique plane with a grid size of length ~l_i~. The drawback of Neo's dream world is that when he wakes up, he forgets most of the properties he used in order to create the world.

He is only able to remember ~W~, the number of different shortest paths there are from his starting corner to the furthest point of his starting corner, within his ~K~-dimensional grid, and a list of ~N~ numbers, ~l_1, l_2, \dots, l_N~, which are possible side lengths he chose for each dimensions' grid length. A single value of ~l_i~ may only correspond to the length of 1 dimensions' grid size.

Can you help Neo determine ~K~, the dimension of the world he created and ~l_1, l_2, \dots, l_N~, the length of each grid size?

Note: Neo will not create a world less than 2 dimensions.

Constraints

For all subtasks:

~0 \le W < 10^9 + 7~

~K \le N~

~2 \le l_i \le 10~

Subtask 1 [10%]

~K = 2~

~2 \le N \le 5~

Subtask 2 [20%]

~K = 3~

~2 \le N \le 10~

Subtask 3 [70%]

~2 \le N \le 20~

Input

First line: ~W~, the number of different shortest paths from the corner located at the origin to its opposite corner modulo ~10^9 + 7~.

Second line: ~N~, the number of possible side lengths to construct the ~K~-dimensional grid.

Third line: ~N~ space-separated integers, ~l_1, l_2, \dots, l_N~, the list of possible side lengths.

Output

On the first line, print ~K~, the dimension of the world.

On the second line, print ~K~ numbers in non-decreasing order, the lengths of each side.

If there is no solution print -1, otherwise it is guaranteed that there is only 1 solution.

Sample Input 1

6
3
2 3 2

Sample Output 1

2
2 2

Explanation for Sample Output 1

A 2-dimensional grid of length ~2 \cdot 2~ will create a grid that has ~6~ different paths. The 6 different paths are (where R is right and D is down):

RRDD
RDRD
RDDR
DRRD
DRDR
DDRR