题目描述

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

给定一个由数字 $0\sim 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

样例解释 1

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

数据范围

对于 $30\%$ 的数据，$|S|\leq 50$。

对于 $50\%$ 的数据，$|S|\leq 500$。

对于 $100\%$ 的数据，$0\leq T\leq 10^9$，$|S|\leq 4000$。