错排数 $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$。