题目描述

Dave 在研究一种数字字符串矩阵时遇到了一个挑战。

给定一个由数字 0～9 构成的字符串 $S$，其长度为 $n$。 他可以据此构造一个 $n \times n$ 的矩阵，其中位于第 $i$ 行第 $j$ 列的元素等于 $S$ 中第 $i$ 个字符对应数字乘以第 $j$ 个字符对应数字的乘积。 例如，若 $S$ 的第 3 位是 5、第 7 位是 2，则矩阵中 $(3,7)$ 位置（第三行第七列）的元素为 $5 \times 2 = 10$。

现在，给定一个整数 $T$，Dave 想知道这个矩阵中有多少个不同的子矩阵，其内部所有元素之和恰好等于 $T$。

这里的子矩阵定义为由若干连续行和列围成的矩形区域（包括只含单个元素的矩形）。请你帮助他解决这个问题。

输入格式

• 第一行一个整数 $T$。
• 第二行一个字符串 $S$。

输出格式

• 一行一个整数表示答案。

5
123

2

提示

A矩阵为：
1 2 3
2 4 6
3 6 9
符合题意的子矩阵为 [(2,1),(3,1)] 与 [(1,2),(1,3)]（用矩阵的左上角和右下角坐标表示矩阵）。

数据范围

• 对于 30% 的数据，$\lvert S\rvert \le 50$；
• 对于 50% 的数据，$\lvert S\rvert \le 500$；
• 对于 100% 的数据，$0 \le T \le 10^{9}$，$\lvert S\rvert \le 4000$。