Array Description

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. Cho mảng độ dài $n$. Mỗi phần tử bằng $0$ nghĩa là chưa xác định, hoặc là một số trong $[1,m]$. Cần thay mọi số $0$ sao cho hai phần tử kề nhau chênh lệch không quá $1$. Hãy đếm số mảng hợp lệ.

Input

Dòng đầu chứa $n,m$. Dòng hai chứa $n$ số.

Output

In số cách modulo $10^9+7$.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

3 5
2 0 2

Output

3

Explanation

The output follows directly from the rules above.