406880: GYM102591 H With love from A(rr)(b)ay

H. With love from A(rr)(b)ayограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Задан массив $$$A$$$ размером $$$N \times M$$$, заполненный натуральными числами. Строки массива пронумерованы от 1 до $$$N$$$ сверху вниз. Столбцы пронумерованы от 1 до $$$M$$$ слева направо. Клетку в строке номер $$$i$$$ и столбце номер $$$j$$$ назовем $$$A_{ij}$$$. Подпрямоугольником с координатами $$$x_1, y_1, x_2, y_2$$$ ($$$x_1 \leq x_2$$$ и $$$y_1 \leq y_2$$$) назовем множество всех клеток $$$A_{ij}$$$, для которых выполняется условие: $$$x_1 \leq i \leq x_2$$$ и $$$y_1 \leq j \leq y_2$$$. Введем функцию $$$f$$$($$$x_1, y_1, x_2, y_2$$$) (при этом так же $$$x_1 \leq x_2$$$ и $$$y_1 \leq y_2$$$), которая обозначает количество таких простых чисел $$$p$$$, что каждое число $$$A_{ij}$$$ в подпрямоугольнике с координатами $$$x_1, y_1, x_2, y_2$$$ делится нацело на $$$p$$$. Требуется посчитать сумму $$$f$$$($$$x_1, y_1, x_2, y_2$$$) по всем возможным подпрямугольникам.

Входные данные

На первой строке выходных данных заданы два числа — $$$N$$$ и $$$M$$$ ($$$1 \leq N, M \leq 1000$$$) — размеры массива.

Далее следуют $$$N$$$ строк, каждая строка содержит по $$$M$$$ натуральных чисел — элементы массива $$$A$$$ ($$$1 \leq A_{ij} \leq 10^6$$$).

Выходные данные

Выведите одно число — ответ на задачу.

ПримерыВходные данные

2 2
9 6
6 12

Выходные данные

14

Входные данные

4 4
7 6 8 9
8 7 7 9
3 6 6 1
5 10 3 7

Выходные данные

29

Примечание

В первом примере существует лишь 9 подпрямоугольников:

1) Для [9] ответ 1

2) Для [6] ответ 2

3) Для [6] ответ 2

4) Для [12] ответ 2

5) Для [9, 6] ответ 1

6) Для [9, 6] ответ 1

7) Для [6, 12] ответ 2

8) Для [6, 12] ответ 2

9) Для [9, 6, 6, 12] ответ 1

Итого 14.