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

Limits: 4 sec., 256 MiB

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

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

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

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

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

Input

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

Output

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

Constraints

$1 \le n \le 10^6$.

Samples

Input (stdin) сopy	Output (stdout) сopy
47	10

Notes

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