Imagine you have a rooted tree consisting of vertices. Consider the following function:

int order[n]; // initially consists of -1
int pointer = 0;
void dfs(int vertex, int depth) {
  order[pointer] = depth;
  pointer++;
  for each child of vertex
    dfs(child, depth + 1);
}

In the end this function produces an array . We will call an array suitable if and only if it can be produced as a result of running on a rooted tree with vertices.

You are given an array , whose elements are either question signs or integer numbers. How many suitable arrays can you get, if you are allowed to replace any question sign with non-negative integer number? Print this number modulo .

Input Format

The first line contains a single integer , that is the size of array . The next line contains elements of the array: . Each element is either a question sign, or a non-negative integer number which doesn't exceed .

Constraints

Output Format

Print a single integer the number of suitable arrays you can get modulo .

Sample Input #0

3
? ? ?    

Sample Output #0

2

Sample Input #1

2
1 ?

Sample Output #1

0

Sample Input #2

4
0 ? 1 ?

Sample Output #2

2

Explanation

In sample#0 there are two possible arrays: [0, 1, 2] and [0, 1, 1];

In sample#1 there cannot be any suitable arrays, because each of them starts with 0.