该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

奇偶模板

题目描述

给定一个只含数字的字符串 $S$ 和一个整数 $P$。将 $P$ 看作一个 10 位二进制数，不足 10 位时在高位补 0，并从最低位开始依次编号为 $0,1,\ldots,9$。

对于每个数字 $d\in\{0,1,\ldots,9\}$，定义

如果 $b_d=1$，目标子串中数字 $d$ 必须出现奇数次；如果 $b_d=0$，数字 $d$ 必须出现偶数次。请统计满足全部十个奇偶要求的连续非空子串数量。

输入格式

第一行给出只含数字的字符串 $S$（$1\le |S|\le 5\times 10^5$）。第二行给出整数 $P$（$0\le P<2^{10}$）。$P$ 的二进制最低位对应数字 0，次低位对应数字 1，依此类推。

输出格式

输出满足目标奇偶模板的连续子串数量。

输入输出样例 #1

输入 #1

20230322
0

输出 #1

4

说明/提示

样例中 $P=0$，所以十个数字都必须出现偶数次。满足条件的 4 个子串为

• $S[1..6]=\texttt{202303}$；
• $S[1..8]=\texttt{20230322}$；
• $S[2..7]=\texttt{023032}$；
• $S[7..8]=\texttt{22}$。

这些子串中，每一种出现过的数字都恰好出现偶数次，其他数字出现 0 次，也属于偶数次。