← 返回比赛

已结束 GESP挑战赛#34

← 上一题下一题 →

A7484 | $星愿密码$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

$Sherry$ 正在制作科技节的星愿密码。密码由一串字符组成，每个字符可能是数字 0 到 9 ，也可能是问号 ? 。 在正式解读之前，每个 ? 都可以被替换成任意一个数字 0 到 9 。 解读规则如下： - 数字 1 到 26 分别表示字母 A 到 Z ； - 一个字符可以单独作为一个编码，但只能是 1 到 9 ； - 相邻两个字符可以合在一起作为一个编码，但必须是 10 到 26 ； - 所有字符都必须被恰好解读一次。 不同的替换方式或不同的划分方式，都算作不同的解读方案。 请你计算一共有多少种合法解读方案。由于答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行输入一个整数 $n$，表示密码长度。 第二行输入一个长度为 $n$ 的字符串 $s$。

输出格式

输出一个整数，表示合法解读方案数对 $10^9+7$ 取模后的结果。

输入输出样例

输入 #1

3
1?2

输出 #1

输入 #2

2
?0

输出 #2

C++ 编辑器

输入

输出