Число беспорядков $D_n$ обозначает количество таких перестановок $p$ чисел $1, 2, \dots, n$, что для каждого $i$ выполняется условие $p_i \neq i$.
Подсказка: существует простая рекуррентная формула для вычисления числа беспорядков: $D_n = (n-1)(D_{n-1}+D_{n-2})$.
Сяо Ай точно вычислила $D_n$ и распечатала его десятичное представление.
Однако из-за неисправности принтера на очень небольшом участке текста произошла ошибка, и невозможно распознать, какие именно цифры были напечатаны.
Она просит вас помочь восстановить исходные цифры на этом участке.
Входные данные
В первой строке вводится положительное целое число $n$.
Далее следует строка, состоящая из цифр и знаков вопроса ?. Пусть $S$ — десятичная запись числа $D_n$ (без ведущих нулей). Гарантируется, что во входной строке ровно один непустой интервал из $S$ был заменен на ? той же длины.
Выходные данные
Выведите целое число — точное значение $D_n$.
Примеры
Пример 1
Входные данные
10 133??61
Выходные данные
1334961
Подзадачи
Пусть общая длина ? равна $l$.
Для $100\%$ данных гарантируется, что $2\le n\le 10^5, 1\le l\le 9$.
| Номер теста | Особые свойства |
|---|---|
| $1, 2$ | $n\le 10$ |
| $3\sim 8$ | $n\le 10^3$ |
| $9\sim 11$ | ? образуют префикс $S$ |
| $12\sim 14$ | ? образуют суффикс $S$ |
| $15\sim 17$ | $l=1$ |
| $18\sim 20$ | Нет |