错排数 $D_n$ 表示 $1,2,\dots,n$ 的排列中对每个 $i$ 都满足 $p_i\neq i$ 的 $p$ 的数目。
提示：我们有一个简单的递推公式来计算错排数：$D_n = (n-1)(D_{n-1}+D_{n-2})$。
小艾精确地算出了 $D_n$，并将其十进制表示打印了出来。
但是由于打印机出现了一点故障，其中有一个非常小段的部分出现了错误，识别不出所印的数字是几了。
她请你帮忙还原这段位置原本的数字。
输入格式
第一行输入一个正整数 $n$。
接下来一个字符串。其由数字和问号 ? 组成。设 $D_n$ 在十进制表示下书写成的串为 $S$（无前导零），保证输入的字符串恰好将 $S$ 中的一个非空区间替换为相同长度的 ?。
输出格式
输出一个整数，即 $D_n$ 的精确值。
样例数据
样例 1 输入
10 133??61
样例 1 输出
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$ | 无 |