Розміщення вентиляторів

Сектор для вболівальників на стадіоні складається з N рядів сидінь, розташованих один за одним на сходах. Щоб уникнути натовпу під час футбольних матчів, адміністрація стадіону встановила лише одне місце в кожному ряді.

Відомо, що K вболівальників збираються відвідати наступний футбольний матч. Для кожного вболівальника i відома його висота h_i. Кожен вболівальник буде підтримувати свою команду і тому стоятиме на місці протягом усього матчу. Усі вболівальники дотримуються правил, тому вони не будуть рухатися зі своїх місць під час гри.

Добрий продавець квитків Біллі вирішив розподілити квитки в секторі для вболівальників стадіону так, щоб кожен вболівальник міг комфортно бачити гру. Вимоги до такої розстановки (яка також називається хорошою розстановкою) наведені нижче.

Припустимо, що ряди на стадіоні пронумеровані знизу вгору від 1 до N. Вболівальник, призначений до ряду i і чия висота h_1, не буде заважати огляду вболівальнику, призначеному до ряду j і чия висота h_2, якщо виконується хоча б одна з двох умов:

1. i > j;

2. i + h_1 < j + h_2.

Робота продавця квитків дуже нудна, тому Біллі вирішив дізнатися, скільки хороших розстановок існує для даного набору вболівальників. Звісно, неможливо призначити одне місце кільком вболівальникам або одного вболівальника на кілька місць. На жаль, зараз у Біллі немає доступу до комп'ютера, тому він попросив вас обчислити кількість хороших розстановок за модулем 1000200013. Дві розстановки відрізняються, якщо хоча б один вболівальник стоїть на іншому місці.

Вхідні дані

У першому рядку введення містяться два цілі числа N та K (1 ≤ N ≤ 1000, 1 ≤ K ≤ 10, K ≤ N), розділені пробілом: кількість рядів та кількість вболівальників відповідно. Наступний рядок містить K цілих чисел: i-те число описує висоту h_i (1 ≤ h_i ≤ 1000) вболівальника номер i.

Вихідні дані

Виведіть одне ціле число: кількість хороших розстановок для даної кількості рядів і даних вболівальників за модулем 1000200013.

Приклади