在一行上输入一个整数 。在第二行上输入一个长度为 的 串 。
输出一个整数,表示满足要求的切分方案数量对 取模后的结果。
5 10001
4
两数 之间有 个 ,可以在 个相邻的空隙中任选一个位置切分:`1 | 0 0 0 1``1 0 | 0 0 1``1 0 0 | 0 1``1 0 0 0 | 1`故共有 种切分方案。