Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

У Пети есть последовательность a из n целых чисел.

Подпоследовательность последовательности a — это последовательность, которая получается из a путем удаления нуля или более ее элементов.

Две подпоследовательности считаются различными, если множества индексов входящих в них чисел различны, то есть значения элементов не учитываются при сравнении подпоследовательностей. В частности, любая последовательность длины n имеет ровно 2ⁿ различных подпоследовательностей (считая пустую).

Подпоследовательность называется счастливой, если она имеет длину ровно k, и не содержит двух одинаковых счастливых чисел (несчастливые числа могут повторяться сколько угодно раз).

Помогите Пете найти количество различных счастливых подпоследовательностей последовательности a. Так как родители не разрешают Пете играть с большими числами, результат нужно вывести по модулю простого числа 1000000007 (10⁹ + 7).