26699번 - Mopadulo 다국어

문제

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

Policz, na ile sposobów można podzielić zadany ciąg liczb a₁, a₂, . . . , a_n na przedziały, tak aby suma liczb w każdym z nich była liczbą mopadulo_{1 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) 10⁹ + 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 a₁, a₂, . . . , a_n (0 ≤ a_i < 10⁹ + 7).

출력

Na wyjściu powinna znaleźć się jedna liczba całkowita, oznaczająca resztę z dzielenia liczby poprawnych podziałów ciągu a₁, a₂, . . . , a_n przez 10⁹ + 7.

제한

힌트

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

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