Дана строка из десятичных цифр s. Определим bij = si·sj. Найдите в матрице b количество таких прямоугольников, что сумма bij для всех клеток (i, j), являющихся элементами прямоугольника, в каждом прямоугольнике равна a.
Прямоугольником в матрице называется четверка чисел (x, y, z, t) (x ≤ y, z ≤ t). Элементами прямоугольника называются все клетки (i, j), такие, что x ≤ i ≤ y, z ≤ j ≤ t.
Выходные данные
Выведите единственное целое число — ответ на задачу.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
12345
|
6
|
|
2
|
16
439873893693495623498263984765
|
40
|