Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.
Однажды во сне Петя увидел лексикографически k-ую перестановку целых чисел от 1 до n. Определите, сколько счастливых чисел стоит в этой перестановке на позициях, номера которых также являются счастливыми числами.
Выходные данные
Если не существует k-ой перестановки чисел от 1 до n, выведите одно число «-1» (без кавычек). Иначе выведите ответ на задачу: количество таких i, что одновременно и i, и ai являются счастливыми числами.
Примечание
Перестановка — это упорядоченный набор из n элементов, в котором каждое целое число от 1 до n встречается ровно один раз. Элемент перестановки в позиции i обозначается ai (1 ≤ i ≤ n). Перестановка a лексикографически меньше перестановки b, если существует такое i (1 ≤ i ≤ n), что ai < bi, и для любого j (1 ≤ j < i) aj = bj. Составим список из всех возможный перестановок из n элементов, и отсортируем его в порядке лексикографического возрастания. Тогда лексикографически k-ая перестановка — k-ый элемент этого списка перестановок.
В первом примере перестановка имеет вид:
1 2 3 4 6 7 5
Единственная подходящая позиция — 4.
Во втором примере перестановка имеет вид:
2 1 3 4
Единственная подходящая позиция — 4.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7 4
|
1
|
|
2
|
4 7
|
1
|