T469844 [2024迎新马拉松] 质数

给定数字串 $S$，请计算 $S$ 中存在多少个子串，使得该子串不以 `0` 打头且它是长度**恰好** $K$ 的质数。

第一行包含一个整数 $K$。 第二行包含一个字符串 $S$。$S$ 中仅包含 `0`, `1`, $\ldots$, `9`。

一个整数，表示满足要求的子串数量。

【样例解释#$1$】 $S$ 中共有 $4$ 个长度 $2$ 的子串，其中 `71`, `29` 是质数。 【样例解释#$2$】 $S$ 中共有 $3$ 个长度 $4$ 的子串。它们或以 `0` 打头，或不是质数。 【样例解释#$3$】 $S$ 中能找到的长度 $6$ 的质数有 `314159`、`358979`、`589793`。 【样例解释#$4$】 $S$ 中有两个 `101`。 【数据规模】 本题共有三个子任务，每个子任务捆绑计分： - 子任务一，占分 $35\%$，保证 $1 \le K \le 2$； - 子任务二，占分 $35\%$，保证 $1 \le |S| \le 10^5$； - 子任务三，占分 $30\%$，无特殊约定。 对于全部测试数据，保证 $1 \le |S| \le 10^7$，$1 \le K \le 6$。