Given an array of ~N~ integers, print the number of different subsets such that no two subsets have identical contents, and that every subset does not contain duplicate elements. Since this number can be very large, print it modulo ~10^9+7~. Note that the empty subset is counted.

Input Specification

The first line will contain the integer ~N\ (1 \le N \le 10^5)~, the number of integers.

The next line will contain ~N~ integers ~a_i\ (1 \le a_i \le 10^9)~, the array.

Output Specification

Print the answer modulo ~10^9+7~.

Subtasks

Subtask 1 [40%]

~1 \le N \le 18~

Subtask 2 [60%]

No further constraints.

Sample Input

4
1 2 2 3

Sample Output

8