Задача 453
Четырехугольники на сетке

Простой четырехугольник - это многоугольник, имеющий четыре несовпадающие вершины, не имеющий прямых углов и не пересекающий сам себя.

Пусть Q(m, n) будет количеством простых четырехугольников, чьи вершины являются точками решетки с координатами (x,y), удовлетворяющими 0 ≤ x ≤ m и 0 ≤ y ≤ n.

Например, Q(2, 2) = 94, как показано ниже:

Также можно показать, что Q(3, 7) = 39590, Q(12, 3) = 309000 и Q(123, 45) = 70542215894646.

Найдите Q(12345, 6789) mod 135707531.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net