You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

给定一个由数字 $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$，$Alice$ 想知道这个矩阵中有多少个不同的子矩阵，其内部所有元素之和恰好等于 $T$。

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

Format

Input

第一行一个整数 $T$。

第二行一个字符串 $S$。

Output

一行一个整数表示答案。

Samples

样例输入

5
123

样例输出

2

样例解释

A矩阵为：

1 2 3

2 4 6

3 6 9

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

Limitation

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

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

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