crescator

Fie un șir $a$ de $N$ numere îıntregi. Trebuie construit un nou șir $b$ (tot cu $N$ elemente) astfel:

• dacă $a_i \gt 0$, atunci $b_i = a_i$
• dacă $a_i = 0$, atunci $b_i$ poate avea orice valoare strict pozitivă
• dacă $a_i \lt 0$, atunci $b_i$ poate avea orice valoare strict pozitivă cu excepția lui $-a_i$

Se garantează că $a_1$ și $a_N$ au valori strict pozitive și între oricare două valori strict pozitive se va afla cel mult una strict negativă.

Cerință

Știindu-se șirul $a$, să se calculeze numărul de moduri de a forma șirul $b$ astfel încât acesta să fie crescător (nu neapărat strict). Deoarece acest număr poate fi foarte mare, se va afișa doar restul împărțirii la $10^9+7$.

Date de intrare

Fișierul de intrare crescator.in conține pe prima linie un număr natural $N$ și pe cea de-a doua $N$ numere întregi separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire crescator.out conține pe singura sa linie numărul cerut modulo $10^9+7$.

Restricții și precizări

• $1 \leq N \leq 300 \ 000$
• $−300 \ 000 \leq a_i \leq 300 \ 000$
• Pentru $35$ de puncte, $1 \leq N \leq 1 \ 000$ și $−1\ 000 \leq a_i \leq 1 \ 000$.
• Pentru alte $20$ de puncte, $0 \leq a_i \leq 300 \ 000$.

Exemplu

crescator.in

6
1 0 3 0 -4 5

crescator.out

12

Explicație

Cele $12$ șiruri crescătoare $b$ sunt: $(1, 1, 3, 3, 3, 5)$, $(1, 1, 3, 3, 5, 5)$, $(1, 1, 3, 4, 5, 5)$, $(1, 1, 3, 5, 5, 5)$, $(1, 2, 3, 3, 3, 5)$, $(1, 2, 3, 3, 5, 5)$, $(1, 2, 3, 4, 5, 5)$, $(1, 2, 3, 5, 5, 5)$, $(1, 3, 3, 3, 3, 5)$, $(1, 3, 3, 3, 5, 5)$, $(1, 3, 3, 4, 5, 5)$, $(1, 3, 3, 5, 5, 5)$.