Bob and Alice are playing with an array \(A[]\) of \(n\) elements with Bob starting the game. In each turn:

A player picks a non-zero number of elements from \(A[]\) with the same value and remove it from \(A[]\).
The player whose turn makes array \(A[]\) empty wins the game.

Alice modifies the game a bit. She selects some distinct elements that are present in \(A[]\) and removes all other elements that are not selected from \(A[]\). Now, the game is played using this modified array. For example, if \(A = [1,1,3,12,2,34,2]\) and Alice selects values \((1,\ 2,\ 34)\), then the array with which the game is played is \([1,\ 1,\ 2,\ 34,\ 2]\).

Find the number of possible subsets of elements that Alice can select to modify \(A[]\) such that Alice must win if both the players play optimally.

Note

Consider an empty subset as a valid answer.
Since the number of possible subsets can be large, print the answer modulo \(10^9 + 7\).

Input format

The first line contains \(N\).
The next line contains \(N\) space-separated integers denoting the elements of \(A[]\).

Output format

Print the number of possible subsets of elements that Alice can select to modify \(A[]\) such that Alice must win if both the players play optimally modulo \(10^9 + 7\).

Constraints
\(1 \le N \le 100000\\ 1 \le A[i] \le 100\)