F. Харилцан анхны сэлгэмэл

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

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

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

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

Хоёр эерэг тоонууд нь хэрвээ $1$-с их ерөнхий хуваагчгүй бол харилцан анхны болно.

Баавгай Рэйдвүүшд зарим алгоритмын бодлогуудыг хэрхэн шийдэхийг хэлэхийг хүсээгүй. Ингээд Рэйдвүүш баавгайн нууцруу шийдлүүдийн тусламжтай халдхаар шийдсэн. Хаалгыг нэвтрэн гарахын тулд тэр $1$-c $n$ хүртэлх тоонуудын сэлгэмэл оруулах ёстой. Хаалга нь оруулсан $p_{1}, p_{2}, ..., p_{n}$ сэлгэмэл нь:

нөхцөл хангагдсан байх үед л нээгдэнэ.

Өөрөөр хэлбэл ялгаатай хоёр элементийн индексүүд нь харилцан анхны бол уг элементүүд харилцан анхны байна.

Сэлгэмэлийн зарим элементүүд тогтмол байж болно. Хаалгыг онгойлгохоор Рэйдвүүш хэдэн янзаар үлдсэн завсарыг дүүргэж чадах вэ? Хариултыг $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэ.

Оролт

Оролтын эхний мөрөнд нэг бүхэл тоо $n$ ($2 ≤ n ≤ 1 000 000$) байна.

Хоёр дахь мөрөнд $n$ бүхэл тоо $p_{1}, p_{2}, ..., p_{n}$ ($0 ≤ p_{i} ≤ n$) байх ба энд $p_{i} = 0$ нь дүүргэх завсар бол $p_{i} ≥ 1$ нь тогтмол тоог илэрхийлнэ.

Хэрвээ $i ≠ j$ ба $p_{i}, p_{j} ≥ 1$ байвал $p_{i} ≠ p_{j}$ байх нь тодорхой.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

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

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

Тэмдэглэл

Эхний жишээн дээр дөрвөн элементийн аль нь ч тогтмол биш. Өгөгдсөн нөхцлийг хангах дөрвөн сэлгэмэл байна: (1,2,3,4), (1,4,3,2), (3,2,1,4), (3,4,1,2).

Хоёр дахь жишээн дээр $p_{3} = 1$ ба $p_{4} = 2$ байх ёстой. Нөхцлүүдийг хангах хоёр сэлгэмэл нь: (3,4,1,2,5), (5,4,1,2,3).

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