26797번 - Impreza krasnali 다국어

Krasnale znowu urządziły sobie imprezę^∗. Znów było ich n i znów każdy z nich dostał spiczastą czapkę (spośród n czapek o różnych wysokościach od 1 do n). Tym razem jednak wszyscy ucztowali po jednej stronie długiego stołu.

Ponieważ krasnale wspominały tę imprezę jak żadną inną, lokalny malarz postanowił uwiecznić scenę uczty na obrazie. W tym celu potrzebuje dowiedzieć się, kto gdzie siedział przy stole i jaką miał czapkę. Krasnale pamiętają, gdzie siedziały, ale czapki były zakładane losowo i żaden z krasnali nie pamięta wysokości swojej czapki. Każdy z nich umie jedynie powiedzieć, jaką czapkę miał jeden z jego sąsiadów przy stole.

Pomóż malarzowi i napisz program, który wyznaczy liczbę możliwych ustawień czapek dla danych zeznań krasnali. Wystarczy reszta z dzielenia przez 10⁹ + 7. Jeśli krasnale pomyliły się i informacje podane przez nie są wzajemnie sprzeczne, prawidłowym wynikiem jest 0.

^∗Poprzednim razem miało to miejsce w zeszłym roku, podczas zawodów II stopnia XXVIII OI, w zadaniu Zdjęcia krasnali.

W pierwszym wierszu wejścia znajduje się liczba całkowita n (n ≥ 2) oznaczająca liczbę krasnali.

W drugim wierszu jest ciąg n liczb całkowitych h₁, h₂, . . . , h_n (1 ≤ h_i ≤ n); liczba h_i oznacza, że i-ty krasnal (licząc od lewego końca stołu) powiedział malarzowi: „ jeden z moich sąsiadów przy stole miał czapkę o wysokości h_i”.

Twój program powinien wypisać na wyjście jeden wiersz zawierający liczbę całkowitą oznaczającą liczbę możliwych ustawień czapek zgodnych z odpowiedziami krasnali. Wynik ma być podany modulo 10⁹ + 7.

• n ≤ 100 000

Wyjaśnienie przykładu: Pierwszy krasnal na pewno opisuje czapkę drugiego (zatem drugi ma czapkę 3), a piąty krasnal czapkę czwartego (zatem czwarty ma czapkę 1). Poza tym drugi i czwarty krasnal pamiętają czapkę 4, zatem na pewno była to czapka trzeciego krasnala. Pozostały dwie możliwości rozstawienia czapek 2 i 5.