题目描述

给定一个只包含数字字符的字符串 s 和一个十进制正整数 k。请问可以从 s 中截取多少个子串，使得构成子串所包含的数码和是 k 的倍数。

例如：当 $s=$"5764"$,k=3$ 时，有且仅有 6，57，576 这三个子串是 3 的倍数，因为 6 是 3 的倍数，$5+7=12$ 是 3 的倍数，$5+7+6=18$ 是 3 的倍数。

输入格式

第一行一个字符串 s；

第二行一个整数 k。

输出格式

一行一个整数，表示 k 的倍数的字串数量。

样例输入

1234
3

样例输出

4

提示

对于 20% 的数据：$1\le |s|\le 10$；

对于 40% 的数据：$1\le |s|\le 100$；

对于 70% 的数据：$1\le |s|\le 5000$；

对于 100% 的数据：$1\le |s|,k\le 1000000$，其中 $|s|$ 表示字符串 s 的长度，s 不含前导 0。

0
7

1

5
1

1

1234
3

4