The derangement number $D_n$ denotes the number of permutations $p$ of $1, 2, \dots, n$ such that $p_i \neq i$ for every $i$.
Hint: We have a simple recurrence relation to calculate derangement numbers: $D_n = (n-1)(D_{n-1}+D_{n-2})$.
Xiao Ai calculated $D_n$ precisely and printed its decimal representation.
However, due to a printer malfunction, a very small segment of the output was corrupted, making it impossible to identify the printed digits.
She asks for your help to restore the original digits in that position.
Input
The first line contains a positive integer $n$.
The next line contains a string consisting of digits and question marks ?. Let $S$ be the decimal representation of $D_n$ (without leading zeros). It is guaranteed that the input string is formed by replacing a non-empty substring of $S$ with ? of the same length.
Output
Output an integer, which is the exact value of $D_n$.
Examples
Input 1
10 133??61
Output 1
1334961
Subtasks
Let $l$ be the total length of the ? sequence.
For $100\%$ of the data, it is guaranteed that $2 \le n \le 10^5$ and $1 \le l \le 9$.
| Test Case ID | Special Properties |
|---|---|
| $1, 2$ | $n \le 10$ |
| $3 \sim 8$ | $n \le 10^3$ |
| $9 \sim 11$ | ? forms a prefix of $S$ |
| $12 \sim 14$ | ? forms a suffix of $S$ |
| $15 \sim 17$ | $l = 1$ |
| $18 \sim 20$ | None |