Some people like to pretend that they are a pharaoh. Or a dolphin. Luka is one such person.

He has built a relief consisting of a long line of columns with nonnegative integer heights. The heights of all columns were initially zero. The relief was built in steps, where in each step Luka would select a **contiguous subsequence of columns with equal heights** and raise all columns in the subsequence, **except** the first and last column, by **one**.

Hundreds of years have passed, and **some of the columns** have been **stolen**. Luka's great-great-…-great-grandson is trying to determine the number of possible reliefs that could have been built by Luka such that the remaining columns' heights match the original relief.

#### Input Specification

The first line of input contains the positive integer , the number of columns in Luka's relief.

The second line of input contains space-separated integers , the column heights. A height of represents a stolen column.

#### Output Specification

The first and only line of output must contain the required number of possible reliefs modulo .

#### Sample Input 1

```
3
-1 2 -1
```

#### Sample Output 1

`0`

#### Sample Input 2

```
3
-1 -1 -1
```

#### Sample Output 2

`2`

#### Sample Input 3

```
6
-1 -1 -1 2 -1 -1
```

#### Sample Output 3

`3`

## Comments