The fan sector of the stadium consists of \textbf{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 \textbf{K} fans are going to visit the next football game. For each fan \textbf{i}, you are given his height \textbf{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 \textbf{1} to \textbf{N}. A fan assigned to the row \textbf{i} and whose height is \textbf{h_1} will not block the view for a fan assigned to the row \textbf{j} and whose height is \textbf{h_2} if at least one of the two conditions is true: \begin{enumerate} \item \textbf{i} > \textbf{j}; \item \textbf{i + h_1} < \textbf{j + h_2}. \end{enumerate} 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 \textbf{1000200013}. Two setups are different if at least one fan stands in a different place. \InputFile The first line of the input contains two integers \textbf{N} and \textbf{K} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{K} ≤ \textbf{10}, \textbf{K} ≤ \textbf{N}) separated by space: the number of rows and the number of fans, respectively. The next line holds \textbf{K} integers: \textbf{i}-th number describes the height \textbf{h_i} (\textbf{1} ≤ \textbf{h_i} ≤ \textbf{1000}) of the fan number \textbf{i}. \OutputFile Output a single integer: the number of good setups for the given number of rows and given fans modulo \textbf{1000200013}.