You are given an array \(A\). Your task is to determine the number of good subsequences. A subsequence is a non-empty set of indices from the provided array. A subsequence is defined as good if for any pairs of indexes \(i,\ j\) \((i != j)\) belonging to a subsequence, \(A_i\) and \(A_j\) have no common digits.

Two subsequences are said to be different if there is at least one index in one of the subsequences that is not present in the other subsequence.

Since the number of good subsequences can be large, print it modulo ^{\({10^{9} + 7}\)}.

Input format

• First line: An integer \(N\) denoting the size of array \(A\)
• Next line: \(N\) space-separated integers denoting the elements of array \(A\)

Output format

Print the number of good subsequences modulo ^{\({10^{9} + 7}\)} on a single line.

Constraints

\(1 \le N \le 100000\\ 1 \le A[i] \le 10^9\)