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 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
- 2 1 2
- 2 2 2
- 2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB