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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

Output

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

Constraints

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

Samples

Input (stdin) сopy	Output (stdout) сopy
4747	6

Notes

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