eolymp
bolt
Try our new interface for solving problems
Məsələlər

Fans Placement

Fans Placement

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 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.

Giriş verilənləri

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.

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3 2
1 2
Çıxış verilənləri #1
4
Mənbə Yandex.Algorithm, Online Round 3, July 22, 2013