Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.
У Пети есть последовательность a из n целых чисел.
Подпоследовательность последовательности a — это последовательность, которая получается из a путем удаления нуля или более ее элементов.
Две подпоследовательности считаются различными, если множества индексов входящих в них чисел различны, то есть значения элементов не учитываются при сравнении подпоследовательностей. В частности, любая последовательность длины n имеет ровно 2n различных подпоследовательностей (считая пустую).
Подпоследовательность называется счастливой, если она имеет длину ровно k, и не содержит двух одинаковых счастливых чисел (несчастливые числа могут повторяться сколько угодно раз).
Помогите Пете найти количество различных счастливых подпоследовательностей последовательности a. Так как родители не разрешают Пете играть с большими числами, результат нужно вывести по модулю простого числа 1000000007 (109 + 7).
Примечание
В первом примере все 3 подпоследовательности нужной длины являются счастливыми.
Во втором примере есть 4 счастливые подпоследовательности, множества индексов для которых равны (индексация с 1): {1, 3}, {1, 4}, {2, 3} и {2, 4}.