C. Иахуб ба сэлгэмлүүд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Иахуб ажил дээрээ өдөржингөө бабблэ-сорт граф зохион бүтээн, сэлгэмлүүд бичихдээ ихэд аз жаргалтай байв. Иахубина Иахубт чухал нэгэн байхаа больсон хэмээн ихэд ууртай байв. Иахубыг явсан хойгуур Иахубина түүний ажлын байранд очин судалгааны ажлыг бусниулж орхижээ.

Тэрээр судалгаанд их чухал үүрэг бүхий сэлгэмэл олжээ. Сэлгэмэл $a_{1}$, $a_{2}$, ..., $a_{n}$ $(1 ≤ a_{i} ≤ n)$ гэсэн ялгаатай $n$ ширхэг бүхэл тоогоор илэрхийлэгдэнэ. Тэрээр өшөө авах зорилгоор сэлгэмлийн зарим тоонуудыг -1 болгон өөрчилжээ.

Иахув сэлгэмлийг гэмтсэн болохыг мэдэн түүнийг сэргээн засварлахыг хүсчээ. Түүний санаж байгаа ганц зүйл нь сэлгэмэлд бэхлэгдсэн цэг байгаагүй ажээ. Сэлгэмлийн бэхлэгдсэн цэг гэдэг нь $(a_{k} = k)$ байх $a_{k}$ гишүүнийг хэлж байгаа юм. Чиний даалгавар бол Иахубт сэлгэмлийг сэргээх нь сайхан санаа биш болохыг ойлгуулах юм. Иахубын анхны сэлгэмэл нь байж болох сэлгэмлүүдийн тоог $1000000007$ ($10^{9} + 7$) тоонд хуваан хэвлэ.

Оролт

Эхний мөрөнд $n$ ($2 ≤ n ≤ 2000$) гэсэн бүхэл тоо байна. Хоёрдахь мөрөнд Иахубинагийн сүйтгэсний дараа үүссэн, зарим тоонууд нь -1 байх сэлгэмлийг илэрхийлэх $n$ ширхэг тоо байна.

Өгөгдсөн сэлгэмэлд бэхлэгдсэн цэг байхгүй байна. Мөн өгөгдсөн сэлгэмэлд хамгийн багадаа хоёр ширхэг -1 байх ба үлдсэн тоонууд хоорондоо ялгаатай байна. Мөн тохиромжтой сэлгэмэл ядаж нэг олдоно.

Гаралт

Өгөгдсөн сэлгэмлийг засварласны дараа үүсч болох сэлгэмлүүдийн тоог $1000000007$ ($10^{9} + 7$) тоонд хуваан үлдэгдлийг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
5
-1 -1 4 3 -1
Гаралт
2

Тэмдэглэл

Эхний жишээнд [2, 5, 4, 3, 1] ба [5, 1, 4, 3, 2] нар нь бэхлэгдсэн цэггүй. Бусад сэлгэмлүүд ядаж нэг бэхлэгдсэн цэгтэй байна.

Сэтгэгдлүүдийг ачааллаж байна...