Mopadulo

Liczby mopadulop to liczby, których reszta z dzielenia przez p jest parzysta. Nie znamy innych dużych liczb pierwszych niż 109 + 7, dlatego będziemy zajmować się tylko liczbami mopadulo1 000 000 007.

Policz, na ile sposobów można podzielić zadany ciąg liczb a1, a2, . . . , an na przedziały, tak aby suma liczb w każdym z nich była liczbą mopadulo1 000 000 007. W takim podziale każdy element ciągu musi należeć do dokładnie jednego przedziału. Jako że liczba takich podziałów może być bardzo duża, to wystarczy, że podasz jej resztę z dzielenia przez (jakżeby inaczej) 109 + 7.

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 300 000), oznaczająca długość zadanego ciągu.

W drugim wierszu wejścia znajduje się ciąg n liczb całkowitych a1, a2, . . . , an (0 ≤ ai < 109 + 7).

Na wyjściu powinna znaleźć się jedna liczba całkowita, oznaczająca resztę z dzielenia liczby poprawnych podziałów ciągu a1, a2, . . . , an przez 109 + 7.

Wyjaśnienie przykładu: Poprawne podziały na przedziały to:

• [1000000006, 1, 5, 1000000004]
• [1000000006, 1], [5, 1000000004]
• [1000000006], [1, 5], [1000000004]