K. Power Divisions
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We are given a sequence of non-negative integers $$$a_1, a_2, \ldots, a_n$$$. Based on this sequence, we create a sequence of integers $$$b_1, b_2, \ldots, b_n$$$, where $$$b_i = 2^{a_i}$$$ for each $$$i$$$.

A division of the sequence $$$b_1, b_2, \ldots, b_n$$$ is called a set of its contiguous intervals, such that each element belongs to exactly one interval. We call a division good if the sum of numbers in each interval is a power of two (with an integer exponent).

Your task is to count the number of good divisions of the sequence $$$b_1, b_2, \ldots, b_n$$$. Since this number can be very large, it is sufficient to provide its remainder when divided by $$$10^9+7$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) representing the length of the sequence $$$a_1, a_2, \ldots, a_n$$$ (and thus also the length of the sequence $$$b_1, b_2, \ldots, b_n$$$).

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^6$$$).

Output

The output should contain a single integer, representing the remainder when divided by $$$10^9+7$$$ of the number of good divisions of the sequence $$$b_1, b_2, \ldots, b_n$$$.

Example
Input
5
2 0 0 1 1
Output
6
Note

The sequence $$$b_1, b_2, \ldots, b_n$$$ in the sample test is $$$4, 1, 1, 2, 2$$$. Its good divisions are:

  • $$$[4], [1], [1], [2], [2]$$$,
  • $$$[4], [1, 1], [2], [2]$$$,
  • $$$[4], [1], [1], [2, 2]$$$,
  • $$$[4], [1, 1], [2, 2]$$$,
  • $$$[4], [1, 1, 2], [2]$$$,
  • $$$[4, 1, 1, 2], [2]$$$.