Distinct Values Subsequences

Given an array of $nn$ integers, count the number of subsequences where each element is distinct.

A subsequence is a sequence of array elements from left to right that may have gaps.

Input

The first line has an integer $nn$: the array size.

The second line has $nn$ integers $x_1,x_2,\dots ,x_{n}x\_1,x\_2,\backslash dots,x\_n$: the array contents.

Output

Print the number of subsequences with distinct elements. The answer can be large, so print it modulo ${10}^9+710^9+7$.