Internationella informatikolympiaden hålls i Japan. För att välkomna de tävlande från hela världen har man beslutat att dekorera skyskraporna längs huvudgatan från flygplatsen till boendeanläggningen. En berömd designer fick i uppdrag att utforma designen, och denne sade att byggnaderna som används för dekoration måste öka i höjd från flygplatsen mot boendeanläggningen. Med andra ord, om vi betecknar höjderna på de byggnader som används för dekoration i ordning från den som ligger närmast flygplatsen som $h_1, h_2, h_3, \dots$, så måste det gälla att $h_1 < h_2 < h_3 < \dots$.

För att göra dekorationerna så spektakulära som möjligt vill vi använda så många byggnader som möjligt. JOI, som fick i uppgift att välja ut vilka byggnader som ska dekoreras, insåg att det finns en risk att en fastighetsägare kommer med det orimliga kravet: "Jag vill att ni definitivt använder min byggnad för dekoration. För att byggnaden ska sticka ut vill jag dessutom att ni väljer byggnaderna så att min byggnad är den som ligger närmast boendeanläggningen bland alla byggnader som används för dekoration."

Det finns $N$ byggnader längs huvudgatan från flygplatsen till boendeanläggningen, och vi kallar den $i$-te byggnaden från flygplatsen ($1 \le i \le N$) för byggnad $i$. Höjderna på de $N$ byggnaderna är alla olika. JOI har på förhand beräknat följande: "När man väljer byggnader så att byggnad $i$ används för dekoration och byggnad $i$ är den som ligger närmast boendeanläggningen bland alla byggnader som används för dekoration, är det maximala antalet byggnader som kan väljas $A_i$."

JOI antecknade heltalsföljden $A_1, A_2, \dots, A_N$ som beräknats på detta sätt och lämnade in den till ordförande K i den japanska kommittén för Internationella informatikolympiaden.

Men anteckningen som ordförande K fick innehöll i själva verket bara en heltalsföljd $B_1, B_2, \dots, B_{N-1}$ av längd $N-1$. Eftersom ordförande K inte känner till informationen om byggnadernas höjder kan han inte beräkna värdena på $A_i$.

Ordförande K tänkte att JOI måste ha glömt att skriva ner ett tal. Olika följder $A_1, A_2, \dots, A_N$ kan tänkas beroende på byggnadernas höjder. Bland dessa, hur många följder finns det sådana att om man tar bort ett värde från följden så får man följden $B_1, B_2, \dots, B_{N-1}$?

Observera att JOI i verkligheten kan ha gjort andra misstag när han skrev. Beroende på värdena i $B_1, B_2, \dots, B_{N-1}$ kanske det inte finns någon sådan följd alls.

Uppgift

Givet en heltalsföljd $B_1, B_2, \dots, B_{N-1}$ av längd $N-1$, skriv ett program för att bestämma hur många följder $A_1, A_2, \dots, A_N$ som kan tänkas sådana att om man tar bort ett värde från följden så får man följden $B_1, B_2, \dots, B_{N-1}$.

Indata

Läs följande från standard inmatning:

• Den första raden innehåller ett heltal $N$. Detta representerar att det finns $N$ byggnader längs huvudgatan från flygplatsen till boendeanläggningen.
• Den $j$-te raden ($1 \le j \le N-1$) av de följande $N-1$ raderna innehåller ett heltal $B_j$. Detta är det $j$-te värdet i heltalsföljden som står i anteckningen som ordförande K fick.

Utdata

Skriv ut heltalet som representerar antalet följder $A_1, A_2, \dots, A_N$ sådana att om man tar bort ett värde från följden så får man följden $B_1, B_2, \dots, B_{N-1}$ på en enda rad.

Begränsningar

All indata uppfyller följande villkor:

• $2 \le N \le 1\,000\,000$.
• $1 \le B_j \le N$ ($1 \le j \le N-1$).

Deluppgifter

1. (10 poäng) $N \le 8$ är uppfyllt.
2. (30 poäng) $N \le 300$ är uppfyllt.
3. (60 poäng) Inga ytterligare begränsningar.

Exempel

Indata 1

4
1
1
2

Utdata 1

5

Det finns 4 byggnader längs huvudgatan från flygplatsen till boendeanläggningen. Låt $H_i$ vara höjden på byggnad $i$. Olika följder $A_1, A_2, A_3, A_4$ kan tänkas beroende på byggnadernas höjder. Bland dessa finns det 5 sätt sådana att om man tar bort ett värde från följden så får man följden $1, 1, 2$:

• Följden $1, 2, 1, 2$. Till exempel, när $H_2 > H_4 > H_1 > H_3$ har vi $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$. Även när $H_2 > H_1 > H_4 > H_3$ har vi $A_1 = 1, A_2 = 2, A_3 = 1, A_4 = 2$.
• Följden $1, 1, 2, 3$. Till exempel, när $H_4 > H_3 > H_1 > H_2$ har vi $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 3$.
• Följden $1, 1, 2, 1$. Till exempel, när $H_3 > H_1 > H_2 > H_4$ har vi $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 1$.
• Följden $1, 1, 2, 2$. Till exempel, när $H_3 > H_4 > H_1 > H_2$ har vi $A_1 = 1, A_2 = 1, A_3 = 2, A_4 = 2$.
• Följden $1, 1, 1, 2$. Till exempel, när $H_4 > H_1 > H_2 > H_3$ har vi $A_1 = 1, A_2 = 1, A_3 = 1, A_4 = 2$.

Indata 2

8
1
1
2
1
2
3
1

Utdata 2

15