Petya非常喜欢幸运数字。大家都知道,幸运数字是正整数,其小数记录中仅包含幸运数字4和7。例如,数字47、744、4是幸运数字,而5、17、467则不是幸运数字。
Petya 有一个包含 n 个整数的数组 a。数组中的数字从 1 开始编号。不幸的是,Petya 一直行为不端,所以他的父母不允许他玩有很多幸运数字的数组。保证数组a中幸运数字不超过1000个。
Petya 需要找到不相交线段 [l1;r1] 和 [l2;r2] 的对数(1 ≤ l1 ≤ r1 < l2 ≤ r2 ≤ n,所有四个数字都是整数),使得子数组 a[l1..r1] 和子数组 a[l2..r2] 中不存在同时出现的幸运数字。帮助 Petya 数一下这样的对的数量。
输入
第一行包含一个整数 n (2 ≤ n ≤ 105) — 数组 a 的大小。第二行包含 n 个空格分隔的整数 ai (1 ≤ ai ≤ 109) — 数组 a。保证数组a中幸运数字不超过1000个。
输出
在单行上打印唯一的数字——问题的答案。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。
示例
输入 #1
4 1 4 2 4
输出 #1
9
输入 #2
2 4 7
输出 #2
1
输入 #3
4 4 4 7 7
输出 #3
9
注意
子数组 a[l..r] 是一个由元素 al, al + 1, ..., ar 组成的数组。
在第一个样本中,有 9 个可能的对满足条件:[1, 1] 和 [2, 2]、[1, 1] 和 [2, 3]、[1, 1] 和 [2, 4]、[1, 1] 和 [3, 3]、[1, 1] 和 [3, 4]、[1, 1] 和 [4, 4]、[1, 2] 和[3, 3]、[2, 2] 和 [3, 3]、[3, 3] 和 [4, 4]。
在第二个样本中只有一对段 - [1;1] 和 [2;2] 并且满足条件。