Problem H
How to Paint?

Being a Pokenom trainer is very stressful. You always need to take good care of all your Pokenoms and always be prepared to battle other Pokenom trainers.

To cope with the stressful life, Bash learns to paint in his free time. Today Bash is working on his masterpiece: ‘The two staircases’.

The painting is divided into a grid with $M$ rows and $N$ columns. Rows and columns are numbered starting from $1$, from bottom to top and from left to right, respectively. Let $(i, j)$ denote the cell at the $i$-th row and $j$-th column.

Bash colors each cell red or blue, such that the bottom part forms a blue ‘staircase’ and the top part forms a red ‘inverted staircase’. More formally, Bash’s picture has the following properties:

• For every column $i$ $(1 \leq i \leq N)$, there exists two integers $b_{i}, r_{i}$ satisfying:

  • $0 \leq b_{i}, 0 \leq r_{i}, b_{i} + r_{i} \leq M$.

  • $b_{i}$ bottommost cells (i.e, cells $(1, i), (2, i), \ldots , (b_{i}, i)$) are blue.

  • $r_{i}$ topmost cells (i.e, cells $(M, i), (M - 1, i), \ldots , (M - r_{i} + 1, i)$) are red.

  • All other cells are not painted.

• $M \geq b_{1} \geq b_{2} \geq \ldots \geq b_{N} \geq 0$.

• $0 \leq r_{1} \leq r_{2} \leq \ldots \leq r_{N} \leq M$.

Hence, Bash’s picture can be uniquely determined by two sequences $b = (b_{1}, b_{2}, \ldots , b_{N})$ and $r = (r_{1}, r_{2}, \ldots r_{N})$. This is an example of a valid picture with $M=5$, $N=4$, $b = (4, 2, 2, 0)$ and $r = (1, 1, 2, 3)$:

Below are three examples of invalid pictures:

After few hours of hard work, Bash has finished his painting, and shows his best friend Cee. The picture satisfies all the above properties, with parameters $b = (c_{1}, c_{2}, \ldots , c_{N})$ and $r = (M - c_{1}, M - c_{2}, \ldots M - c_{N})$. No cells are left unpainted in this picture.

Cee wants to know step-by-step of how Bash created such beautiful painting. Bash can not remember the order which he painted the cells, but Bash remembers that he always followed these rules:

• Bash starts with an empty picture.

• First, Bash paints the bottom-left cell $(1, 1)$ blue and the top-right cell $(M, N)$ red.

• In each step, Bash chooses some unpainted cell, paints it either red or blue, such that the picture after this step satisfies all the above properties.

• The process stops when the picture is completed.

Cee tries to follow Bash’s rules to replicate the painting. But first Cee wants to know how many ways Cee can create the painting. Two ways are considered different if there exists a step where the painted cells are different.

Represent the result as $100\, 003^ X \times Y$, where $Y$ is not divisible by $100\, 003$, and output $X \; Y_ m$ where $Y_ m$ is the result of $Y \bmod 100\, 003$.

Input

• Line $1$: Two integers $N$ and $M$ $(1 \le M, N \le 1\, 000)$.

• Line $2$: $N$ integers $c_1, c_2, \cdots , c_ N$ $(M \ge c_1 \ge c_2 \ge \cdots \ge c_ n \ge 0)$ describes the blue parameters in Bash’s final picture (see description above).

Output

Two integers $X$ and $Y_ m$ as described above.

Sample clarification

Bash’s pictures in $2$ sample cases:

3 3
3 2 1

0 672

4 4
4 3 1 0

0 16296