양의 정수로 이루어진 배열 $x$에 대한 다음 두 단계를 하나의 연산이라고 부릅니다:

1. $x$에서 인접한 두 원소를 임의로 선택하여, 그중 하나를 $1$ 감소시키고 다른 하나를 $0$으로 설정합니다.
2. $x$에서 모든 0을 제거합니다.

유한 번(0번도 가능)의 연산 후에 빈 수열로 변환될 수 있을 때, 그리고 그때에만 $x$를 신비롭다(mystic)고 부릅니다.

$n$개의 정수로 이루어진 배열 $a$와 정수 $m$이 주어집니다. $a$의 각 원소는 $1$부터 $m$까지의 정수이거나 $-1$입니다. 당신의 과제는 $a$에 등장하는 모든 $-1$을 $1$부터 $m$까지의 임의의 정수로 대체하는 것입니다.

대체 후에 얻을 수 있는 서로 다른 신비로운 배열 $a$의 개수를 구하세요. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하세요.

입력

입력의 첫째 줄에 두 정수 $n$과 $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$)이 주어집니다.

입력의 둘째 줄에 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ 또는 $a_i = -1$)이 주어집니다.

출력

얻을 수 있는 서로 다른 신비로운 수열 $a$의 개수를 $10^9 + 7$로 나눈 나머지를 나타내는 정수 하나를 출력하세요.

예제

예제 입력 1

2 2
-1 -1

예제 출력 1

3

예제 입력 2

6 10
-1 -1 -1 -1 1 7

예제 출력 2

9125

노트

첫 번째 테스트에서 배열 $a$는 $[-1, -1]$입니다. 두 $-1$을 모두 대체하여 얻을 수 있는 결과 중 하나는 $[1, 2]$입니다. 이 경우 인접한 두 수를 선택하여 첫 번째 수를 $1$ 감소시키고 두 번째 수를 $0$으로 설정하면 $[0, 0]$을 얻습니다. 모든 0을 제거하면 수열은 비게 됩니다. 따라서 $[1, 2]$는 신비로운 수열입니다.

마찬가지로 $-1$들을 대체하여 $[1, 1]$ 또는 $[2, 1]$로 만들면 두 수열 모두 빈 수열로 줄일 수 있습니다. 따라서 서로 다른 신비로운 수열의 총개수는 $3$입니다.