Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.
У Пети есть массив a из n целых чисел. Числа в массиве нумеруются начиная с 1. К сожалению, в последнее время Петя плохо писал контесты, поэтому родители не разрешают ему играть с массивами, в которых много счастливых чисел. Гарантируется, что в массиве a не более 1000 элементов являются счастливыми.
Пете нужно найти количество пар непересекающихся отрезков [l1;r1] и [l2;r2] (1 ≤ l1 ≤ r1 < l2 ≤ r2 ≤ n, все четыре числа — целые) таких, что нет такого счастливого числа, которое встречается одновременно и в подмассиве a[l1..r1], и в подмассиве a[l2..r2]. Помогите Пете посчитать количество таких пар.
Выходные данные
В единственной строке выведите одно число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примечание
Подмассив 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] и она удовлетворяет условие.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 4 2 4
|
9
|
|
2
|
2
4 7
|
1
|
|
3
|
4
4 4 7 7
|
9
|