Question
Subsequence 404 Finder
Emma has an array of n numbers and wants to find special subsequences within it. For each subsequence, if she combines all digits from its numbers, they should form the sequence “404.” Can you help Emma determine the number of subsequences that meet this condition?
Input
The first line of the input contains a single integer N, denoting the number of elements.
The second line of the input contains n space-separated integers, denoting the elements.
Constraints
1 ≤ n ≤ 105
a[i] belongs in {0, 4, 40, 404}
The second line of the input contains n space-separated integers, denoting the elements.
Constraints
1 ≤ n ≤ 105
a[i] belongs in {0, 4, 40, 404}
Output
A single integer denoting the answer.
Example
Sample Input
5
0 4 0 40 4
Sample Output
2
Explanation
{4, 0, 4} => 404
{40, 4 } => 404
5
0 4 0 40 4
Sample Output
2
Explanation
{4, 0, 4} => 404
{40, 4 } => 404