Числа в Задзеркаллі#5770
Назвемо -значне число, яке не містить провідних незначущих нулів, числом із Задзеркалля, якщо його можна написати на папері, зображуючи цифри так, як їх показують на електронних табло (див. рисунок), а потім піднести до цього зображення дзеркало і побачити в ньому те саме число. При цьому всі цифри повинні відображатися в дзеркалі без викривлень, а число має читатися, як зазвичай, зліва направо. Єдине, що може змінюватися, — це відстань між цифрами числа.
Вася записав на папері деякі цифри одного з -значних чисел. Він також зафіксував позиції цих цифр у числі. Допоможіть йому визначити, скільки різних чисел із Задзеркалля він може скласти, заповнюючи всіма можливими способами інші позиції.
У першому рядку вхідних даних записано одне натуральне число (1 \le N \le 30). У другому рядку знаходяться рівно символів, частина з яких цифри, а частина — символи '*', що позначають вільні місця. Рядок закінчується символом переведення рядка.
Виведіть кількість -значних чисел із Задзеркалля, які можна отримати, заповнюючи вільні місця цифрами.
Приклад 1
Умову цієї задачі потрібно зрозуміти буквально.
Щоб перевірити відповідь до першого прикладу, можна перебрати всі варіанти на папері і підносити до них дзеркало, поки не стане зрозуміло, які 3 варіанти є підходящими.