Jedan

Σε κάποιους αρέσει να προσποιούνται ότι είναι φαραώ. Ή ένα δελφίνι. Ο Luka είναι ένα τέτοιο άτομο.
Έχει κατασκευάσει ένα ανάγλυφο που αποτελείται από μια μεγάλη γραμμή ~N~ στηλών με μη αρνητικά ακέραια ύψη. Τα ύψη όλων των στηλών ήταν αρχικά μηδενικά. Το ανάγλυφο χτίστηκε σταδιακά, όπου σε κάθε βήμα ο Luka επιλέγει μια συνεχόμενη υποακολουθία στηλών με ίσα ύψη και υψώνει όλες τις στήλες στην υπακολουθία, εκτός από την πρώτη και την τελευταία στήλη, κατά ένα.

Έχουν περάσει εκατοντάδες χρόνια και μερικές από τις στήλες έχουν κλαπεί. Ο δισέγγονος του Luka προσπαθεί να προσδιορίσει τον αριθμό των πιθανών ανάγλυφων που θα μπορούσε να είχε χτίσει ο Luka έτσι ώστε τα ύψη των υπόλοιπων στηλών να ταιριάζουν με το αρχικό ανάγλυφο.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~N~ ~(1 \le N \le 10\,000)~, τον αριθμό των στηλών στο ανάγλυφο του Luka.
Η δεύτερη γραμμή εισόδου περιέχει ~N~ ακέραιους αριθμούς ~h_i~ ~(-1 \le h_i \le 10\,000)~, χωρισμένους με διάστημα, τα ύψη στηλών.
Ένα ύψος -1 αντιπροσωπεύει μια κλεμμένη στήλη.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό πιθανών ανάγλυφων με μορφή υπολοίπου ακέραιας διαίρεσης με το ~1\,000\,000\,007~.

Παραδείγματα

input

3
-1 2 -1

output

0

input

3
-1 -1 -1

output

2

input

6
-1 -1 -1 2 -1 -1

output

3