← 返回题目列表

Codeforces · 364/A

A. 矩阵

中文机器翻译题面 查看原题

您有一串十进制数字 s。让我们定义bij = si·sj。在矩阵 b 中查找这样的矩形的数量,即每个矩形中作为矩形元素的所有单元格 (i, j) 的总和 bij 等于 a。

矩阵中的矩形是一组四个整数 (x, y, z, t) (x ≤ y, z ≤ t)。矩形的元素都是单元格 (i, j),且满足 x ≤ i ≤ y、z ≤ j ≤ t。

输入

第一行包含整数 a (0 ≤ a ≤ 109),第二行包含一串十进制整数 s (1 ≤ |s| ≤ 4000)。

输出

打印一个整数——问题的答案。

请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

10
12345

输出 #1

6

输入 #2

16
439873893693495623498263984765

输出 #2

40