Muallif: __thecrash__

K. Yomg'irda yuvilgan chizmalar

Vaqt limiti: 2000 ms Xotira limiti: 256 mb

Shahar arxitektura byurosida \(n\) ta bino balandligini ko'rsatuvchi \([b_1, b_2, \dots, b_n]\) massivi saqlanadi — bu yerda har bir \(b_i\) musbat butun son.

Har bir \(i\) \((1 \le i \le n)\) uchun \(g(b)\) massivini quyidagicha aniqlaymiz:

• Agar shunday \(j < i\) mavjud bo'lsaki, \(b_j < b_i\) bo'lsa, u holda \(g(b)_i = \max\limits_{j < i, \, b_j < b_i} j\). Ya'ni, \(g(b)_i\) — bu \(i\)-binodan chapda joylashgan, balandligi \(b_i\) dan qat'iy kichik bo'lgan eng o'ngdagi binoning raqami.
• Aks holda \(g(b)_i = 0\).

\([y_1, y_2, \dots, y_n]\) manfiy bo'lmagan butun sonlar massivini tiklanadigan massiv deb ataymiz, agar shunday \(b\) balandliklar massivi mavjud bo'lsaki, \(g(b) = y\) bo'lsa.

Yaqinda yomg'ir arxivdagi qog'ozlarni yuvib yubordi — uzunligi \(n\) bo'lgan \(x\) massivda ba'zi raqamlar o'chib ketdi (o'chgan joy \(-1\) bilan belgilanadi), qolganlari esa \(-1 \le x_i \le n\) shartini qanoatlantiradi. \(x\) dagi har bir \(-1\) ni \([0, n]\) oralig'idagi butun songa almashtirib, nechta usulda \(x\) ni tiklanadigan massivga aylantirish mumkinligini hisoblang. Javobni \(10^9 + 7\) ga bo'lgandagi qoldiqni chiqaring.

Kiruvchi ma'lumotlar

Har bir test bir nechta sinovdan iborat. Birinchi qatorda bitta butun son \(t\) \((1 \le t \le 10^3)\) — sinovlar soni. Keyin sinovlar tavsifi keladi.

Har bir sinovning birinchi qatorda \(x\) ning uzunligini bildiruvchi bitta butun son \(n\) \((1 \le n \le 5000)\) beriladi.

Ikkinchi qatorda \(n\) ta butun son \(x_1, x_2, \dots, x_n\) \((-1 \le x_i \le n)\) beriladi.

Barcha sinovlar bo'yicha \(n\) yig'indisi \(5000\) dan oshmasligi kafolatlanadi.

Chiquvchi ma'lumotlar

Har bir sinov uchun, \(x'\) tiklanadigan massiv bo'lgan \(x'\) massivlari sonini \(10^9 + 7\) bo'yicha qoldiqni ifodalovchi bitta butun son chiqaring.

Misollar

1

5
1
-1
4
-1 -1 0 -1
6
-1 -1 -1 -1 -1 -1
5
-1 1 3 4 -1
3
0 1 2

1
4
132
0
1

Izoh

Birinchi sinov uchun faqat \([0]\) massiv tiklanadigan hisoblanadi — chunki \(n = 1\) da \(g(b)_1\) doim \(0\) bo'ladi (chapda hech qanday element yo'q), shuning uchun \(x'_1 = 1\) bo'lishi mumkin emas.

Ikkinchi sinov uchun faqat \([0, 0, 0, 0]\), \([0, 0, 0, 3]\), \([0, 1, 0, 0]\) va \([0, 1, 0, 3]\) massivlari tiklanadigan hisoblanadi.