printРайонно-городские командные соревнования

print4. Обычные билеты

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Питер любит теорию чисел. Поэтому он интересуется автобусными билетами. Билет с числом длиной `2N` цифр является "интересным", если произведение первых `N` цифр этого числа равно произведению последних `N` цифр. Другие билеты называются "обычными".
Питер нашел использованный билет в кармане. К сожалению, билет был прокомпостирован, так что Питер не мог разобрать некоторые цифры. Он хотел узнать, является ли этот билет "интересным" для него. Более того, он хотел узнать, как много различных "интересных" и "обычных" билетов при компостировании могли дать этот билет.
Помогите Питеру найти ответы на его вопросы.
Первая строка входного файла содержит целое число `N` (`1\ ≤\ N\ ≤\ 9`). Следующая строка содержит номер билета. Если некоторая цифра прокомпостирована, она помечается как "?", в противном случае она изображается как есть.
Первая строка выходного файла должна содержать число "интересных" билетов. Вторая строка выходного файла должна содержать число "обычных" билетов.

Пример ввода 1

2
2??3

Пример вывода 1

4
96

Пример ввода 2

3
2?6??3

Пример вывода 2

46
954
Источник: ACM ICPC NEERC, Northern subregion 2003
loading