# Membobol brankas

Batasan Waktu: 1 detik
Batasan Memori: 256 MB

## Deskripsi

Pak Dengklek adalah seorang pembobol brankas yang handal. Namun hari ini, brankas yang ingin ia bobol sedikit unik, PIN-nya merupakan bilangan berbasis $K$ dengan $N$ digit yang dinomori dari $1$ sampai $N$ (bisa saja terdapat *leading zero*) yang tentunya setiap digit merupakan bilangan bulat dari $0$ sampai $K - 1$ secara inklusif.

Untuk membobol brankas ini, tentunya Pak Dengklek harus menebak semua digit tersebut dengan benar. Namun entah bagaimana caranya, Pak Dengklek berhasil mendapatkan informasi tentang PIN brankas ini berupa *array* $A$ sepanjang $N$ dimana setiap elemen di *array* ini merupakan bilangan bulat dari $-1$ sampai $K - 1$ secara inklusif. Jika $A_i \geq 0$, itu menandakan bahwa digit ke-$i$ sudah pasti lebih besar dari atau sama dengan $A_i$, sementara semua digit dengan nomor $i$ dimana $A_i = -1$ sudah pasti berbeda. Dengan kata lain, tidak ada 2 index $i$ dan $j$ dimana $1 \leq i < j \leq N$ yang memenuhi $A_i = A_j = -1$ dan digit ke-$i$ sama dengan digit ke-$j$.

Sebelum Pak Dengklek memulai aksinya, ia penasaran, ada berapa kemungkinan PIN yang memenuhi informasi yang diterimanya. Bantulah Pak Dengklek untuk menghitung jumlah kemungkinan tersebut! Karena jawabannya bisa sangat besar, keluarkan jawaban modulo $10^9 + 7$. Perhatikan bahwa bisa saja tidak ada PIN yang memenuhi, dalam kasus ini, artinya informasi yang diterima Pak Dengklek salah.

## Soal 1

Diberikan $N = 5, K = 10,$ dan $A = [1, 3, -1, -1, 9]$. Pak Dengklek menduga PIN-nya merupakan salah satu dari pilihan-pilihan berikut:
* $12345$
* $23449$
* $11159$
* $44459$
* $13339$

Manakah PIN dugaan Pak Dengklek yang memenuhi informasi yang diterimanya!

## Soal 2

Jika $N = K = 7$ dan $A_i = -1$ untuk semua $1 \leq i \leq 7$. Berapa kemungkinan PIN yang memenuhi informasi yang diterima Pak Dengklek?

## Soal 3

Setelah Pak Dengklek mencoba semua kemungkinan bilangan berbasis $K = 5$ dengan $N = 6$ digit yang jumlahnya ada $5^6$ kemungkinan, hanya ada $96$ kemungkinan yang memenuhi informasi yang diterima Pak Dengklek.

Beberapa saat setelah Pak Dengklek sudah mendapatkan jawabannya, ia malah lupa nilai dari $A_6$ dan hanya ingat $5$ elemen pertama di *array* $A$ yaitu $A = [3, 3, 3, 2, 3, ?]$. Ia tetap penasaran nilai dari $A_6$ yang sebenarnya. Berapakah nilai $A_6 \,$?

## Soal Pemrograman

### Masukan

Di baris pertama masukkan 2 bilangan $N$ dan $K$. Lalu dilanjut $N$ bilangan $A_1, A_2, ..., A_N$ di baris kedua.

### Keluaran

Keluarkan 1 baris berisikan jawaban yang diminta Pak Dengklek modulo $10^9 + 7$.

### Contoh 1

#### Masukan

3 3
-1 2 -1

#### Keluaran

6

#### Penjelasan

Kemungkinan-kemungkinan PIN yang memenuhi adalah 021, 022, 120, 122, 220, dan 221. Ada 6 kemungkinan.

### Contoh 2

#### Masukan

7 4
2 -1 -1 -1 0 -1 -1

#### Keluaran

0

#### Penjelasan

Ada 5 digit yang nilainya harus berbeda yaitu digit ke-2, 3, 4, 6, dan 7, sementara hanya ada $K = 4$ nilai yang mungkin untuk 1 digit, maka tidak mungkin ada PIN yang memenuhi.

### Batasan

* $1 \leq N, \, K \leq 100 \, 000$
* $-1 \leq A_i < K$
* Semua variabel di masukan merupakan bilangan bulat

### Subsoal

1. (50 poin) Hanya berisi kasus uji berikut:

   10 3
   -1 0 1 1 0 -1 1 0 0 1

2. (50 poin) Tidak ada batasan tambahan.