给定一个长度为 的 串 ,你需要把它完全切分成若干连续子串 ,使得: 对于任意的连续子段 ,命题 “该连续子段 内 恰好 包含一个数字字符 ” 恒成立。 ,即这些切分后的连续子串按切分顺序拼接起来后恰好能得到原字符串 。 你需要求出满足以上两个要求的切分方案的总数量。由于最终的计算结果可能很大,你只需要输出这个结果对 取模后的结果即可。
输入描述:
在一行上输入一个整数 。在第二行上输入一个长度为  的  串  。


输出描述:
输出一个整数,表示满足要求的切分方案数量对  取模后的结果。
示例1

输入

5
10001

输出

4

说明

{\hspace{15pt}}两数 1 之间有 30,可以在 4 个相邻的空隙中任选一个位置切分:
{\hspace{23pt}}\bullet\,`1 | 0 0 0 1`
{\hspace{23pt}}\bullet\,`1 0 | 0 0 1`
{\hspace{23pt}}\bullet\,`1 0 0 | 0 1`
{\hspace{23pt}}\bullet\,`1 0 0 0 | 1`
{\hspace{15pt}}故共有 4 种切分方案。
加载中...