Liczba nieporządków $D_n$ oznacza liczbę permutacji $p$ zbioru $\{1, 2, \dots, n\}$ takich, że dla każdego $i$ zachodzi $p_i \neq i$.
Wskazówka: Mamy prosty wzór rekurencyjny na obliczanie liczby nieporządków: $D_n = (n-1)(D_{n-1}+D_{n-2})$.
Xiao Ai dokładnie obliczyła $D_n$ i wydrukowała jego zapis dziesiętny.
Jednak z powodu awarii drukarki, w bardzo krótkim fragmencie wystąpił błąd i nie da się odczytać, jakie cyfry zostały wydrukowane.
Prosi Cię o pomoc w odtworzeniu oryginalnych cyfr w tym miejscu.
Wejście
W pierwszej linii znajduje się dodatnia liczba całkowita $n$.
W kolejnej linii znajduje się ciąg znaków składający się z cyfr oraz znaków zapytania ?. Niech $S$ będzie ciągiem znaków reprezentującym $D_n$ w zapisie dziesiętnym (bez zer wiodących). Gwarantuje się, że wejściowy ciąg znaków powstał poprzez zastąpienie niepustego podciągu $S$ znakami ? o tej samej długości.
Wyjście
Wypisz jedną liczbę całkowitą, będącą dokładną wartością $D_n$.
Przykład
Przykład 1
Wejście
10 133??61
Wyjście
1334961
Podzadania
Niech $l$ oznacza łączną liczbę znaków ?.
Dla $100\%$ danych wejściowych gwarantuje się, że $2\le n\le 10^5$ oraz $1\le l\le 9$.
| Numer testu | Własności specjalne |
|---|---|
| $1, 2$ | $n\le 10$ |
| $3\sim 8$ | $n\le 10^3$ |
| $9\sim 11$ | ? tworzą prefiks $S$ |
| $12\sim 14$ | ? tworzą sufiks $S$ |
| $15\sim 17$ | $l=1$ |
| $18\sim 20$ | brak |