Petya的序列

时间限制:10s      空间限制:512MB

题目描述

幸运数字是那些仅由4和7构成的数字,比如477,44,777是幸运数字,而789,457,123不是幸运数字。
有一天Petya得到了一个长度为N的非负整数序列A,其中A[i]表示该序列的第i个元素。他想从整个序列中选出两个互不相交的子段A[L1,R1], A[L2,R2](1<=L1<=R1<L2<=R2<=n),使得不存在某个幸运数字既在A[L1,R1]出现,又在A[L2,R2]出现。Petya想知道他有多少种选择方案,你能帮帮他吗?
Petya保证A序列中幸运数字的总出现次数不会超过1000次。


输入格式

输入的第一行包含一个正整数n,表示A序列的长度。
第二行包含n个整数,第i个整数表示A[i]。


输出格式

输出一行表示总的方案个数。


样例输入

4
1 4 2 4

样例输出

9

提示

n <= 100000,幸运数字的总出现次数不超过1000
此题存在版权,故不再支持提交,保留在此只供大家参考题面! 望见谅!


题目来源

没有写明来源