Оң бүтін сандардан тұратын $x$ массивіне жасалатын келесі екі қадам операция деп аталады:

1. $x$ ішінен кез келген екі көршілес элементті таңдап, олардың біреуін $1$-ге азайту, ал екіншісін $0$-ге теңестіру.
2. $x$ ішінен барлық нөлдерді өшіру.

Егер $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]$ шығады. Барлық нөлдерді өшіргеннен кейін тізбек бос болып қалады. Демек, $[1, 2]$ — жұмбақ тізбек.

Дәл сол сияқты, егер $-1$ сандарын $[1, 1]$ немесе $[2, 1]$ етіп алмастырсақ, бұл екі тізбекті де бос тізбекке айналдыруға болады. Сондықтан әртүрлі жұмбақ тізбектердің жалпы саны $3$-ке тең.