Щасливенькі числа

Обмеження: 4 сек., 256 МіБ

Жоден із однокласників Зеника та Марічки не пристав до їхньої підготовки до ЗНО, бо сьогодні вони беруть участь у районній олімпіаді з інформатики. Тому Зеник і Марічка готуватимуться вдвох. Першою вони складатимуть математику, тому й розпочнуть підготовку з неї. Відкрили програму з математики, і першою темою, на яку вони натрапили, були щасливі числа. Добре, що в шкільній бібліотеці є збірник задач з цієї теми.

Зеник і Марічка пропонують Вам теж розв’язати одну з задач зі збірника.

Відомо, що щасливим числом є те, десятковий запис якого містить тільки четвірки та сімки. Наприклад, щасливими є числа 4, 7, 47, 7777 та 4744474.

Щасливеньким називається натуральне число, у якого сума цифр — щаслива.

Порахуйте кількість щасливеньких чисел, що не перевищують \(n\).

Вхідні дані

У єдиному рядку задано одне ціле число \(n\).

Вихідні дані

У єдиному рядку виведіть одне ціле число — кількість щасливеньких чисел, що не перевищують \(n\).

Обмеження

\(1 \le n \le 10^6\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
47	10

Примітки

Усі щасливенькі числа, що не перевищують 47: 4, 7, 13, 16, 22, 25, 31, 34, 40, 43.