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

Сектор болельщиков на стадионе состоит из 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.

Примеры