eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Fans Placement

Fans Placement

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

The fan sector of the stadium consists of N rows of seats placed one behind another on the stairs. To prevent crowds during football games, the stadium administration set up only one seat in each row.

It is known that K fans are going to visit the next football game. For each fan i, you are given his height h_i. Each fan will cheer for his team and therefore will stand still all game long. All fans obey the rules, so they will not move from their places during the game.

A nice ticket seller Billy decided to distribute tickets to fan sector of the stadium in such way that each fan will comfortably see the game. The requirements for such setup (that is also called a good setup) are below.

Assume that the rows on the stadium are numbered from the bottom to the top of the stadium from 1 to N. A fan assigned to the row i and whose height is h_1 will not block the view for a fan assigned to the row j and whose height is h_2 if at least one of the two conditions is true:

  1. i > j;

  2. i + h_1 < j + h_2.

The job of a ticket seller is really boring, so Billy decided to find out how many good setups exist for the given set of fans. Surely, it is impossible to assign one seat to multiple fans or one fan to multiple seats. Unfortunately, Billy doesn't have access to a computer right now, so he asked you to calculate the number of good setups modulo 1000200013. Two setups are different if at least one fan stands in a different place.

Входные данные

The first line of the input contains two integers N and K (1N1000, 1K10, KN) separated by space: the number of rows and the number of fans, respectively. The next line holds K integers: i-th number describes the height h_i (1h_i1000) of the fan number i.

Выходные данные

Output a single integer: the number of good setups for the given number of rows and given fans modulo 1000200013.

Пример

Входные данные #1
3 2
1 2
Выходные данные #1
4
Источник Yandex.Algorithm, Online Round 3, July 22, 2013