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, Ai and Aj 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 109+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 109+7 on a single line.
Constraints
1≤N≤1000001≤A[i]≤109
There are following subsequences:
{1},{12},{23},{34} -> Good as there is only one element in each subsequence. These are 4 good subsequences.
{1, 12} -> Not good as 1 and 12 have 1 as the common digit.
{1,23}, {1,34}, {12,34} -> Good, no common digit. These are 3 good subsequences.
{12, 23} -> Not good as 1 and 12 have 2 as the common digit.
{23,34} -> Not good as 23 and 34 have 3 as the common digit.
{1,12,23}, {1,12,34} -> Not good as each of these have pair (1,12) which have 1 as the common digit.
{1,23,34}, {12,23,34} -> Not good as each of these have pair (23,34) which have 3 as the common digit.
{1,12,23,34} -> Not good as (1,12) pair has 1 as common digit.
So, there are 7 good subsequences for the given array.
