CSES 1746 ↗

Array Description

Number of arrays with values in `1..m`, adjacent values differing by at most 1, matching a description where `0` means unknown, modulo `10^9 + 7`.

0
submissions
—
best score

You know that an array has n integers between 1 and m, and the absolute difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

Input

The first input line has two integers n and m: the array size and the upper bound for each value.

The next line has n integers x1,x2,…,xn: the contents of the array. Value 0 denotes an unknown value.

Output

Print one integer: the number of arrays modulo 109+7.

Constraints

  • 1≤n≤105
  • 1≤m≤100
  • 0≤xi≤m

Example

Input:

3 5
2 0 2

Output:

3

Explanation: The arrays [2,1,2], [2,2,2] and [2,3,2] match the description.

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/ArrayDescription/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.