Eftirfarandi tvö skref, á fylki $x$ sem samanstendur af jákvæðum heiltölum, kallast aðgerð:

1. Veldu hvaða tvö aðliggjandi stök í $x$, minnkaðu annað þeirra um $1$ og settu hitt sem $0$.
2. Fjarlægðu öll núll úr $x$.

Við köllum $x$ dularfullt (mystic) ef og aðeins ef hægt er að breyta því í tóma runu eftir endanlegan fjölda aðgerða (mögulega núll).

Gefið er fylki $a$ sem samanstendur af $n$ heiltölum, ásamt heiltölu $m$. Hvert stak í $a$ er annaðhvort heiltala frá $1$ til $m$ eða $-1$. Verkefni þitt er að skipta út hverri tilviki af $-1$ í $a$ fyrir hvaða heiltölu sem er frá $1$ til $m$.

Ákvarðaðu fjölda ólíkra dularfullra fylkja $a$ sem hægt er að fá eftir útskiptinguna. Þar sem svarið getur verið mjög stórt skaltu prenta það modulo $10^9 + 7$.

Inntak

Fyrsta lína inntaksins inniheldur tvær heiltölur $n$ og $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^8$).

Önnur lína inntaksins inniheldur $n$ heiltölur $a_1, a_2, \dots, a_n$ ($1 \le a_i \le m$ eða $a_i = -1$).

Úttak

Prentaðu eina heiltölu sem táknar fjölda ólíkra dularfullra runa $a$ sem hægt er að fá, modulo $10^9 + 7$.

Dæmi

Dæmi um inntak 1

2 2
-1 -1

Dæmi um úttak 1

3

Dæmi um inntak 2

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

Dæmi um úttak 2

9125

Athugasemd

Í fyrsta prófinu er fylkið $a$ jafnt $[-1, -1]$. Með því að skipta út báðum $-1$ er ein möguleg niðurstaða $[1, 2]$. Í þessu tilviki veljum við tvær aðliggjandi tölur: minnkum þá fyrri um $1$ og setjum þá seinni sem $0$, og fáum $[0, 0]$. Eftir að öll núll hafa verið fjarlægð verður runan tóm. Því er $[1, 2]$ dularfull runa.

Á svipaðan hátt, ef við skiptum $-1$ út fyrir $[1, 1]$ eða $[2, 1]$, má einnig minnka báðar runurnar niður í tóma runu. Því er heildarfjöldi ólíkra dularfullra runa $3$.