Послідовність нулів

Обмеження: 2 сек., 256 МіБ

У вас є послідовність з $n$ нулів.

Вам необхідно замінити $k$ з них додатними числами $a_i$.

Причому для кожного числа $c$, що міститься в послідовності, має бути принаймні $c$ нулів зліва та принаймні $c$ нулів справа від нього. Ці нулі мають йти послідовно одразу до та після числа $c$. Тобто, частина послідовності має виглядати так: $..., 0, 0, ..., 0, c, 0, 0, ..., 0, ...$

Вам необхідно знайти кількість різних таких послідовностей за модулем простого числа 1234567891.

Вхідні дані

Перший рядок містить два цілих числа $n$ та $k$ — кількість нулів у початковій послідовності та кількість замін.

Другий рядок містить $k$ цілих чисел $a_i$.

Вихідні дані

Виведіть ціле число — кількість різних послідовностей за модулем 1234567891.

Обмеження

$1 \le n \le 10^3$,

$1 \le k \le 100$,

$1 \le a_i \le 100$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
10 3 1 2 1	12