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

• dacă \( {a}_{i}>0 \), atunci \( {b}_{i}={a}_{i} \)
• dacă \( {a}_{i}=0 \), atunci \( {b}_{i} \) poate avea orice valoare strict pozitivă
• dacă \( {a}_{i}<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ța

Ș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 1.000.000 007.

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 1.000.000 007.

Restricții și precizări

• 1 ≤ N ≤ 300.000
• \( -300.000 ≤ {a}_{i} ≤ 300.000 \)
• Pentru 35 de puncte, 1 ≤ N ≤ 1000 și \( -1.000 ≤ {a}_{i} ≤ 1.000 \)
• Pentru alte 20 de puncte, \( 0 ≤ {a}_{i} ≤ 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.