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

Обмеження: 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