题目描述

档案终端使用一种特殊的数码字体。以下数字旋转 $180$ 度后，仍可辨认为表中对应的数字：

原编号恰好有 $n$ 位，每一位都必须是表中的数字，且第一位不能是 $0$。将显示原编号的整块屏幕旋转 $180$ 度后，数字的位置顺序也会反转。例如，原编号 126 旋转后读作 921。

终端将原编号与旋转后读数分别按十进制整数解释，并把两者的和作为校验值。旋转后读数保留 $n$ 个数位，可以以 $0$ 开头；其前导零不影响求和。校验值写成恰好 $n+1$ 位，不足时在左侧补 $0$。

现在，原编号的部分数位已经模糊，用字符 ? 表示。给定原编号的模板和校验值，请计算有多少个原编号既符合模板，又能产生该校验值。答案对 $1000000007$ 取模。

输入格式

从文件 rotcheck.in 中读取数据。

第一行输入一个整数 $n$。

第二行输入一个长度为 $n$ 的字符串 $P$，表示原编号的模板。? 可以替换为任意一个可旋转数字，其他字符表示该位置的数字已经确定。

第三行输入一个长度为 $n+1$ 的字符串 $S$，表示校验值。

输出格式

输出到文件 rotcheck.out 中。

输出一个整数，表示符合条件的原编号数量对 $1000000007$ 取模后的结果。

2
??
033

2

3
6?9
1368

2

样例解释

样例 #1 中，两个符合条件的原编号是 12 和 21。它们旋转后分别读作 21 和 12，校验值都是 033。

样例 #2 中，两个符合条件的原编号是 669 和 699。它们旋转后分别读作 699 和 669，校验值都是 1368。

数据规模与约定

对于所有测试数据，保证：

• $1\le n\le 2\times 10^5$；
• $P$ 的长度为 $n$，且仅包含字符 ?、0、1、2、5、6、8、9；
• $S$ 的长度为 $n+1$，且仅包含数字字符，第一位为 0 或 1。

记 $q$ 为 $P$ 中字符 ? 的数量。各子任务采用捆绑计分：只有通过该子任务的全部测试数据，才能获得该子任务的分值。

下发文件

下载三组测试数据，非真实测试数据