子矩阵和

题目描述

给定由数字 $0 \sim 9$ 构成的字符串 $S$，长度为 $n$。构造 $n \times n$ 矩阵，第 $i$ 行第 $j$ 列元素为 $S_i \times S_j$。给定整数 $T$，求有多少个子矩阵的元素之和恰好等于 $T$。

输入格式

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

输出格式

一行一个整数表示答案。

数据范围

$0 \leq T \leq 10^9$，$|S| \leq 4000$

样例

样例输入

5
123

样例输出

2

说明

矩阵为：

1 2 3
2 4 6
3 6 9

符合条件的子矩阵为 $[(2,1),(3,1)]$（和为5）与 $[(1,2),(1,3)]$（和为5）。