配列の埋め方
n 個の要素からなる配列があり、そのすべての値は 1 以上 m 以下であることがわかっています。さらに、隣接する要素同士の絶対差は最大でも 1 に収まるように配置されているとします。このとき、配列のいくつかの値が消されている場合に、もとの条件を壊さずに配列を再び埋める方法が何通りあるかを求める問題です。入力
最初の行には 2 つの整数
n (1 ≤ n ≤ ) と m (1 ≤ m ≤ 100) が与えられます。次の行には、
n 個の要素 (1 ≤ ≤ m) がスペース区切りで与えられます。ここで、 が 0 の場合は、その位置の値が消されていることを意味します。出力
条件を満たすように配列を埋めることができる方法の総数を出力してください。答えが大きくなる場合があるので、結果は で割った余りを出力します。
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