Щаслива генерація

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

Зеник і Марічка мають рядок \(s\) із \(n\) щасливих цифр 4 та 7.

За один крок Марічка може наказати Зенику поміняти місцями довільні дві сусідні цифри рядка \(s\).

Марічці цікаво, скільки різних рядків вона може отримати, виконавши довільну кількість кроків (можливо, нульову).

Вхідні дані

У першому рядку задано рядок \(s\), який складається лише із цифр 4 та 7.

Вихідні дані

У єдиному рядку виведіть одне ціле число — кількість можливих рядків.

Обмеження

\(1 \le n \le 16\).

Приклади

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

Примітки

Використовуючи один обмін Марічка може отримати рядки 7447, 4477, 4774, за два обміни — 7474, а за три — 7744. Отже, відповідь (з урахуванням початкового рядка) рівна 6.