Algorithms and Data Structures

Filling the array

Given an array of n elements, you know that all the values in the array are between 1 and m. Besides that, the absolute difference between two adjacent elements is at most 1. Some of the values have been erased from the array and you’re asked to calculate the number of different ways the array can be filled without breaking the conditions.

Input

The first line of the input contains two integers n (1 ≤ n ≤ ) and m (1 ≤ m ≤ 100).
The next line contains n space-separated integers (1 ≤ ≤ m) representing the elements in the array. The value of being 0 denotes the erased value at position i.

Output

The program should print the number of ways to fill the array that satisfy the conditions. The output can be large, so the answer should be taken modulo .

Examples

Input
Output
3 5 2 0 2
3

Explanation

  1. 2 1 2
  1. 2 2 2
  1. 2 3 2
 

Constraints

Time limit: 6 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue